14.10. Graphs¶
14.10.1. Graphs¶
14.10.1.1. Graphs¶
A graph \(G = (V, E)\) consists of a set of vertices \(V\), and a set of edges \(E\), such that each edge in \(E\) is a connection between a pair of vertices in \(V\).
The number of vertices is written \(|V|\), and the number edges is written \(|E|\).
14.10.1.2. Paths, Cycles¶
14.10.1.3. Connected Components¶
The maximum connected subgraphs of an undirected graph are called connected components.
14.10.1.4. Directed Graph Representation¶
14.10.1.5. Undirected Graph Representation¶
14.10.1.6. Representation Space Costs¶
- Adjacency Matrix Space:
\(|V|^2\)
Small constants
- Adjacency List Space:
\(|V| + |E|\)
Larger constants
14.10.1.7. Graph ADT¶
14.10.1.8. .¶
.
14.10.1.9. Visiting Neighbors¶
14.10.1.10. Graph Traversals¶
Some applications require visiting every vertex in the graph exactly once.
The application may require that vertices be visited in some special order based on graph topology.
- Examples:
Artificial Intelligence Search
Shortest paths problems
14.10.1.11. Graph Traversals (2)¶
To insure visiting all vertices:
14.10.1.12. Depth First Search (1)¶
14.10.1.13. Depth First Search (2)¶
14.10.1.14. Depth First Search (3)¶
Cost: \(\Theta(|V| + |E|)\).
14.10.1.15. Breadth First Search (1)¶
- Like DFS, but replace stack with a queue.
Visit vertex’s neighbors before continuing deeper in the tree.
14.10.1.16. Breadth First Search (3)¶
14.10.1.17. Topological Sort¶
Problem: Given a set of jobs, courses, etc., with prerequisite constraints, output the jobs in an order that does not violate any of the prerequisites.
14.10.1.18. Depth-First Topological Sort (1)¶
14.10.1.19. Depth-First Topological Sort (2)¶
14.10.1.20. .¶
.
14.10.1.21. Queue-Based Topsort (1)¶
14.10.1.22. .¶
.
14.10.1.23. Queue-Based Topsort (2)¶
14.10.1.24. .¶
.
14.10.1.25. Shortest Paths Problems¶
Input: A graph with weights or costs associated with each edge.
Output: The list of edges forming the shortest path.
- Sample problems:
Find shortest path between two named vertices
Find shortest path from S to all other vertices
Find shortest path between all pairs of vertices
Will actually calculate only distances.
14.10.1.26. Shortest Paths Definitions¶
\(d(A, B)\) is the shortest distance from vertex \(A\) to \(B\).
\(w(A, B)\) is the weight of the edge connecting \(A\) to \(B\).
If there is no such edge, then \(w(A, B) = \infty\).
14.10.1.27. Single-Source Shortest Paths¶
Given start vertex \(s\), find the shortest path from \(s\) to all other vertices.
Try 1: Visit vertices in some order, compute shortest paths for all vertices seen so far, then add shortest path to next vertex \(x\).
Problem: Shortest path to a vertex already processed might go through \(x\).
Solution: Process vertices in order of distance from \(s\).
14.10.1.28. Dijkstra’s Algorithm Example¶
14.10.1.29. .¶
.
14.10.1.30. Dijkstra’s Implementation¶
14.10.1.31. Implementing minVertex¶
Issue: How to determine the next-closest vertex? (I.e., implement
minVertex)
- Approach 1: Scan through the table of current distances.
Cost: \(\Theta(|V|^2 + |E|) = \Theta(|V|^2)\).
Approach 2: Store unprocessed vertices using a min-heap to implement a priority queue ordered by \(D\) value. Must update priority queue for each edge.
Cost: \(\Theta((|V| + |E|)log|V|)\)
14.10.1.32. Approach 1¶
14.10.1.33. Approach 2¶
14.10.1.34. .¶
.
14.10.1.35. All-pairs Shortest Paths (1)¶
We could run Shortest Paths starting at each vertex.
- Better is to use Floyd’s algorithm.
An example of Dynamic Programming
Simpler than it sounds: A trivial triple loop
Define a k-path from vertex \(v\) to vertex \(u\) to be any path whose intermediate vertices (aside from \(v\) and \(u\)) all have indices less than \(k\).
14.10.1.36. All-pairs Shortest Paths (2)¶
14.10.1.37. Floyd’s Algorithm¶
14.10.1.38. Minimal Cost Spanning Trees¶
Minimal Cost Spanning Tree (MST) Problem:
Input: An undirected, connected graph G.
- Output: The subgraph of G that
has minimum total cost as measured by summing the values of all the edges in the subset, and
keeps the vertices connected.
14.10.1.39. MST Example¶
14.10.1.40. Prim’s MST Algorithm¶
14.10.1.41. .¶
.
14.10.1.42. Implementation 1¶
14.10.1.43. Alternate Implementation¶
As with Dijkstra’s algorithm, the key issue is determining which vertex is next closest.
As with Dijkstra’s algorithm, the alternative is to use a priority queue.
Running times for the two implementations are identical to the corresponding Dijkstra’s algorithm implementations.
14.10.1.44. Kruskal’s MST Algorithm (1)¶
Initially, each vertex is in its own MST.
- Merge two MST’s that have the shortest edge between them.
Use a priority queue to order the unprocessed edges. Grab next one at each step.
How to tell if an edge connects two vertices already in the same MST?
- Use the UNION/FIND algorithm with parent-pointer
representation.
14.10.1.45. Kruskal’s MST Algorithm (2)¶
14.10.1.46. .¶
.
14.10.1.47. Kruskal’s MST Algorithm (3)¶
- Cost is dominated by the time to remove edges from the heap.
Can stop processing edges once all vertices are in the same MST
Total cost: \(\Theta(|V| + |E| log |E|)\).
