📚 Drozdek (Ch. 8)
A directed graph
A weighted graph
A Subgraph (in blue)
The degree of a vertex \(v\) is the number of edges incident with \(v\).
A vertex with no incident edges is called an isolated vertex.
Vertex Degrees
Drozdek, Figure 8.2
Drozdek, Figure 8.2
Drozdek, Figure 8.2
Much like tree traversals, vertices are “visited” one at a time.
Unlike trees, graphs have cycles, so tree traversal algorithms would result in infinite loops.
Vertices must be “marked” to avoid re-visiting the same vertex.
Isolated vertices must also be visited in some way.
This algorithm generates a tree (or forest , a set of trees) called a spanning tree.
We have discussed Depth-First traversals, where the traversal choose one path and “follows” it as far as possible before returning to try other paths.
The Breadth-First Traversal instead focuses on visiting all neighboring vertices before proceeding to other vertices.
In a tree-like structure, we could visualize this as working across each level of the tree before proceeding further “down” toward the leaves.
In a graph, the idea is the same - work on all vertices you can discover at the same “level” (distance from the start) before moving further into the graph.
Whereas depth-first traversals made use of a stack as the primary “bookkeeping” data structure to allow backtracking, breadth-first traversals will use a queue to aid in prioritizing the ordering of vertex visits. The general algorithm is:
function breadthFirstSearch(graph G):
let unseen := all vertices from G
let edges := empty List {}
let working := empty Queue {}
for each vertex v in unseen do
remove v from unseen
enqueue v into working
while working is not empty do
v := dequeue from working
for all vertices u adjacent to v in G do
if u is in unseen
enqueue u into working
insert edge(vu) into edges
return edges
See also: Drozdek pg. 397
Drozdek Fig. 8.5
We’ll start traversing from (a).
Drozdek Fig. 8.5
We see the nodes with edges from (a) and queue them up…
Drozdek Fig. 8.5
From (e) we don’t discover anything new; just mark it and continue.
Drozdek Fig. 8.5
From (f) we don’t discover anything new; just mark it and continue.
Drozdek Fig. 8.5
From (g) we discover (b) and add it to the queue.
Drozdek Fig. 8.5
From (i) we don’t discover anything new; just mark it and continue.
Notice that the edges (ef), (ei), (fi) will not be traversed at this point.
Drozdek Fig. 8.5
From (b) we don’t discover anything new; just mark it and continue.
Now our queue is empty, but we have unvisited nodes, so we pick one ( (c) ) and continue.
Drozdek Fig. 8.5
From (b) we discover (h) and add it to the queue.
Drozdek Fig. 8.5
From (h) we discover (d) and add it to the queue.
Drozdek Fig. 8.5
From (d) we don’t discover anything new.
Also, our queue is empty now, so we check for unvisited nodes…
But there are none. That means we are finished.
Drozdek Fig. 8.5
Final state, with visit ordering shown.
Edges that were traversed are shown in solid black; edges not traversed are shown in dotted grey.
Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes.
Mark all nodes except the initial node as unvisited. Set the initial node as current. Create a set of the unvisited nodes called the unvisited set consisting of all the nodes except the initial node.
function Dijkstra(Graph, source):
let Q be an empty queue
for each vertex v in Graph.Vertices: # Initialize
dist[v] ← INFINITY
prev[v] ← UNDEFINED
add v to Q
dist[source] ← 0
while Q is not empty:
u ← vertex in Q with min dist[u]
remove u from Q
for each neighbor v of u still in Q:
alt ← dist[u] + Graph.Edges(u, v)
if alt < dist[v]:
dist[v] ← alt
prev[v] ← u
return dist[], prev[]
Source: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
Drozdek, Figure 8.7
Drozdek, Figure 8.7
Drozdek, Figure 8.7
Drozdek, Figure 8.7
Drozdek, Figure 8.7
Drozdek, Figure 8.7
Drozdek, Figure 8.7
Drozdek, Figure 8.7
Drozdek, Figure 8.7
Drozdek, Figure 8.7
Drozdek, Figure 8.7
Drozdek, Figure 8.7
You can find the shortest path by backtracking to the points where the “best” assigned distance updated to the final value.
Dijkstra’s Algorithm does not work if some weights are negative.
To solve this problem, a label-correcting algorithm can be used.
Ford’s algorithm is an example.
function BellmanFord(list vertices, list edges, vertex source) is
distance := list of size n
predecessor := list of size n
for each vertex v in vertices do // Step 1: initialize graph
distance[v] := inf // Init. vertex dist. to infinity
predecessor[v] := null // Init. a null predecessor
distance[source] := 0 // Dist. to self is zero.
repeat |V|−1 times: // Step 2: relax edges repeatedly
for each edge(u, v) with weight w in edges do
if distance[u] + w < distance[v] then
distance[v] := distance[u] + w
predecessor[v] := u
// Step 3: error if neg. weight cycle
if a negative-weight cycle exists, raise an error
return distance, predecessor
Source: https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
Based on Drozdek, Chapter 8.3
function labelCorrectingAlgorithm (weighted simple digraph Graph, vertex first)
for all vertices v in Graph do // Step 1: initialize graph
currDist[v] := inf // Init. vertex dist. to infinity
currDist[first] := 0 // Dist. to self is zero
toBeChecked := {first} // Set of vertices to check
while toBeChecked is not empty // Step 2: relax edges repeatedly
v := a vertex in toBeChecked
remove v from toBeChecked
for all vertices u adjacent to v do
if currDist[u] > currDist[v] + weight(edge(vu))
currDist[u] := currDist[v] + weight(edge(vu))
predecessor[u] := v
add u to toBeChecked if it is not there
Efficiency hinges on the data structure used for toBeChecked
Based on Drozdek, Chapter 8.3
function WFI(matrix weights):
for i := 1 to numberOfVertices do
for j := 1 to numberOfVertices do
for k := 1 to numberOfVertices do
if weights[j][k] > weights[j][i] + weights[i][k] then
weights[j][k] := weights[j][i] + weights[i][k] then
return weights
weights
is an adjacency matrix
N-cubed efficiency…
Can detect cycles if the diagonal of the weight matrix is initialized to infinity.
We often need to detect cycles in both directed and undirected graphs.
Depth-First Traversal can be used for this.
function detectCyclesDFS(vertex v, Graph G):
let static visited := {} // Set of visited nodes (shared between calls)
let static edges := {} // Set of edges found (shared for all calls)
let has_cycle := false
insert v into visited
for each vertex u in G adjacent to v do
if u is not in visited:
has_cycle := has_cycle || detectCyclesDFS(u, G)
else if edge(u,v) is not in edges:
has_cycle := true // cycle detected
add edge(u,v) to edges
return has_cycle
Algorithm is a bit more complicated. Label vertices as “working” when we discover them, and as “finished” when we exhaust recursively traversing all adjacent nodes.
If we see a vertex labeled “working” for the second time, we have a cycle.
function detectDigraphCyclesDFS(vertex v, Graph G):
let has_cycle := false
label[v] = WORKING // label the current vertex as "working"
for each vertex u in G adjacent to v do
if u has no label yet:
has_cycle := has_cycle || detectDigraphCyclesDFS(u, G)
else if label[u] is not FINISHED
has_cycle := true // cycle detected
num[v] = FINISHED // mark v as "finished"
return has_cycle
(Euler is pronounced very much like “oiler”.)
An Eulerian trail is a path that includes all edges of the graph only once.
An Eulerian cycle is a cycle that is also an Eulerian trail.
An Eulerian graph is a graph that has an Eulerian cycle.
“Only take a bridge when there is no other path to take.”
function FleuryAlgorithm(undirected graph G):
let success := false
let v := any vertex in G
let path := v
let untraversed := G
while v has untraversed edges
let e represent an edge to be determined later
if edge(v,u) is the only untraversed edge
e := edge(v,u)
remove v from untraversed
else e := edge(v,u) which is not a bridge in untraversed
path := path + u
remove e from untraversed
v := u
if untraversed has no edges
success := true
return success, path
Drozdek, Figure 8.34
An Eulerian graph
An Eulerian path illustrated (numbers indicate traversal order from b)
Hamiltonian Graph
Image: https://commons.wikimedia.org/wiki/File:Hamiltonian_path.svg
Given a set of \(n\) cities, find the minimum length tour in which each city is visited exactly once, then you return home.
CS 50x2 Accelerated Programming Series
Graphs