0 1 2 3 4 5 0 inf 9 inf inf 1 inf 1 9 inf 8 inf 6 inf 2 inf 8 inf 5 inf 2 3 inf inf 5 inf inf inf 4 1 6 inf inf inf 7 5 inf inf 2 inf 7 infThe adjanceny list is:
0 --> {1,9} --> {4,1} 1 --> {0,9} --> {2,8} --> {4,6} 2 --> {1,8} --> {3,5} --> {5,2} 3 --> {2,5} 4 --> {0,1} --> {1,6} --> {5,7} 5 --> {2,2} --> {4,7}
a b c d e f g h i a 0 1 1 0 0 0 0 0 0 b 0 0 0 1 0 0 0 1 0 c 0 0 0 1 1 0 0 0 0 d 0 0 0 0 0 0 0 1 0 e 0 0 0 0 0 0 1 0 0 f 0 0 0 0 0 0 0 0 1 g 0 0 1 0 0 0 0 0 0 h 0 0 0 0 0 0 1 0 0 i 0 0 1 0 0 0 0 0 0The adjanceny list is:
a --> {b} --> {c} b --> {d} --> {h} c --> {d} --> {e} d --> {h} e --> {g} f --> {g} --> {i} g --> {c} h --> {g} i --> {c}
bool Graph::Detect_Cycle() { return Detect_Cycle(0); } bool Graph::Detect_Cycle(int v) { mark v as visited if (v has more than 1 visited neighbor) return true; bool temp=false; for (each unvisited neighbor u of v) temp=temp||Detect_Cycle(u); return temp; }
a h / | \ / / | \ / b c d | | | | e f / \ / \ i gThe DFS tree is:
a h / | / / | / b c---d | | e---f / \ / \ i gThe MST is:
a h / | / / | / b c---d | | e---f / / / / i g
b / c h / / \ / a e d / \ / / \ g i \ / \ / f
If the graph is not connected, then at least one vertex will not be visited,
as all of our traversal algorithms rely on the crossing of edges. If no
path of successive edges connects two nodes (which is necessary if the graph
is to be disconnected), then one of them (at least)
will not be visited by the algorithm (since if the algorithm did visit both,
it would mean that some chain of edges allows passage from one to the
other).
Conversly, if DFS misses even one vertex, that means that no succession of
edges leads to that vertex from some vertex, meaning that the graph is
disconnected (if another node is connected to the vertex in question and to
the initial vertex, it gives a path from the initial to the final vertex,
contradicting the assumption that DFS missed the final vertex).
Thus, the two conditions are equivalent.
Loop Invariant: Once a vertex v is placed in S, W[v] is the weight of the absolutely shortest path from 0 to v and will not change.
Base case: for Step=1, S consists of only one vertex (0), and W[0]==0, which
is in fact the shortest path from 0 to 0, so base case is done.
Inductive Hypothesis: We assume that the invariant is true for steps 1 to
N.
Inductive Step: The inductive hyp. tells us that S consists of {v1, v2,
... , vN, w}, and that W[v1], ..., W[vN] is the shortest path cost from 0 to
each of the first N vertices. We need to show that W[w] is the cost of the
shortest path from 0 to w: Suppose there is a shorter path. Then it must
pass through some vertex u not in S (because by construction, W[w] is the
shortest path possible by using only vertices in S). Then the shortest path
cost for w (call it x) is the shortest path cost for u (call it y) added to
the shortest path cost from u to w (call it z), i.e.: x=y+z. But then y is
less than x, and neither u nor w was in S in the N'th step, so u would have
been added to S in the N+1'st step, and *NOT* w. This contradiction shows
that the invariant is in fact true. QED.