Week 07 Tutorial Questions

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);

Graph Problems

What is the difference between a connected graph and a complete graph? Give simple examples of each.
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
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..
What is the difference between a Hamiltonian path/circuit and an Euler path/circuit? Identify any Hamiltonian/Euler paths/circuits in the following graphs:
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.