COMP2521

24T3

Cycle
Checking COMP2521 24T3
Connected
Components
Graphs (III)
Hamiltonian
Graph Problems
Path/Circuit

Eulerian
Path/Circuit
Hao Xue
Other
Problems [email protected]

cycle checking
connected components
hamiltonian paths/circuits
eulerian paths/circuits
 COMP2521
24T3 Graph Problems
Cycle
Checking

Connected
Components

Hamiltonian
Path/Circuit

Eulerian
Path/Circuit Basic graph problems:
Other • Is there a cycle in the graph?
Problems
• How many connected components are there in the graph?
• Is there a path that passes through all vertices?
• Is there a path that passes through all edges?
 COMP2521
24T3 Cycle Checking
Cycle
Checking

A cycle is a path of length > 2

Attempt 1
Attempt 2

where the start vertex = end vertex

Solution
Analysis

Connected and no edge is used more than once

Components

Hamiltonian
Path/Circuit 1 3
Eulerian
0
Path/Circuit

Other
2
Problems
4
5 6

This graph has three distinct cycles:

1-2-5-1, 2-5-6-2, 1-2-6-5-1

(two cycles are distinct if they have different sets of edges)

 COMP2521
24T3 Cycle Checking
Attempt 1
Cycle
Checking
Attempt 1
Attempt 2 How to check if a graph has a cycle?
Solution
Analysis

Connected Idea:
Components
• Perform a DFS, starting from any vertex
Hamiltonian
Path/Circuit • During the DFS, if the current vertex has an edge to an already-visited
Eulerian
Path/Circuit vertex, then there is a cycle
Other
Problems

1 3
0
2
4
5 6
tests/cycle1.txt
 COMP2521
24T3 Cycle Checking
Attempt 1
Cycle
Checking
Attempt 1
Attempt 2
Solution
hasCycle(G):
Analysis Input: graph G
Connected Output: true if G has a cycle, false otherwise
Components

Hamiltonian pick any vertex v in G

Path/Circuit
create visited array, initialised to false
Eulerian
Path/Circuit return dfsHasCycle(G, v, visited)
Other
Problems dfsHasCycle(G, v, visited):
visited[v] = true

for each neighbour w of v in G:

if visited[w] = true:
return true
else if dfsHasCycle(G, w, visited):
return true

return false
 COMP2521
24T3 Cycle Checking
Attempt 1
Cycle
Checking
Attempt 1
Attempt 2
Solution
Problem:
Analysis
• The algorithm does not check whether the neighbour w is the vertex that
Connected
Components it just came from
Hamiltonian
Path/Circuit
• Therefore, it considers moving back and forth along a single edge to be a
Eulerian cycle (e.g., 0-1-0)
Path/Circuit

Other
Problems
1 3
0
2
4
5 6
tests/cycle2.txt
 COMP2521
24T3 Cycle Checking
Attempt 2
Cycle
Checking
Attempt 1
Attempt 2
Solution
Analysis

Connected
Components

Hamiltonian
Path/Circuit Improved idea:
Eulerian • Perform a DFS, starting from any vertex
Path/Circuit

Other • Keep track of previous vertex during DFS

Problems
• During the DFS, if the current vertex has an edge to an already-visited
vertex which is not the previous vertex, then there is a cycle
 COMP2521
24T3 Cycle Checking
Attempt 2
Cycle
Checking
Attempt 1 hasCycle(G):
Input: graph G
Attempt 2
Solution
Analysis
Output: true if G has a cycle, false otherwise
Connected
Components
pick any vertex v in G
Hamiltonian
Path/Circuit create visited array, initialised to false
Eulerian
return dfsHasCycle(G, v, v, visited)
Path/Circuit

Other dfsHasCycle(G, v, prev, visited):

Problems visited[v] = true

for each neighbour w of v in G:

if w = prev:
continue
if visited[w] = true:
return true
else if dfsHasCycle(G, w, v, visited):
return true

return false
 COMP2521
24T3 Cycle Checking
Attempt 2
Cycle
Checking
Attempt 1
Attempt 2
Solution
Analysis Problem:
Connected
Components
• The algorithm only checks one connected component
Hamiltonian • The connected component that the initially chosen vertex belongs to
Path/Circuit

Eulerian
Path/Circuit

Other 1 3
Problems 0
2
4
5 6
tests/cycle3.txt
 COMP2521
24T3 Cycle Checking
Working Solution
Cycle
Checking
Attempt 1
Attempt 2
Solution
Analysis

Connected
Components Working idea:
Hamiltonian
Path/Circuit
• Perform a DFS, starting from any vertex
Eulerian • Keep track of previous vertex during DFS
Path/Circuit

Other
• During the DFS, if the current vertex has an edge to an already-visited
Problems
vertex which is not the previous vertex, then there is a cycle
• After the DFS, if any vertex has not yet been visited, perform another
DFS, this time starting from that vertex
• Repeat until all vertices have been visited
 COMP2521
24T3 Cycle Checking
Working Solution
Cycle
Checking hasCycle(G):
Attempt 1
Attempt 2
Input: graph G
Solution Output: true if G has a cycle, false otherwise
Analysis

Connected create visited array, initialised to false

Components

Hamiltonian for each vertex v in G:

Path/Circuit if visited[v] = false:
Eulerian if dfsHasCycle(G, v, v, visited):
Path/Circuit return true
Other
Problems return false

dfsHasCycle(G, v, prev, visited):

visited[v] = true

for each neighbour w of v in G:

if w = prev:
continue
if visited[w] = true:
return true
else if dfsHasCycle(G, w, v, visited):
return true

return false
 COMP2521
24T3 Cycle Checking
Analysis
Cycle
Checking
Attempt 1
Attempt 2
Solution
Analysis

Connected
Components

Hamiltonian
Path/Circuit
Analysis for adjacency list representation:
Eulerian
Path/Circuit • Algorithm is a slight modification of DFS
Other
Problems
• A full DFS traversal is O(V + E)
• Thus, worst-case time complexity of cycle checking is O(V + E)
 COMP2521
24T3 Connected Components
Cycle
Checking

Connected
Components

Hamiltonian
Path/Circuit
A connected component
Eulerian is a maximally connected subgraph
Path/Circuit

Other
Problems
For example, this graph has three connected components:

1 3
0 7
2
4
5 8
6
 COMP2521
24T3 Connected Components
Cycle
Checking

Connected
Components

Hamiltonian
Path/Circuit
Definitions:
Eulerian
Path/Circuit subgraph
Other
Problems
a subset of vertices and edges of original graph

connected subgraph
there is a path between every pair of vertices in the subgraph

maximally connected subgraph

no way to include more edges/vertices from original graph into the subgraph
such that subgraph is still connected
 COMP2521
24T3 Connected Components
Cycle
Checking

Connected
Components

Hamiltonian
Path/Circuit

Eulerian
Path/Circuit

Other
Problems:
Problems

How many connected components are there?

Are two vertices in the same connected component?

 COMP2521
24T3 Connected Components
Cycle
Checking Goal:
Connected
Components
• Compute an array which indicates which connected component each
Hamiltonian vertex is in
Path/Circuit
• Let this array be called componentOf
Eulerian
Path/Circuit
• componentOf[v] contains the component number of vertex v
Other • For example:
Problems

1 3
0 7
2
4
5 8
6

[0] [1] [2] [3] [4] [5] [6] [7] [8]

0 0 1 1 0 1 1 2 2
 COMP2521
24T3 Connected Components
Cycle
Checking

Connected
Components

Hamiltonian
Path/Circuit
Idea:
Eulerian
Path/Circuit • Choose a vertex and perform a DFS starting at that vertex
Other • During the DFS, assign all vertices visited to component 0
Problems
• After the DFS, if any vertex has not been assigned a component,
perform a DFS starting at that vertex
• During this DFS, assign all vertices visited to component 1
• Repeat until all vertices are assigned a component, increasing the
component number each time
 COMP2521
24T3 Connected Components
Cycle
Checking
components(G):
Connected
Components
Input: graph G
Output: componentOf array
Hamiltonian
Path/Circuit

Eulerian create componentOf array, initialised to -1

Path/Circuit

Other compNo = 0
Problems
for each vertex v in G:
if componentOf[v] = -1:
dfsComponents(G, v, componentOf, compNo)
compNo = compNo + 1

return componentOf

dfsComponents(G, v, componentOf, compNo):

componentOf[v] = compNo
for each neighbour w of v in G:
if componentOf[w] = -1:
dfsComponents(G, w, componentOf, compNo)
 COMP2521
24T3 Connected Components
Analysis
Cycle
Checking

Connected
Components

Hamiltonian
Path/Circuit

Eulerian
Path/Circuit

Other
Problems
Analysis for adjacency list representation:
• Algorithm performs a full DFS, which is O(V + E)
 COMP2521
24T3 Connected Components
Cycle
Checking

Connected
Components

Hamiltonian
Path/Circuit

Eulerian
Path/Circuit Suppose we frequently need to answer the following questions:
Other
Problems
• How many connected components are there?
• Are v and w in the same connected component?
• Is there a path between v and w?
Note: The last two questions are actually equivalent in an undirected graph.
 COMP2521
24T3 Connected Components
Cycle
Checking

Connected
Components

Hamiltonian
Path/Circuit
Solution:
Eulerian
Path/Circuit • Cache the components array in the graph struct
Other
Problems
struct graph {
...
int nC; // number of connected components
int *cc; // componentOf array
};
 COMP2521
24T3 Connected Components
Cycle
Checking

Connected This allows us to answer the questions very easily:

Components

Hamiltonian // How many connected components are there?

Path/Circuit
int numComponents(Graph g) {
Eulerian
Path/Circuit
return g->nC;
Other
}
Problems

// Are v and w in the same connected component?

bool inSameComponent(Graph g, Vertex v, Vertex w) {
return g->cc[v] == g->cc[w];
}

// Is there a path between v and w?

bool hasPath(Graph g, Vertex v, Vertex w) {
return g->cc[v] == g->cc[w];
}
 COMP2521
24T3 Connected Components
Cycle
Checking

Connected
Components

Hamiltonian
Path/Circuit

Eulerian
Path/Circuit
However, this information needs to be maintained as the graph changes:
Other • Inserting an edge may reduce nC
Problems
• If the endpoint vertices were in different components
• Removing an edge may increase nC
• If the endpoint vertices were in the same component and there is no other
path between them
 COMP2521
24T3 Hamiltonian Path and Circuit
Cycle
Checking

Connected
Components

Hamiltonian
Path/Circuit

Eulerian
Path/Circuit
A Hamiltonian path is
Other
a path that includes each vertex exactly once
Problems

A Hamiltonian circuit (or Hamiltonian cycle) is

a cycle that includes each vertex exactly once
(a cycle that visits each vertex of a graph exactly once and returns to the
starting vertex)
 COMP2521
24T3 Hamiltonian Path and Circuit
Cycle
Checking

Connected
Components

Hamiltonian
Path/Circuit

Eulerian
Path/Circuit

Other
Problems Graph needs to be connected (as expected)
If multiple components, then it’s not possible
 COMP2521
24T3 Hamiltonian Path and Circuit
Cycle
Checking

Connected
Named after
Components Irish mathematician, astronomer and physicist
Hamiltonian
Path/Circuit
Sir William Rowan Hamilton (1805-1865)
Eulerian
Path/Circuit

Other
Problems
 COMP2521
24T3 Hamiltonian Path and Circuit
Cycle
Checking
Consider the following graph:
Connected
Components

Hamiltonian 1 3
Path/Circuit

Eulerian
Path/Circuit

Other
2
Problems
0 4

1 3 1 3

2 2
0 4 0 4
Hamiltonian path pHamiltonian circuit p
 COMP2521
24T3 Hamiltonian Path
Cycle
Checking

Connected
Components

Hamiltonian
Path/Circuit How to check if a graph has a Hamiltonian path?
Eulerian
Path/Circuit

Other
Idea:
Problems
• Brute force
• Use DFS to check all possible paths
• Recursive DFS is perfect, as it naturally allows backtracking
• Keep track of the number of vertices left to visit
• Stop when this number reaches 0
 COMP2521
24T3 Hamiltonian Path
Cycle
Checking

Connected
Components

Hamiltonian
Path/Circuit hasHamiltonianPath(G):
Eulerian Input: graph G
Path/Circuit
Output: true if G has a Hamiltonian path
Other
Problems
false otherwise

create visited array, initialised to false

for each vertex v in G:
if dfsHamiltonianPath(G, v, visited, #vertices(G)):
return true

return false
 COMP2521
24T3 Hamiltonian Path
Cycle
Checking

Connected
Components

Hamiltonian
dfsHamiltonianPath(G, v, visited, numVerticesLeft):
Path/Circuit visited[v] = true
Eulerian numVerticesLeft = numVerticesLeft - 1
Path/Circuit

Other if numVerticesLeft = 0:
Problems
return true

for each neighbour w of v in G:

if visited[w] = false:
if dfsHamiltonianPath(G, w, visited, numVerticesLeft):
return true

visited[v] = false
return false
 COMP2521
24T3 Hamiltonian Path
Cycle
Checking

Connected
Components

Hamiltonian
Why set visited[v] to false at the end of dfsHamiltonianPath?
Path/Circuit

Eulerian
Path/Circuit 2
Other
Problems 4
1
3
0

allow the algorithm to explore other potential paths

 COMP2521
24T3 Hamiltonian Circuit
Cycle
Checking

Connected
Components

Hamiltonian
Path/Circuit

Eulerian
Path/Circuit How to check if a graph has a Hamiltonian circuit?
Other
Problems
• Similar approach as Hamiltonian path
• Don’t need to try all starting vertices
• After a Hamiltonian path is found, check if the final vertex is adjacent to
the starting vertex
 COMP2521
24T3 Hamiltonian Circuit
Cycle hasHamiltonianCircuit(G):
Checking Input: graph G
Connected Output: true if G has a Hamiltonian circuit
Components false otherwise
Hamiltonian
Path/Circuit if #vertices(G) < 3:
Eulerian return false
Path/Circuit

Other create visited array, initialised to false

Problems return dfsHamiltonianCircuit(G, 0, visited, #vertices(G))

dfsHamiltonianCircuit(G, v, visited, numVerticesLeft):

visited[v] = true
numVerticesLeft = numVerticesLeft - 1

if numVerticesLeft = 0 and adjacent(G, v, 0):

return true

for each neighbour w of v in G:

if visited[w] = false:
if dfsHamiltonianCircuit(G, w, visited, numVerticesLeft):
return true

visited[v] = false
return false
 COMP2521
24T3 Hamiltonian Path and Circuit
Analysis
Cycle
Checking

Connected
Components

Hamiltonian
Path/Circuit

Eulerian Analysis:
Path/Circuit

Other • Worst-case time complexity: O(V !)

Problems
• There are at most V ! paths to check (all possible permutations of the V
vertices)
• There is no known polynomial time algorithm, so the Hamiltonian path
problem is NP-hard (Non-deterministic Polynomial-time Hard)
• no easy way
 COMP2521
24T3 Eulerian Path and Circuit
Cycle
Checking

Connected
Components An Eulerian path is
Hamiltonian a path that visits each edge exactly once
Path/Circuit

Eulerian
Path/Circuit An Eulerian circuit is
Other an Eulerian path that starts and ends at the same vertex
Problems

0 1 0 1

2 3 2 3
4 4
Eulerian path: Eulerian circuit:
4-2-0-1-3-0 4-2-0-1-3-4
 COMP2521
24T3 Eulerian Path and Circuit
Cycle
Checking

Connected
Components

Hamiltonian
Path/Circuit

Eulerian
Path/Circuit

Other
Problems One-stroke problem: whether it is possible to draw a graph or figure in a
single stroke without lifting the pen and without retracing any edge.
 COMP2521
24T3 Eulerian Path and Circuit
Background
Cycle
Checking

Connected
Components Problem is named after
Hamiltonian Swiss mathematician, physicist, astronomer, logician and engineer
Path/Circuit
Leonhard Euler (1707-1783)
Eulerian
Path/Circuit

Other
Problems
 COMP2521
24T3 Eulerian Path and Circuit
Background
Cycle
Checking

Connected
Components

Hamiltonian Problem was introduced by Euler while trying to solve the

Path/Circuit
Seven Bridges of Konigsberg problem in 1736.
Eulerian
Path/Circuit

Other
Problems

Is there a way to cross all the bridges exactly once on a walk through the
town?
 COMP2521
24T3 Eulerian Path and Circuit
Background
Cycle
Checking

Connected
Components This is a graph problem:
Hamiltonian vertices represent pieces of land
Path/Circuit
edges represent bridges
Eulerian
Path/Circuit

Other
Problems
 COMP2521
24T3 Eulerian Path and Circuit
Cycle
Checking

Connected
Components
How to check if a graph has an Eulerian path or circuit?
Hamiltonian
Path/Circuit

Eulerian
Can use the following theorems:
Path/Circuit

Other
Problems
A graph has an Eulerian path if and only if
exactly zero or two vertices have odd degree,
and all vertices with non-zero degree belong to the same connected
component

A graph has an Eulerian circuit if and only if

every vertex has even degree,
and all vertices with non-zero degree belong to the same connected
component
 COMP2521
24T3 Eulerian Path and Circuit
Cycle
Checking

Connected
Components

Hamiltonian
Which of these graphs have an Eulerian path? How about an Eulerian circuit?
Path/Circuit

Eulerian
Path/Circuit
6
Other
Problems
4
4 5
2
2 3
0 1 2 3
0 1
0 1
 COMP2521
24T3 Eulerian Path and Circuit
Cycle
Checking

Connected
Components

Hamiltonian
Path/Circuit
Why
Eulerian “all vertices with non-zero degree belong to the same connected
Path/Circuit
component”?
Other
Problems

0 1

2 3
4
 COMP2521
24T3 Eulerian Path
Cycle
Checking

Connected
Components

Hamiltonian
Path/Circuit hasEulerianPath(G):
Eulerian
Input: graph G
Path/Circuit Output: true if G has an Eulerian path
Other false otherwise
Problems

numOddDegree = 0
for each vertex v in G:
if degree(G, v) is odd:
numOddDegree = numOddDegree + 1

return (numOddDegree = 0 or numOddDegree = 2) and

eulerConnected(G)
 COMP2521
24T3 Eulerian Path
Cycle
Checking

Connected eulerConnected(G):
Components Input: graph G
Hamiltonian Output: true if all vertices in G with non-zero degree
Path/Circuit
belong to the same connected component
Eulerian
Path/Circuit
false otherwise
Other
Problems create visited array, initialised to false

for each vertex v in G:

if degree(G, v) > 0:
dfsRec(G, v, visited)
break

for each vertex v in G:

if degree(G, v) > 0 and visited[v] = false:
return false

return true
 COMP2521
24T3 Eulerian Circuit
Cycle
Checking

Connected
Components

Hamiltonian
Path/Circuit
hasEulerianCircuit(G):
Eulerian
Path/Circuit Input: graph G
Other
Output: true if G has an Eulerian circuit
Problems false otherwise

for each vertex v in G:

if degree(G, v) is odd:
return false

return eulerConnected(G)
 COMP2521
24T3 Eulerian Path and Circuit
Analysis
Cycle
Checking

Connected
Components

Hamiltonian
Path/Circuit

Eulerian
Path/Circuit
Analysis for adjacency list representation:
Other • Finding degree of every vertex is O(V + E)
Problems
• Checking connectivity requires a DFS which is O(V + E)
• Therefore, worst-case time complexity is O(V + E)

So unlike the Hamiltonian path problem, the Eulerian path problem can be
solved in polynomial time.
 COMP2521
24T3 Other Graph Problems
Tractable and Intractable
Cycle
Checking

Connected
Components

Hamiltonian
Path/Circuit

Eulerian
Path/Circuit
Many graph problems are intractable – that is,
Other
Problems there is no known “efficient” algorithm to solve them.

In this context, “efficient” usually means polynomial time.

A tractable problem is one that is known to have a

polynomial-time solution.
 COMP2521
24T3 Other Graph Problems
Tractable and Intractable
Cycle
Checking

Connected
Components

Hamiltonian
Path/Circuit tractable intractable
Eulerian
Path/Circuit what is the shortest path
how about the longest path?
Other
Problems
between two vertices?
 COMP2521
24T3 Other Graph Problems
Tractable and Intractable
Cycle
Checking

Connected
Components

Hamiltonian
Path/Circuit tractable intractable
Eulerian
Path/Circuit what is the shortest path
how about the longest path?
Other
Problems
between two vertices?

does a graph contain a clique? what is the largest clique?

 COMP2521
24T3 Other Graph Problems
Tractable and Intractable
Cycle
Checking

Connected
Components

Hamiltonian
Path/Circuit tractable intractable
Eulerian
Path/Circuit what is the shortest path
how about the longest path?
Other
Problems
between two vertices?

does a graph contain a clique? what is the largest clique?

given two colors, is it possible to

colour every vertex in a graph such
what about three colours?
that no two adjacent vertices are the
same colour?
 COMP2521
24T3 Other Graph Problems
Tractable and Intractable
Cycle
Checking

Connected
Components

Hamiltonian
Path/Circuit tractable intractable
Eulerian
Path/Circuit what is the shortest path
how about the longest path?
Other
Problems
between two vertices?

does a graph contain a clique? what is the largest clique?

given two colors, is it possible to

colour every vertex in a graph such
what about three colours?
that no two adjacent vertices are the
same colour?

does a graph contain an Eulerian path? how about a Hamiltonian path?

 COMP2521
24T3 Other Graph Problems
Bonus Round!
Cycle
Checking

Connected
Components

Hamiltonian
a e 1 2
Path/Circuit

Eulerian
Path/Circuit

Other
b f 5 6
Problems

c g 8 7

d h 4 3

Graph isomorphism:
Can we make two given graphs identical by renaming vertices?
 COMP2521
24T3 Feedback
Cycle
Checking

Connected
Components https://forms.office.com/r/zEqxUXvmLR
Hamiltonian
Path/Circuit

Eulerian
Path/Circuit

Other
Problems