Graph Traversal
- st-connectivity is a decision problem determining if there is a path between two vertices and in a graph .
Breadth-First Search (BFS)
- Let be a graph and be a starting node.
- The layers of the node in the graph constructed by BFS are defined as follows:
- (the set of vertices adjacent to )
- (the set of vertices adjacent to the vertices in that are not in )
- is the set of vertices at distance from .
- BFS is not only determining the nodes reachable from , but also the shortest path from to them.
- For each , layer produced by BFS consists of all nodes at distance exactly from .
- There is a path from to if and only if appears in some layer.
- BFS produces a BFS tree rooted at which is a tree .
- (the set of nodes reachable from )
- If and , then .
- (3.4) If and (a non-tree edge), then either and are in the same layer, or they are in adjacent layers.
- BFS explores the connected component in the graph containing .
- is the set of nodes reachable from , produced as the following algorithm:
- Start with
- While there exists an edge such that and , add to .
- (note: in this context, connected component refers to the set of nodes, not the subgraph induced by them)
- is the set of nodes reachable from , produced as the following algorithm:
- The layers of the node in the graph constructed by BFS are defined as follows:
Layered BFS Algorithm
BFS Algorithm:
Runs in O(n+m) time if the graph is represented as an adjacency list.
---
BFS(s):
Discovered[s]=true
for all other v, Discovered[v]=false
L[0] = {s} // layer 0
i = 0 // layer counter
T = {} // BFS tree initially empty
while L[i] != {} do
L[i+1] = {}
for each v in L[i] do
for each (v,u) in E do
if not Discovered[u] then
Discovered[u] = true
Add u to L[i+1]
Add (v,u) to T
i = i+1
Queue-based BFS Algorithm
BFS Algorithm: (Queue-based)
---
BFS(s):
Create a queue Q
Enqueue s onto Q
Discovered[s] = true
while Q is not empty do
v = Dequeue from Q
for each neighbor u of v do
if not Discovered[u] then
Discovered[u] = true
Parent[u] = v // Optional:
Enqueue u onto Q
Add (v, u) to T // Optional: if building a BFS tree
Print nodes of a tree T in BFS order:
---
Print(T, s):
Create a queue Q
Enqueue s onto Q
Discovered[s] = true
while Q is not empty do
dequeue v from Q and print v
for each child u of v do
Enqueue u onto Q
Depth-First Search (DFS)
DFS (Undirected)
- An edge is a tree edge if is visited for the first time when is explored. (i.e.
visited(u) = false
) - An edge is a back edge if is already visited when is explored. (i.e.
visited(u) = true
) - The tree that DFS constructs is called a DFS tree.
Algorithm 2.2 DFS(G)
Input: G = (V, E) connected undirected graph on n vertices
---
for all v ∈ V do
vistied(v) ← false
for all v ∈ V do
if not visited(v) then
DFS-Explore(G, v)
Algorithm 2.3 DFS-Explore(G, v)
---
visited(v) ← true
for all (v, u) ∈ E do
if not visited(u) then
DFS-Explore(G, u)
Stack-based DFS Algorithm
DFS Algorithm: (Stack-based)
Runnning time: O(n+m) (if the graph is represented as an adjacency list)
---
DFS(s):
Initialize S to be a stack with one element s
While S is not empty do
Pop v from S
If Explored[u] = false then
Set Explored[u] = true
For each edge (u,v) incident to u do
Push v onto S
binary tree traversal and DFS
todo which one of the bianry tree traversal algorithms (inorder, preorder, postorder) is a DFS algorithm on a binary tree?
DFS (Directed)
- A tree edge is an edge such that was first discovered by exploring .
- Back edges are those edges connecting a vertex to an ancestor in a depth-first tree. We consider self-loops, which may occur in directed graphs, as back edges.
- Forward edges are those nontree edges connecting a vertex to a proper descendant in a depth-first tree.
- Cross edges are all other edges. They can go between vertices in the same depth-first tree, as long as one vertex is not an ancestor of the other, or they can go between vertices in different depth-first trees.
DFS_visits_explore(G,v):
visited[v] = true
clock++
pre[v] = clock
for each edge (v,u) in E do
if not visited[u] then
DFS_visits_explore(G,u)
clock++
post[v] = clock
Finding the Set of All Connected Components
- Algorithm:
- Find the connected components that contain the node using BFS or DFS.
- Find a node (if any) in the graph that is not in any connected component found in step 1.
- Repeat step 1 with as the starting node.
- This algorithm runs in time. (even though it may run BFS or DFS multiple times, it spends a constant amount of time on each edge and node)
Testing Bipartiteness
- We can implement an algorithm to test whether a graph is bipartite by simply taking the implementation of BFS and adding an extra array
Color
over the nodes. - Whenever we get to a step in BFS where we are adding a node to a list , we assign:
Color[v] = red
if is an even number,Color[v] = blue
if is an odd number.
- At the end of this procedure, we simply scan all the edges:
- if there is any edge for which both ends received the same color, then the graph is not bipartite.
- Otherwise, the graph is bipartite.
- Thus, the total running time for the coloring algorithm is , just as it is for BFS.
Directed Graphs
Directed Graph Representation
- We can use a version of adjacency list representation for directed graphs, which is, instead of each node having a single list of neighbors, each node has two lists associated with it:
AdjOut[v]
contains all the vertices such that (outgoing edges)AdjIn[v]
contains all the vertices such that (incoming edges)
Directed Graph Traversal
- Given a directed graph :
- is the reverse graph of , where and .
- A node has a path to in if and only if has a path to in .
- By running
BFS(s)
(orDFS(s)
) on , we can find the set of all nodes reachable from in . - By running
BFS(s)
(orDFS(s)
) on , we can find the set of all nodes that can reach a given node in . - There is a simple linear-time algorithm to test if a directed graph is strongly connected
- Run
BFS(s)
on for some node . - Run
BFS(s)
on for the node - If all nodes are reachable from in both runs, then the graph is strongly connected.
- Run
lecture 3 notes
-
probelms:
- how to find all shortest paths from a given node to a given node in a graph ?
-
problem solving using reduction (reduction is the process of transforming one problem into an easier eqvivalent problem)
- given an undirected heaph G with edges with weights. we ewant an algorithme that finds the shortest path between in terms of the sum of the weights of the edges.
- will runnig of BFS algo. solve the problem?
- ans: no. counter example was shown in the lecture.
- solution:
- by using the reduction method, we can build a new graph by replacing each edge with a path of length of the minimal weight is in the original graph.
- then, we can run BFS on the new graph to find the shortest path.
- the reducion does not lose or add any shortest path. i.e. we can prove:
- for every -length path from to in , there is a -length path from to in . (length=the sum of the weights of the edges)
- for every every -length path from to in (where and are nodes in ), there is a -length path from to in .
- the running time of the new algorithm is
- will runnig of BFS algo. solve the problem?
- given an undirected heaph G with edges with weights. we ewant an algorithme that finds the shortest path between in terms of the sum of the weights of the edges.
-
exercise:
-
given a neighberhood with two-way streets. but there is a traffic jam in the city.
-
we want to make the roads one-way to solve the traffic jam.
- we have to make sure that the city remains strongly connected.
- is it always possible? no.todo
- bridge in an undirected graph is an edge in an undirected connected graph is a bridge if removing it disconnects the graph
- we have to make sure that the city remains strongly connected.
-
we’ll use in
Bridges
algo. in time O(n+m) that cheeck if G has a bridge or not. -
our question is: give an algorithm that make all roads one-way such that the city remains strongly connected.
- hint: dfs has two types of edges: (in undirected graph. in directed graph, we have more types of edges)
- tree edges - edges that are in the dfs tree
- back edges - edges that are not in the dfs tree BUT connects a node to an ancestor in the dfs tree.
- algo:
- if there is a bridge in the graph, so this road should be two-way, so we can’t make the graph directed and strongly connected.
- otherwise, we can make the graph directed and strongly connected
- correctness proof:
- every node is reachable from the root in the dfs tree.
- hint: dfs has two types of edges: (in undirected graph. in directed graph, we have more types of edges)
-
-
varient of the problem: what if we want make roads one way as much as possible..
Shortest Path Problem
- The shortest path problem is the problem of finding the shortest path between two nodes in a graph.
- single-source: finding the shortest path from a given node to all other nodes in the graph.
- single-destination: finding the shortest path from all nodes to a given node .
- all-pairs: finding the shortest path between all pairs of nodes in the graph.
- single-pair: finding the shortest path between a given pair of nodes .
- The shortest path problem can be defined for graphs whether undirected, directed, or mixed.
- The shortest path problem can be defined for graphs with or without weights on the edges.
Undirected Graphs
- we can use the BFS algorithm to find the shortest path in an undirected unweighted graph.
- for a weighted graph, we can replace each edge with a path of length equal to the weight of the edge and then run the BFS algorithm.
- cons: 1. the new graph may have multiple edges between two nodes. 2. it’s not good for weights of real numbers.
Dijkstra’s Algorithm
- Dijkstra’s algorithm is an algorithm for finding the shortest path (in terms of the sum of weights) from a given start node to every other node in a directed graph with non-negative weights.
- Although this algorithm is for a directed graph, it can be used for an undirected graph by replacing each undirected edge with two directed edges and , each with the same weight.
- Assumptions:
- the graph is connected
- non-negative weights
- The output of Dijkstra’s algorithm is a tree called the shortest path tree rooted at the start node.
- Dijkstra’s algorithm is using a priority queue which can be implemented using:
- (unsorted) Doubly linked list -
- Binary heap
- Fibonacci heap
# Dijkstra's Algorithm using Priority Queue
Dijkstra(G, s, w):
input:
G = (V, E) directed graph
non-negative weights w
s = source node
output: for each u ∈ V:
d[u] = the shortest path estimate from s to u
π[u] = the predecessor of u in the shortest path tree
----
InitPriorityQueue(Q)
d[s] = 0
Q.Insert(s, 0)
For each u ∈ G.V:
if u ≠ s:
d[u] = ∞
π[u] = null
Q.Insert(u, ∞)
While Q ≠ ∅:
u ← Q.ExtractMin() # Remove & return the node with the smallest d[u]
S ← S ∪ {u} # Mark u as processed
For each neighbor v ∈ G.Adj[u]:
If d[u] + w(u, v) < d[v]: # Relax the edge (u, v)
d[v] = d[u] + w(u, v)
π[v] = u # Update the predecessor (optional)
DECREASE-KEY(Q, v, d[v]) # Update v's priority in Q
Flight Times and Layovers (lecture 4 exercise)
You are given:
- A list of cities and their unique identifiers.
- Flight times between pairs of cities, represented as a weighted directed graph:
- Each edge represents a flight with a time cost (in hours).
- Waiting times at each city (in hours), which must be added to the travel time whenever a flight lands there.
Goal: Write a program to calculate:
- The shortest total travel time from a given starting city to every other city.
- The path taken for the shortest travel time to each city.
Bellman–Ford algorithm
- The Bellman–Ford algorithm is an algorithm for finding the shortest path from a single source node to all other nodes in a directed weighted graph.
- It is slower than Dijkstra’s algorithm for the same problem, but more versatile, as it is capable of handling graphs in which some of the edge weights are negative numbers
- If there is a negative cycle reachable from , then there is no shortest path from to any node, and