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)

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:
    1. Find the connected components that contain the node using BFS or DFS.
    2. Find a node (if any) in the graph that is not in any connected component found in step 1.
    3. 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) (or DFS(s)) on , we can find the set of all nodes reachable from in .
    • By running BFS(s) (or DFS(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.

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
  • 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’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.
  • 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:

  1. A list of cities and their unique identifiers.
  2. Flight times between pairs of cities, represented as a weighted directed graph:
    • Each edge represents a flight with a time cost (in hours).
  3. 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:

  1. The shortest total travel time from a given starting city to every other city.
  2. 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