Week 07 Tutorial Answers

Graph Traversal, Graph Problems

Graph Traversal

Consider the breadth-first and depth-first traversal algorithms below and the following graph:

bfs(G, src):
    Input: graph G, vertex src
    
    create visited array, initialised to false
    create predecessor array, initialised to -1
    create queue Q
    
    mark src as visited
    enqueue src into Q
    
    while Q is not empty:
        dequeue v from Q
        
        for each neighbour w of v:
            if w has not been visited:
                mark w as visited
                set predecessor of w to v
                enqueue w into Q

dfs(G, src):
    Input: graph G, vertex src
    
    create visited array, initialised to false
    create predecessor array, initialised to -1
    create stack S
    
    push src onto S
    
    while S is not empty:
        pop v from S
        if v has been visited:
            continue
        
        mark v as visited
        
        for each neighbour w of v:
            if w has not been visited:
                set predecessor of w to v
                push w onto S

Trace the execution of the traversal algorithms, and show the state of the visited and pred arrays and the Queue (BFS) or Stack (DFS) at the end of each iteration, for each of the following function calls:

bfs(g, 0);
bfs(g, 3);
dfs(g, 0);
dfs(g, 3);

Answer:

For bfs(g, 0):

#  Printed  visited                   pred                      Queue (front at left)
            0  1  2  3  4  5  6  7    0  1  2  3  4  5  6  7
0     -     1  0  0  0  0  0  0  0    -  -  -  -  -  -  -  -    0
1     0     1  1  1  0  0  1  1  1    -  0  0  -  -  0  0  0    1  2  5  6  7
2     1     1  1  1  0  0  1  1  1    -  0  0  -  -  0  0  0    2  5  6  7
3     2     1  1  1  0  0  1  1  1    -  0  0  -  -  0  0  0    5  6  7
4     5     1  1  1  1  1  1  1  1    -  0  0  5  5  0  0  0    6  7  3  4
5     6     1  1  1  1  1  1  1  1    -  0  0  5  5  0  0  0    7  3  4
6     7     1  1  1  1  1  1  1  1    -  0  0  5  5  0  0  0    3  4
7     3     1  1  1  1  1  1  1  1    -  0  0  5  5  0  0  0    4
8     4     1  1  1  1  1  1  1  1    -  0  0  5  5  0  0  0

For bfs(g, 3):

#  Printed  visited                   pred                      Queue (front at left)
            0  1  2  3  4  5  6  7    0  1  2  3  4  5  6  7
0     -     0  0  0  1  0  0  0  0    -  -  -  -  -  -  -  -    3
1     3     0  0  0  1  1  1  0  0    -  -  -  -  3  3  -  -    4  5
2     4     0  0  0  1  1  1  1  1    -  -  -  -  3  3  4  4    5  6  7
3     5     1  0  0  1  1  1  1  1    5  -  -  -  3  3  4  4    6  7  0
4     6     1  0  0  1  1  1  1  1    5  -  -  -  3  3  4  4    7  0
5     7     1  1  0  1  1  1  1  1    5  7  -  -  3  3  4  4    0  1
6     0     1  1  1  1  1  1  1  1    5  7  0  -  3  3  4  4    1  2
7     1     1  1  1  1  1  1  1  1    5  7  0  -  3  3  4  4    2
8     2     1  1  1  1  1  1  1  1    5  7  0  -  3  3  4  4

For dfs(g, 0):

#  Printed  visited                   pred                      Stack (top at right)
            0  1  2  3  4  5  6  7    0  1  2  3  4  5  6  7
0     -     0  0  0  0  0  0  0  0    -  -  -  -  -  -  -  -    0
1     0     1  0  0  0  0  0  0  0    -  0  0  -  -  0  0  0    7  6  5  2  1
2     1     1  1  0  0  0  0  0  0    -  0  0  -  -  0  0  1    7  6  5  2  7
3     7     1  1  0  0  0  0  0  1    -  0  0  -  7  0  7  1    7  6  5  2  6  4
4     4     1  1  0  0  1  0  0  1    -  0  0  4  7  4  4  1    7  6  5  2  6  6  5  3
5     3     1  1  0  1  1  0  0  1    -  0  0  4  7  3  4  1    7  6  5  2  6  6  5  5
6     5     1  1  0  1  1  1  0  1    -  0  0  4  7  3  4  1    7  6  5  2  6  6  5
7     6     1  1  0  1  1  1  1  1    -  0  0  4  7  3  4  1    7  6  5  2  6
8     2     1  1  1  1  1  1  1  1    -  0  0  4  7  3  4  1    7  6  5

For dfs(g, 3):

#  Printed  visited                   pred                      Stack (top at right)
            0  1  2  3  4  5  6  7    0  1  2  3  4  5  6  7
0     -     0  0  0  0  0  0  0  0    -  -  -  -  -  -  -  -    3
1     3     0  0  0  1  0  0  0  0    -  -  -  -  3  3  -  -    5  4
2     4     0  0  0  1  1  0  0  0    -  -  -  -  3  4  4  4    5  7  6  5
3     5     0  0  0  1  1  1  0  0    5  -  -  -  3  4  4  4    5  7  6  0
4     0     1  0  0  1  1  1  0  0    5  0  0  -  3  4  0  0    5  7  6  7  6  2  1
5     1     1  1  0  1  1  1  0  0    5  0  0  -  3  4  0  1    5  7  6  7  6  2  7
6     7     1  1  0  1  1  1  0  1    5  0  0  -  3  4  7  1    5  7  6  7  6  2  6
7     6     1  1  0  1  1  1  1  1    5  0  0  -  3  4  7  1    5  7  6  7  6  2
8     2     1  1  1  1  1  1  1  1    5  0  0  -  3  4  7  1    5  7  6  7  6

Graph Problems

What is the difference between a connected graph and a complete graph? Give simple examples of each.

Answer:

A connected graph is a graph where all vertices are reachable from all others, while a complete graph is a graph where all vertices are directly connected (by edges) to all others.

Connected graphs have the property that there is a single connected component. Complete graphs have the property that every vertex has \( V - 1 \) incident edges, where \( V \) is the number of vertices in the graph. A graph cannot be complete if it is not connected. Some simple examples:

Graphs 1, 2 and 3 are connected. Graph 2 is also complete. Graph 4 is not connected, and therefore also not complete despite each of the individual components being complete.
Consider the following graph with multiple connected components:

And a vertex-indexed connected components array that might form part of the Graph representation structure for this graph:
```
cc[] = {0, 0, 0, 1, 1, 1, 0, 0, 0, 1}
```
1. Show how the cc[] array would change if edge \( d \) was removed
2. Show how the cc[] array would change if edge \( b \) was removed
Answer:
1. After removing \( d \), cc[] = {0, 0, 0, 1, 1, 1, 0, 0, 0, 1} (i.e., unchanged)
2. After removing \( b \), cc[] = {0, 0, 2, 1, 1, 1, 2, 0, 2, 1}
The following question is an example of how graphs can be used to solve more abstract problems.

Suppose you have \(n\) variables (\(x_1\), \(x_2\), ..., \(x_n\)), \(m\) equalities of the form \(x_i = x_j\) (where \(i \ne j\)), and \(k\) inequalities of the form \(x_i \ne x_j\) (where \(i \ne j\)). Come up with an algorithm (described in plain English or pseudocode) to determine whether this system of equations is consistent or contradictory.

For example, suppose we have three variables (\(x_1, x_2, x_3\)), the equality \(x_1 = x_2\), and the two inequalities \(x_1 \ne x_3\) and \(x_2 \ne x_3\). These equations are consistent because we can, for example, assign \(x_1 = x_2 = 1\) and \(x_3 = 2\), and all equations would be satisfied.

For example, suppose we have three variables (\(x_1, x_2, x_3\)), the two equalities \(x_1 = x_2\) and \(x_1 = x_3\), and the inequality \(x_2 \ne x_3\). These equations are contradictory because there is no way to assign values to variables such that all equations are satisfied.
Answer:
We can represent this problem using a graph where vertices represent variables, and edges represent equalities (not inequalities).

For example, suppose we have three variables \(x_1\), \(x_2\) and \(x_3\). The single equality \(x_1 = x_2\) would be represented by the graph:

Meanwhile, the equalities \(x_1 = x_2\) and \(x_1 = x_3\) would be represented by the graph:

One observation is that if there is a path between two variables, then the variables must be equal. This means that if two variables are in the same connected component, the variables must be equal. A contradiction would arise if there is an inequality \(x_i \ne x_j\), but the variables \(x_i\) and \(x_j\) are in the same connected component.

So one possible algorithm would be the following:
- Construct a graph from the variables and equalities where:
  
  Each vertex represents a variable
  
  For each equality \(x_i = x_j\), insert an edge between \(i\) and \(j\)
- Compute the connected components array
- For each inequality \(x_i \ne x_j\):
  
  If \(x_i\) and \(x_j\) are in the same connected component, then return false
- Return true
What is the difference between a Hamiltonian path/circuit and an Euler path/circuit? Identify any Hamiltonian/Euler paths/circuits in the following graphs:

Answer:

A Hamiltonian path is a path that visits each vertex in the graph exactly once. A Hamiltonian circuit is a cycle that visits each vertex exactly once. An Euler path is a path that traverses each edge in the graph exactly once. An Euler circuit is an Euler path that ends at the same vertex where it started.

Graph 1 has both Hamiltonian and Euler paths (e.g. \( [0, 1, 2] \), but cannot have circuits as there are no cycles.

Graph 2 has both Hamiltonian and Euler paths (e.g. \( [0, 1, 2] \)), and also has both Hamiltonian and Euler circuits (e.g. \( [0, 1, 2, 0] \)).

Graph 3 has neither Hamiltonian nor Euler paths, nor Hamiltonian nor Euler circuits.

Graph 4 has Hamiltonian paths (e.g. \( [0, 1, 2, 3] \)) and a Hamiltonian circuit (e.g. \( [0, 1, 2, 3, 0] \)), but it has neither an Euler path nor an Euler circuit.

Write a function to check whether a path, supplied as an array of struct edges is an Euler path. Assume the function has interface:

bool isEulerPath(Graph g, struct edge e[], int nE)

where e[] is an array of nE edges, in path order.

Answer:

// check whether a given path is a Euler path
bool isEulerPath(Graph g, struct edge e[], int nE) {
	assert(g != NULL);

	// includes all edges
	if (g->nE != nE) {
		return false;
	}

	// edges are actually in the graph
	for (int i = 0; i < nE; i++) {
		if (g->edges[e[i].v][e[i].w] == 0) {
			return false;
		}
	}

	// is actually a path
	for (int i = 0; i < nE - 1; i++) {
		if (e[i].w != e[i + 1].v) {
			return false;
		}
	}

	// includes edges exactly once
	for (int i = 0; i < nE; i++) {
		for (int j = i + 1; j < nE; j++) {
			if (e[i].v == e[j].v && e[i].w == e[j].w) return false;
			if (e[i].v == e[j].w && e[i].w == e[j].v) return false;
		}
	}
	
	return true;
}