Tutorial Week 06

Exercise 1

In the 18th Century, the Prussian town of Konigsberg (now Kaliningrad) was famous for the seven bridges connecting its two central islands with the banks of the River Pregel, as shown in the diagram.

1. Can you draw a path which crosses each bridge exactly once?
2. If not, which bridge would you need to remove* to ensure that you could draw such a path?
3. For each case, show the path.

(* Possible methods of "removal" include: blowing up, weighing down with love-locks until it collapses, blocking permanently with Sydney Buses, etc.)

Exercise 2

Graph Search - Comparing DFS and BFS

Show what would be printed by the iterative depth-first and breadth-first traversals in the functions below on the following graph:

When choosing which neighbour to visit next, always choose the smallest unvisited neighbour. Show the state of the Stack (DFS) or Queue (BFS) explicitly in each step.

Exercise 3

In what order would you visit the nodes if you started at vertex 0 and used the cheapest least visited approach from assn2 and you had stamina of 100000? (Show the first 10 vertices you would visit in the order you would travel to them).

Exercise 4

Directed Graph - DFS and BFS

Directed Graph - DFS

What order would the nodes be visited while performing a depth first search starting at node d. What about if we started at node g?

Directed Graph BFS

What order would the nodes be visited while performing a breadth first search starting at node d. What about if we started at node g?

Exercise 5: Additional questions - Do at home

Adjcency Matrix The standard adjacency matrix representation for a graph uses a full V×V matrix and stores each edge twice (at [v,w] and [w,v]). This consumes a lot of space, and wastes a lot of space when the graph is sparse. One simple way to improve the space usage would be to define the matrix elements as bool rather than int, e.g.

int **edges; // matrix of booleans (0 or 1)
... becomes ...
bool **edges; // matrix of booleans (0 or 1)
... where bool is defined as ... 
typedef unsigned char bool;

We could use even less space by storing just the upper (or lower) triangular part of the matrix, as shown in the diagram below:

The V×V matrix has been replaced by a single array containing just the "useful" parts of the matrix. This gives a new Graph representation:

// Upper-triangluar adjacency matrix graph representation

struct graphRep {
    int   nV;     // #vertices
    int   nE;     // #edges
    bool *edges;  // array of booleans (0 or 1)
};

Accessing the elements is no longer as simple as edges[v][w]. Write a function that takes two vertices from an edge and determines the corresponding index in the edges array which holds the boolean value for this edge. Use the following function template:

int indexOf(Vertex v, Vertex w)
{
    assert(v != w); // no self-edges
    if (v > w) { Vertex tmp = v; v = w; v = tmp; }
    ...
}

The standard implementation of the adjacency list representation for graphs stores each edge twice. The edge (v,w) appears as a w stored in the adjacency list for v and as a v stored in the adjacency list for w. A more storage efficient representation (analgous to storing just the top-right half of the adjacency matrix), would be store information for each edge just once.

Re-implement the following functions from lectures to use this each-edge-stored-once variation of adjacency lists:

void insertE(Graph g, Edge e);
void removeE(Graph g, Edge e);
int neighbours(Graph g, Vertex x, Vertex y);

You should not assume that supplied Edge values will necessarily satisfy (e.v < e.w). Assume the code for adjacency List given to you in the lectures and that functions insertVList, deleteVList, searchVList to add,delete and add an edge to a list exist.