CSE 331 Lecture Notes - Lecture 9: Directed Acyclic Graph, Glossary Of Graph Theory Terms, Topological Sorting
Graph Traversal
• Most of the time, we want to traverse through a graph
o Pick any vertex to start, mark it “visited”
o Put all neighbors of first vertex in a “to be visited” collection
o Move onto next vertex in “to be visited” collection
o Mark vertex as “visited”
o Put all unvisited neighbors in “to be visited”
o Move onto next vertex “to be visited” collection
o Repeat
• Breadth First Search (BFS)
o Pick first node and find the neighbors and add “to visit” queue
o Mark first node as visited
o Move to first neighbor in queue and repeat
• Depth First Search
o BFS uses a queue to order which vertex we move to next
o We can use a stack instead
o This will change the order that we visit the nodes
Shortest Paths
• The length of a path is the sum of the edge weights of that path
o Sometimes the weights aren’t uniform
o Sometimes negative weights make sense, but usually we stick with positive
weights
• Given a directed graph G and vertices s and t, find the shortest path from s to t
• In an unweighted graphs, to find the set of vertices at distance k, find set of vertices at
distance k-1 and see if any of them have an outgoing edge to an undiscovered vertex.
o We can do this with BFS. It doesn’t mention a target, but it finds the shortest path
from s to every other vertex.
• Given a weighted graph, we can add in node to make all edges the same weight
o We can then run this algorithm using BFS
o Won’t really work if we have large edge weights or irrational numbers
• Dijkstra’s Algorithm
o If we process only the vertex closest in estimated distance, we won’t ever find a
shorter path to be a processed vertex
Ordering
• Topological sort: given a directed graph G, find an ordering of the vertices so all edges
go from left to right
o Cannot always be done due to circular graphs
o Directed Acyclic Graph: a directed graph without any cycles (DAG) will always
work
• As long as a vertex doesn’t have any edges going into it, we can add it to the ordering.
Strongly Connected Components
• A subgraph C such that every pair of vertices in C is connected via some path in both
directions, and there is no other vertex which is connected to every vertex of C in both
directions
• Finding the SCC lets you collapse the graph into a meta-structure (simplifies everything)
