[Algorithm] Graph Search Algorithms

Q. Using Graph Search Algorithm, what are we searching for?

A. To find out if there is a path from node A to node B / all nodes that can be reached from A

 

Cf Data Structure = Adjacency Matrix/List

 

Breadth First Search (BFS)

Description of operation

First finds the immediate neighbors of the starting point($s$). (at distance 1 from $s)
Then finds nodes at distance 2 from $s$, etc.

BFS Tree example

BFS Tree Example

 

Order of node visits: a → b, h → c, d, g → e, f

 

BFS Algorithm and Complexity ($O(m+n)$)

Purpose: Traverse the graph level-by-level from a starting node $s$, visiting all reachable nodes.

 

Data Structure: Uses a queue to process nodes in the order they are discovered.

 

Pseudocode

BFS(node s)
    Initialize d(v) = false, for all v ∈ V
    d(s) = true
    Queue q
    q.enqueue(s)

    While (!q.isEmpty())
        node u = q.dequeue()
        for (all outgoing edges from u: u → w)
            if (!d(w))
                d(w) = true
                q.enqueue(w)
            end if
        end for
    end while

• Let:
  • $n$ = number of nodes (vertices)
  • $m$ = number of edges
• Each node is visited once → $\Theta(n)$
• Each edge is explored once → $\Theta(m)$
• Total time complexity: ${\boxed{\Theta(n + m)}}$

Key Insight

• The inner `for` loop runs for all outgoing edges from `u`, i.e., degree of `u`
• Therefore, over all nodes:
  $\sum_{u \in V} \text{deg}(u) = \Theta(m)$
• Hence, edge scanning contributes $\Theta(m)$ time

 

Depth First Search (DFS)

Description of operation

Follows a path until it hits a dead-end.
Then backtracks until it finds a new path it can take.

 

DFS Tree example

DFS Tree Example

 

Order of node visits: a → b → c → d → g → f → h

 

DFS Algorithm and Complexity ($O(m+n)$)

Purpose: Traverse the graph in a depth-first manner using a stack.

 

Approach: Start from node $s$, explore as far as possible along each branch before backtracking.

 

Pseudocode

DFS(node s)
    Initialize d(v) = false, for all v ∈ V
    Stack st
    st.push(s)

    While (!st.isEmpty())
        node u = st.pop()
        if (!d(u))
            d(u) = true
            for (all outgoing edges from u: u → w)
                st.push(w)
            end for
        end if
    end while

• Let:
  • $n$ = number of nodes (vertices)
  • $m$ = number of edges
• Each node is visited once → $\Theta(n)$
• Each edge is explored once → $\Theta(m)$
• Total time complexity: ${\boxed{\Theta(n + m)}}$

 

Graph Properties and Algorithms

Bipartite Graph Determination

Q. Given an undirected connected graph G, how do you determine of G is bipartite?

 

A. Starting from any node $s$ in $G$ ⇒ perform a BFS search

 

Observation

• Not possible to have an edge between $v$ and $w$ in $G$
  (since they are more than one level apart in the BFS tree.)
• Edges in $G$ that end up with both ends in the same set ($X$ or $Y$) must have both ends at the same level in the BFS tree (e.g. between $v$ & $u$)

 

Consider a cycle with an odd number of edges

 

`FACT` If a graph G is bipartite, then it cannot contain an odd cycle.

 

Suppose we find an edge in G with both ends in the same set.
Let w be the lowest common ancestor of v and u.

[Image]

 

length of this cycle is 2 * (j-i) + 1, which is odd!

 

Solution:

Run BFS starting from any node, say $s$.

Label each node $X$ or $Y$ depending on whether they appear at an odd or even level on the BFS tree. → $\boxed{O(m+n)}$

Then, go through all edges and examine the labels at the two ends of the edge. If all edges have one end in X and the other in Y, then the graph is bipartite. Otherwise it is not bipartite. → $\boxed{O(m)}$

$\therefore \text{Overall complexity: } \boxed{O(m+n)}$

 

Connectivity in Directed Graphs

1. Weakly Connected

A directed graph is weakly connected if there is a path from any point to any other point in the graph by ignoring edge directions.

Weakly Connected

 

2. Connected

A directed graph is connected if for any pair of nodes $(v, u)$, there is either a path from $v$ to $u$, or a path from $u$ to $v$.

Connected

 

3. Strongly Connected

A directed graph is strongly connected if for any pair of nodes $(v, u)$, there is a path from $v$ to $u$, and a path from $u$ to $v$.

Strongly Connected

 

4. Unconnected

A directed graph is not connected(unconnected) if it is not connected in any of the above 3 ways.

Unconnected (Not Connected)

 

Determining Strong Connectivity

Q. How can you determine if a given graph $G$ is strongly connected?

A. Brute force approach

Run BFS or DFS from every node.
If in each search, all nodes are found then $G$ is strongly connected
⇒ Takes $\boxed {O(n^2 + nm)}$

 

Q. Can we do better?

• if $v$ and $u$ are mutually reachable, and
• $v$ and $w$ are mutually reachable, then
• $u$ and $w$ are mutually reachable.

 

If there is a path from $s$ to $A$ in $G^T$, then this path goes from $A$ to $s$ in $G$.

 

Solution

1. Use BFS or DFS to find all nodes, reachable from $s$ (an arbitrary node) in $G$.
2. If some nodes are not reachable from $s$, stop. The graph is not strongly connected.
   Otherwise, continue with step 2.
3. Create $G^T$
4. Use BFS or DFS to find all nodes reachable from $s$ in $G^T$.
5. If some nodes are not reachable from $s$, stop. The graph is not strongly connected.
   Otherwise the graph is strongly connected.
   (Since all nodes are mutually reachable through $s$)

⇒ Overall Complexity = $\boxed {O(m + n)}$

 

Topological Sort

Finding a Topological Ordering (in a DAG)

High-level Algorithm

• Find a node $v$ with no incoming edges and order it first.
• Delete $v$ from the graph($G$)
• Recursively compute the topological ordering of $G-v$ and append this order after $v$.

[Example walk-through]

[Image][Image][Image]

 

Implementation Plan

We will compute and maintain two things:

• For each node $w$, the number of incoming edges
• The set $S$ of all active nodes in $G$ with no incoming edges.

Pseudocode

TopologicalOrdering(G)
        Intialize the in-degree of all nodes to 0
    for all v in V
        for all w in Adj(v)
            increment the in-degree of w by 1
        endfor
    endfor

    create empty list S
    for all v in V
        if in-degree(v) = 0, Add v to S
    endfor

    for i = 1 to n
        remove any node v from S
        place v in position i in the topological order
        for all w in Adj(v)
            decrement the in-degree of w by 1
            if in-degree(w) = 0, Add w to S
        endfor
    endfor

$\therefore \text{Overall Complexity = } \boxed{O(m+n)}$