Geology Reference
In-Depth Information
distances, except
d
(
x
,
x
), are initialized to infinite.
When the algorithm is running, a value of dis-
tance
d
(
x
,
y
)
D1
indicates that the corresponding
node
y
has not yet been visited. Finally, a flag
f
is
used to test if at least one node with the distance
i
C
1 has been found in the current iteration. This
algorithm is structured on three nested loops.
The two innermost loops are located at line #1.
They check if the nodes
y
with actual distance
i
from
x
have a node
z
in their neighborhoods
I
(
y
) that has not yet been visited. If a node
z
of this kind is found, its distance from
x
is set
to
i
C
1andtheflag
f
is set to
true
, indicating
that algorithm must execute a new iteration. The
loop between lines #1 and #4 is responsible for
increasing the variable
i
at each iteration and gov-
erns the mechanism of fan-shaped expansion that
is characteristic of this algorithm. The procedure
ends, at line #2, when all reachable nodes have
been visited. Such a condition is clearly indicated
by a value
f
D
false
after the execution of the
inner loops at line #1.
A more general class of data structures is
represented by the
weighted graphs
.Inmany
situations, the arcs or the edges of a graph carry
information. For example, in a graph representing
routes between cities, the nodes would contain
information about the cities, while the edges
could store the distance in km between any pair
of neighbor cities. Therefore, the binary func-
tion (
A2.2
) can be considered as a special case
of data structure, such that each arc has unit
length.
In the most general case, ¢ can be defined as a
non-negative real function on
D
2
:
¢
W
x
i
;x
j
2
D
2
higher powers of
A
,sayingthatanelement
A
ij
of
the matrix
A
k
represents the number of paths of
length
k
joining node
x
i
to
x
j
. In general, given
any two vertices
x
and
y
, several distinct paths of
different length may exist that join these nodes.
For example, in Fig.
A2.3
node
x
2
is the end
vertex of three walks that start at
x
5
, namely:
(
x
5
,
x
2
), (
x
5
,
x
4
,
x
3
,
x
2
), and (
x
5
,
x
4
,
x
1
,
x
3
,
x
2
), which
have length one, three, and four respectively. The
distance d
(
x
,
y
) between two nodes is defined as
the length of the smallest path joining
x
and
y
.
It is easy to verify that for any undirected graph
G
D
(
D
,¢), the function
d
isametricon
D
:
1: d .x;y/
0
I
d.x;y/
D
0
”
x
D
y
(A2.4)
2: d .x;y/
D
d.y;x/
(A2.5)
3: d .x;y/
C
d.y;
z
/
d.x;
z
/
(A2.6)
A major task in computer science is to find al-
gorithms that compute the function
d
for any pair
of nodes in a graph
G
. The following
breadth-
first search algorithm
(BFS) is a classic solu-
tion to this problem. Given
x
2
D
,theBFS
algorithm determines
d
(
x
,
y
) for each
y
2
D
.
When the algorithm stops, if
d
(
x
,
y
)
D1
for some
node
y
,thenvertex
y
cannot be reached starting
from
x
:
Algorithm A2.2
bfs
(
x
): Distances from a node
x
Input:
x
2
D
Output:
d
(
x
,
y
)
8
y
2
D
f
0:
i
0;
d
(
x
,
x
)
0;
8
y
2
D
j
y
¤
x
,
d
(
x
,
y
)
1
;
f
false
1:
8
y
2
D
j
d
(
x
,
y
)
D
i
,
8
z
2
I
(
y
)
j
d
(
x
,
z
)
D1
,
d
(
x
,
z
)
i
C
1, f
true
2: f
D
false
)
stop
3:
i
i
C
1; f
false
4: jump #1
g
!
¢
ij
2
Œ0;
1
(A2.7)
An example of weighted undirected graph is
illustrated in Fig.
A2.4
. Just like normal graphs,
in weighted graphs ¢(
x
,
y
)
D
0 is interpreted as
absence of direct link between nodes
x
and
y
.
A substantial difference of this class of graphs
with respect to unweighted data structures is
represented by the possibility that the shortest
path between two nodes
x
and
y
does not coin-
cide with the path having the smallest number
The variable
i
, which at step #0 is initialized
to zero, represents the current estimate of the
distance of a node from the starting node. All
