Origem: Wikipédia, a enciclopédia livre.
Em computação , o algoritmo de Brandes é um algoritmo utilizado para cálcular a intermediação de todos os vértices de um grafo sem pesos. Sua complexidade é
O
(
|
V
|
|
E
|
)
{\displaystyle O(|V||E|)}
O
(
|
V
|
+
|
E
|
)
{\displaystyle O(|V|+|E|)}
V
{\displaystyle V}
E
{\displaystyle E}
G
{\displaystyle G}
[ 1]
O
(
|
V
|
3
)
{\displaystyle O(|V|^{3})}
C
b
←
0
,
v
∈
V
;
{\displaystyle C_{b}\leftarrow 0,v\in V;}
f
o
r
s
∈
V
d
o
{\displaystyle \mathbf {for} \ s\in V\ \mathbf {do} }
S
←
pilha vazia
;
{\displaystyle S\leftarrow {\mbox{pilha vazia}};}
P
[
w
]
←
lista vazia
,
w
∈
V
;
{\displaystyle P[w]\leftarrow {\mbox{lista vazia}},w\in V;}
σ
[
t
]
←
0
,
t
∈
V
;
σ
[
s
]
←
1
;
{\displaystyle \sigma [t]\leftarrow 0,t\in V;\sigma [s]\leftarrow 1;}
d
[
t
]
←
−
1
,
t
∈
V
;
d
[
s
]
←
0
;
{\displaystyle d[t]\leftarrow -1,t\in V;d[s]\leftarrow 0;}
Q
←
fila vazia
;
{\displaystyle Q\leftarrow {\mbox{fila vazia}};}
e
n
f
i
l
e
r
a
r
s
→
Q
;
{\displaystyle enfilerar\ s\rightarrow Q;}
w
h
i
l
e
Q
n
a
o
f
o
r
v
a
z
i
o
d
o
{\displaystyle \mathbf {while} \ Q\ nao\ for\ vazio\ \mathbf {do} }
d
e
s
e
n
f
i
l
e
r
a
r
v
←
Q
;
{\displaystyle desenfilerar\ v\leftarrow Q;}
p
u
s
h
v
→
S
;
{\displaystyle push\ v\rightarrow S;}
f
o
r
e
a
c
h
v
i
z
i
n
h
o
w
d
e
v
d
o
{\displaystyle \mathbf {foreach} \ vizinho\ w\ de\ v\ \mathbf {do} }
/
/
w
e
n
c
o
n
t
r
a
d
o
p
e
l
a
p
r
i
m
e
i
r
a
v
e
z
?
{\displaystyle //\ w\ encontrado\ pela\ primeira\ vez?}
i
f
d
[
w
]
<
0
t
h
e
n
{\displaystyle \mathbf {if} \ d[w]<0\ \mathbf {then} }
e
n
f
i
l
e
r
a
r
w
→
Q
;
{\displaystyle enfilerar\ w\rightarrow Q;}
d
[
w
]
←
d
[
v
]
+
1
;
{\displaystyle d[w]\leftarrow d[v]+1;}
e
n
d
{\displaystyle \mathbf {end} }
/
/
m
e
n
o
r
c
a
m
i
n
h
o
a
t
e
w
p
o
r
v
?
{\displaystyle //\ menor\ caminho\ ate\ w\ por\ v?}
i
f
d
[
w
]
=
d
[
v
]
+
1
t
h
e
n
{\displaystyle \mathbf {if} \ d[w]=d[v]+1\ \mathbf {then} }
σ
[
w
]
←
σ
[
w
]
+
σ
[
v
]
;
{\displaystyle \sigma [w]\leftarrow \sigma [w]+\sigma [v];}
a
d
i
c
i
o
n
a
r
v
→
P
[
w
]
;
{\displaystyle adicionarv\rightarrow P[w];}
e
n
d
{\displaystyle \mathbf {end} }
e
n
d
{\displaystyle \mathbf {end} }
e
n
d
{\displaystyle \mathbf {end} }
δ
[
v
]
←
0
,
v
∈
V
;
{\displaystyle \delta [v]\leftarrow 0,v\in V;}
/
/
S
r
e
t
o
r
n
a
o
s
v
e
r
t
i
c
e
s
e
m
o
r
d
e
m
n
a
o
−
c
r
e
s
c
e
n
t
e
d
a
d
i
s
t
a
n
c
i
a
a
p
a
r
t
i
r
d
e
s
{\displaystyle //\ S\ retorna\ os\ vertices\ em\ ordem\ nao-crescente\ da\ distancia\ a\ partir\ de\ s}
w
h
i
l
e
S
n
a
o
f
o
r
v
a
z
i
o
d
o
{\displaystyle \mathbf {while} \ S\ nao\ for\ vazio\ \mathbf {do} }
p
o
p
w
←
S
;
{\displaystyle pop\ w\leftarrow S;}
f
o
r
v
∈
P
[
w
]
d
o
δ
[
v
]
←
δ
[
v
]
+
σ
[
v
]
σ
[
w
]
⋅
(
1
+
δ
[
w
]
)
;
{\displaystyle \mathbf {for} \ v\in P[w]\ \mathbf {do} \ \delta [v]\leftarrow \delta [v]+{\frac {\sigma [v]}{\sigma [w]}}\cdot (1+\delta [w]);}
i
f
w
≠
s
t
h
e
n
C
b
[
w
]
←
C
b
[
w
]
+
δ
[
w
]
;
{\displaystyle \mathbf {if} \ w\neq s\ \mathbf {then} \ C_{b}[w]\leftarrow C_{b}[w]+\delta [w];}
e
n
d
{\displaystyle \mathbf {end} }
e
n
d
{\displaystyle \mathbf {end} }
Referências Centralidade
Intermediação
![{\displaystyle P[w]\leftarrow {\mbox{lista vazia}},w\in V;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/154da1032bc6340ebec70301f76fdf3d9cc72ac2)
![{\displaystyle \sigma [t]\leftarrow 0,t\in V;\sigma [s]\leftarrow 1;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8b3e926ac7728880422868d9ab3d96fd9341e14f)
![{\displaystyle d[t]\leftarrow -1,t\in V;d[s]\leftarrow 0;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/11917eab75b1e48439c63bbccff42533bc48231f)
![{\displaystyle \mathbf {if} \ d[w]<0\ \mathbf {then} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/03861685e0c408547dfa1e29538722bf3799dc26)
![{\displaystyle d[w]\leftarrow d[v]+1;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5e23a15ee76bf86b3c319183c5c0a55b8b2c4f81)
![{\displaystyle \mathbf {if} \ d[w]=d[v]+1\ \mathbf {then} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/1b840b55909838fd999f58b329712450a0054cc8)
![{\displaystyle \sigma [w]\leftarrow \sigma [w]+\sigma [v];}](https://wikimedia.org/api/rest_v1/media/math/render/svg/133f724a3eab9eac323a77c9084a763460847a58)
![{\displaystyle adicionarv\rightarrow P[w];}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3782e36a5402506845c2ae76ba07ec4346dadb9d)
![{\displaystyle \delta [v]\leftarrow 0,v\in V;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ccd109e62a77e7d39cedf96a7c15a99d8dc3dcf1)
![{\displaystyle \mathbf {for} \ v\in P[w]\ \mathbf {do} \ \delta [v]\leftarrow \delta [v]+{\frac {\sigma [v]}{\sigma [w]}}\cdot (1+\delta [w]);}](https://wikimedia.org/api/rest_v1/media/math/render/svg/038524932f40e909a795ead6404f8e1909b5455c)
![{\displaystyle \mathbf {if} \ w\neq s\ \mathbf {then} \ C_{b}[w]\leftarrow C_{b}[w]+\delta [w];}](https://wikimedia.org/api/rest_v1/media/math/render/svg/12810a4eacc2d7e3729936f09c838659ef77756e)