Graph Algorithms Intro ♢ COMP2521 ♢ (23T1)

COMP2521(23T1) ♢ Graph Algorithms ♢ [0/26]
❖ Problems on Graphs

What kind of problems do we want to solve on/via graphs?

COMP2521(23T1) ♢ Graph Algorithms ♢ [1/26]
❖ Cycle Checking

A graph has a cycle if

This graph has 3 distinct cycles:  0-1-2-0,  2-3-0-2,  0-1-2-3-0

[Diagram:Pics/cycle-graph1.png]

("distinct" means the set  of vertices on the path, not the order)

COMP2521(23T1) ♢ Graph Algorithms ♢ [2/26]
❖ ... Cycle Checking

Consider this graph:

[Diagram:Pics/cycle-graph2.png]


This graph has many cycles e.g.  0-4-3-0,  2-4-5-2,  0-1-2-5-4-6-3-0,  ...

COMP2521(23T1) ♢ Graph Algorithms ♢ [3/26]
❖ ... Cycle Checking

First attempt at checking for a cycle

hasCycle(G):
|  Input  graph G
|  Output true if G has a cycle, false otherwise
|
|  choose any vertex v ∈ G
|  return dfsCycleCheck(G,v)

dfsCycleCheck(G,v):
|  mark v as visited
|  for each (v,w) ∈ edges(G) do
|  |  if w has been visited then  // found cycle
|  |     return true
|  |  else if dfsCycleCheck(G,w) then
|  |     return true
|  end for
|  return false  // no cycle at v

COMP2521(23T1) ♢ Graph Algorithms ♢ [4/26]
❖ ... Cycle Checking

The above algorithm has two bugs ...

If we start from vertex 5 in the following graph, we don't find the cycle:

[Diagram:Pics/cycle-graph3.png]

COMP2521(23T1) ♢ Graph Algorithms ♢ [5/26]
❖ ... Cycle Checking

Version of cycle checking (in C) for one connected component:

bool dfsCycleCheck(Graph g, Vertex v, Vertex u) {
   visited[v] = true;
   for (Vertex w = 0; w < g->nV; w++) {
      if (adjacent(g, v, w)) {
         if (!visited[w]) {
            if (dfsCycleCheck(g, w, v))
               return true;
         }
         else if (w != u)
            return true;
      }
   }
   return false;
}

COMP2521(23T1) ♢ Graph Algorithms ♢ [6/26]
❖ ... Cycle Checking

Wrapper to ensure that all connected components are checked:

Vertex *visited;

bool hasCycle(Graph g, Vertex s) {
   bool result = false;
   visited = calloc(g->nV,sizeof(int));
   for (int v = 0; v < g->nV; v++) {
      for (int i = 0; i < g->nV; i++)
         visited[i] = -1;
      if dfsCycleCheck(g, v, v)) {
         result = true;
         break;
      }
   }
   free(visited);
   return result;
}

COMP2521(23T1) ♢ Graph Algorithms ♢ [7/26]
❖ Connected Components

Consider these problems:

Both of the above can be solved if we can

[Diagram:Pics/components-ex.png]

COMP2521(23T1) ♢ Graph Algorithms ♢ [8/26]
❖ ... Connected Components

Algorithm to assign vertices to connected components:

components(G):
|  Input  graph G
|  Output componentOf[] filled for all V
|
|  for all vertices v ∈ G do
|  |  componentOf[v]=-1
|  end for
|  compID=0  // component ID
|  for all vertices v ∈ G do
|  |  if componentOf[v]=-1 then
|  |     dfsComponent(G,v,compID)
|  |     compID=compID+1
|  |  end if
|  end for

COMP2521(23T1) ♢ Graph Algorithms ♢ [9/26]
❖ ... Connected Components


DFS scan of one connected component

dfsComponent(G,v,id):
|  componentOf[v]=id
|  for each (v,w) ∈ edges(G) do
|     if componentOf[w]=-1 then
|        dfsComponent(G,w,id)
|     end if
|  end for

COMP2521(23T1) ♢ Graph Algorithms ♢ [10/26]
❖ ... Connected Components

Consider an application where connectivity is critical

Add a new fields to the GraphRep structure:

typedef struct GraphRep *Graph;

struct GraphRep {
   ...
   int nC;  // # connected components
   int *cc; // which component each vertex is contained in
   ...      // i.e. array [0..nV-1] of 0..nC-1
}

COMP2521(23T1) ♢ Graph Algorithms ♢ [11/26]
❖ ... Connected Components


With this structure, the above tasks become trivial:

// How many connected subgraphs are there?
int nConnected(Graph g) {
   return g->nC;
}
// Are two vertices in the same connected subgraph?
bool inSameComponent(Graph g, Vertex v, Vertex w) {
   return (g->cc[v] == g->cc[w]);
}


But ... introduces overheads ... maintaining cc[],  nC

COMP2521(23T1) ♢ Graph Algorithms ♢ [12/26]
❖ ... Connected Components


Consider maintenance of such a graph representation:

Additional cost amortised by lower cost for nConnected() and inSameComponent()

Is it simpler to run components() after each edge change?

COMP2521(23T1) ♢ Graph Algorithms ♢ [13/26]
❖ Hamiltonian Path and Circuit

Hamiltonian path problem:

If v = w, then we have a Hamiltonian circuit

Simple to state, but difficult to solve (NP-complete)

Many real-world applications require you to visit all vertices of a graph:

Named after Irish mathematician/physicist/astronomer Sir William Hamilton (1805-1865)
COMP2521(23T1) ♢ Graph Algorithms ♢ [14/26]
❖ ... Hamiltonian Path and Circuit

Graph and some possible Hamiltonian paths:

[Diagram:Pics/hamilton1.png]

COMP2521(23T1) ♢ Graph Algorithms ♢ [15/26]
❖ ... Hamiltonian Path and Circuit


Approach:

Can be expressed via a recursive DFS algorithm
COMP2521(23T1) ♢ Graph Algorithms ♢ [16/26]
❖ ... Hamiltonian Path and Circuit

Algorithm for finding Hamiltonian path:

visited[] // array [0..nV-1] to keep track of visited vertices

hasHamiltonianPath(G,src,dest):
|  Input  graph G, plus src/dest vertices
|  Output true if Hamiltonian path src...dest,
|           false otherwise
|
|  for all vertices v ∈ G do
|     visited[v]=false
|  end for
|  return hamiltonR(G,src,dest,#vertices(G)-1)

COMP2521(23T1) ♢ Graph Algorithms ♢ [17/26]
❖ ... Hamiltonian Path and Circuit

Recursive component:

hamiltonR(G,v,dest,d):
|  Input G    graph
|        v    current vertex considered
|        dest destination vertex
|        d    distance "remaining" until path found
|
|  if v=dest then
|     if d=0 then return true else return false
|  else
|  |  visited[v]=true
|  |  for each (v,w) ∈ edges(G)  where not visited[w] do
|  |     if hamiltonR(G,w,dest,d-1) then
|  |        return true
|  |     end if
|  |  end for
|  end if
|  visited[v]=false           // reset visited mark
|  return false

COMP2521(23T1) ♢ Graph Algorithms ♢ [18/26]
❖ ... Hamiltonian Path and Circuit

Analysis: worst case requires (V-1)! paths to be examined

Consider a graph with isolated vertex and the rest fully-connected

[Diagram:Pics/hamilton-worst.png]

Checking hasHamiltonianPath(g,x,0) for any x

There is no known simpler algorithm for this task ⇒ NP-hard.

Note, however, that the above case could be solved in constant time if
we had a fast check for 0 and x being in the same connected component

COMP2521(23T1) ♢ Graph Algorithms ♢ [19/26]
❖ Euler Path and Circuit

Euler path problem:

If v = w, the we have an Euler circuit

[Diagram:Pics/euler-path-tour.png]

Many real-world applications require you to visit all edges of a graph:

COMP2521(23T1) ♢ Graph Algorithms ♢ [20/26]
❖ ... Euler Path and Circuit


Problem named after Swiss mathematician, physicist, astronomer, logician and engineer Leonhard Euler (1707 - 1783)

Based on a circuitous route via bridges in Konigsberg

[Diagram:Pics/Konigsberg_bridges.png]

COMP2521(23T1) ♢ Graph Algorithms ♢ [21/26]
❖ ... Euler Path and Circuit

Is there a way to cross all the bridges of Konigsberg exactly once on a walk through the town?

[Diagram:Pics/euler-bridges.png]

COMP2521(23T1) ♢ Graph Algorithms ♢ [22/26]
❖ ... Euler Path and Circuit


One possible "brute-force" approach:

Can develop a better algorithm by exploiting:

Theorem.   A graph has an Euler circuit if and only if
   it is connected and all vertices have even degree

Theorem.   A graph has a non-circuitous Euler path if and only if
   it is connected and exactly two vertices have odd degree

COMP2521(23T1) ♢ Graph Algorithms ♢ [23/26]
❖ ... Euler Path and Circuit


Graphs with an Euler path are often called Eulerian Graphs


[Diagram:Pics/euler-graphs.png]

COMP2521(23T1) ♢ Graph Algorithms ♢ [24/26]
❖ ... Euler Path and Circuit

Assume the existence of degree(g,v)

Algorithm to check whether a graph has an Euler path:

hasEulerPath(G,src,dest):
|  Input  graph G, vertices src,dest
|  Output true if G has Euler path from src to dest
|         false otherwise
|
|  if src≠dest then
|     if degree(G,src) is even ∨ degree(G,dest) is even then
|        return false
|     end if
|  end if
|  for all vertices v ∈ G do
|     if v≠src ∧ v≠dest ∧ degree(G,v) is odd then
|        return false
|     end if
|  end for
|  return true

COMP2521(23T1) ♢ Graph Algorithms ♢ [25/26]
❖ ... Euler Path and Circuit

Analysis of hasEulerPath algorithm:

If degree requires iteration over vertices ⇒ problem tractable, even for large graphs   (unlike Hamiltonian path problem)

For the keen, a linear-time (in the number of edges, E) algorithm to compute an Euler path is described in [Sedgewick] Ch.17.7.

COMP2521(23T1) ♢ Graph Algorithms ♢ [26/26]


Produced: 12 Mar 2023