Adjacency List
for a directed, weighted graph
Three classes
› DirectedGraph
› Vertex
– List
– bool Visited (used for depth-first and breadth-first searches)
› Edge
– Vertex
Initially
V
DirectedGraph
Let’s add four vertices using AddVertex
› “lax” › “yul” › “yyz” › “lhr”
lax
yul
yyz
lhr
lax false
yul false
V
DirectedGraph
yyz false
lhr false
Vertex
Now let’s add six edges using AddEdge
› (“lax”, “yul”, 55) › (“yyz”, “lhr”, 40) › (“lax”, “yyz”, 35) › (“lhr”, “yyz”, 20) › (“yyz”, “yul”, 65) › (“lax”, “lhr”, 70)
lax 70
20
40 lhr
55
35
yul
65
yyz
55
lax false
35
yul false
V
70
65
yyz false
20
lhr false
DirectedGraph
40
Vertex Edge
RemoveEdge(“lax”, “yyz”)
55
35
lax 70
20
40 lhr
yul
65
yyz
55
lax false
35
yul false
V
70
65
yyz false
20
lhr false
DirectedGraph
40
Vertex Edge
lax false
55
yul false
V
70
yyz false
65
20
lhr false
DirectedGraph
40
Vertex Edge
RemoveVertex(“yyz”)
› Two steps
– Remove edges leading to “yyz” – Remove vertex “yyz”
yul
lax 70
20
40 lhr
55
35
65
yyz
55
lax false
35
yul false
V
70
65
yyz false
20
lhr false
DirectedGraph
40
Vertex Edge
35
yul false
V
yyz false
70
65
20
lhr false
DirectedGraph
40
Vertex Edge
55
lax false
yul false
V
70
65
yyz false
20
lhr false
DirectedGraph
40
Vertex Edge
55
lax false
55
lax false
yul false
V
70
?
65
yyz false
20
lhr false
DirectedGraph
40
Vertex Edge
yul false
V
70
65
yyz false
20
lhr false
DirectedGraph
40
Vertex Edge
55
lax false
lax false
yul false
V
65
yyz false
lhr false
DirectedGraph
40
Vertex Edge
55
70
yul false
V
70
DirectedGraph
lhr false
Vertex Edge
55
lax false
After “yyz” has been removed
lax
55
70
yul
lhr
Two supporting methods
› int FindVertex(T name) // of DirectedGraph class
– Returns the index of the given vertex in V (if found); otherwise returns -1
› int FindEdge(T name) // of Vertex class
– Returns the index of the given (adjacent) vertex in E (if found); otherwise returns -1
Comparison
ADJACENCY MATRIX
› Better for dense graphs
› Time complexity of the four basic methods is not dependent on the number of edges
ADJACENCY LIST
› Better for sparse graphs
› Time complexity of RemoveVertex is dependent on the number of edges
Exercises
› Implement the same additional methods that you did for the Adjacency Matrix implementation.
› Argue why the time complexity of RemoveVertex is O(max(n,m)) where n is the number of vertices and m is the number of edges in the Graph. What assumption(s) do you make about the List method RemoveAt?
› Modify the Adjacency List implementation of the class DirectedGraph if the graph is unweighted.
› Modify the Adjacency List implementation of the class DirectedGraph to allow for parallel edges (i.e., edges that have the same endpoints and orientation). Differentiate between parallel edges based on cost.