Tutorial

Depth-First and Breadth-First

Consider the following code and the following graph:

void graph_dfs (Graph g, vertex v,
	size_t *count, vertex pre[], vertex st[])
{
	Stack s = stack_new ();
	stack_push (s, (edge){ v, v });
	while (stack_size (s) > 0) {
		edge e = stack_pop (s);
		if (pre[e.w] != -1) continue;
		pre[e.w] = (*count)++; st[e.w] = e.v;
		printf ("%d\n", e.w);
		for (int i = 0; i < g->nV; i++) {
			if (has_edge (g, e.w, i) && pre[i] == -1)
				stack_push (s, (edge){ e.w, i });
		}
	}
}

void graph_bfs (Graph g, vertex v,
	size_t *count, vertex pre[], vertex st[])
{
	Queue s = queue_new ();
	queue_en (s, (edge){ v, v });
	while (queue_size (s) > 0) {
		edge e = queue_de (s);
		if (pre[e.w] != -1) continue;
		pre[e.w] = (*count)++; st[e.w] = e.v;
		printf ("%d\n", e.w);
		for (int i = 0; i < g->nV; i++) {
			if (has_edge (g, e.w, i) && pre[i] == -1)
				queue_en (s, (edge){ e.w, i });
		}
	}
}

Show what would be printed by these iterative DFS and BFS traversals for the following function calls:

graph_dfs (g, 0, &count, pre, st);
graph_dfs (g, 3, &count, pre, st);

graph_bfs (g, 0, &count, pre, st);
graph_bfs (g, 3, &count, pre, st);

You should also show the state of the stack or queue, and the pre and st arrays explicitly in each step. You should assume the pre and st arrays have already been initialised to -1 for all values.

Using the relevant information from your DFS and/or BFS search, what is the shortest unweighted (least hops) path from $3$ to $2$ ?

A Relaxing Time

Consider the following code for Dijkstra’s algorithm:

void dijkstra(Graph g,Vertex s)
{
	int v,t;
	PriQ pq = initPriQ(g->nV);
	//insert each vertex into the pq
	for(v=0;v< g->nV;v++){
		insert(pq,newItem(dist[v],v));
	}
	dist[s] = 0.0; //set start veretex dist to 0
	increasePriority(pq,s,dist[s]); // update pq
	while(!isEmpty(pq)){
		v = value(delMin(pq));
		if(dist[v] != NO_EDGE){
			for(t = 0;t < g->nV;t++){
				if(g->adj[v][t] != NO_EDGE){
					if(dist[v] + g->adj[v][t] < dist[t]){
						dist[t] = dist[v] + g->adj[v][t];
						increasePriority(pq,t,dist[t]);
						st[t] = v;
					}
				}
			}
		}
	}
}

What does the increasePriority function do?

Trace through Dijkstra’s algorithm. At each step show the state of the priority Queue and the dist and st arrays. What is the shortest path from 3 to 1? And what is its cost? Assume the dist array is initialised with the value NO_EDGE (a float representation of infinity) and the st array with -1s.

Throw a Spanning-Tree in the works

What is a spanning tree? What is a minimum spanning tree?

Provide examples of applications for minimum spanning tree algorithms. For each example, discuss what the vertices, edges and weights represent.

The following code gives a reasonably detailed view of Kruskal’s algorithm for finding a minimum spanning tree.

typedef Graph MSTree;

MSTree graph_mst_kruskal (Graph g)
{
	MSTree mst = graph_new (); // MST initially empty
	size_t nE;
	edge *elist = graph_edge_list (g, &nE);
	sort_edge_list (nE, elist);

	size_t nV = graph_num_vertices (g);
	for (size_t i = 0; graph_num_edges (mst) < nV - 1; i++) {
		edge e = eList[i];
		graph_edge_add (mst, e);
		if (graph_has_cycle_p (mst))
			graph_edge_remove (mst, e);
	}

	free (elist);
	return mst;
}

This algorithm effectively constructs the MST by gradually joining together the connected graphs in a forest that starts with each subgraph being a single node. On each iteration, it add a new edge to the forest, and reduces the number of subgraphs by one.

Show how Kruskal’s algorithm would construct the MST for the graph below. How many edges did we have to consider?

For a graph $G$ with $V$ vertices and $E$ edges, what is the least number of edges we might need to consider? What is the most number of edges we might have to consider?

Add another edge to the above graph to force Kruskal’s algorithm to the worst case.

The following code is an implementation of Prim’s algorithm for finding a minimum spanning tree.

void prim(Graph g){
    vertex v, i;
    PriQ pq = initPriQ(g->nV);
    int * visited = malloc(sizeof(int)*g->nV);
    for(v=0;v < g->nV;v++){
        insert(pq,newItem(dist[v],v));
    }

    st[0] = 0;
    dist[0] = 0;
    increasePriority(pq,0,0);
    while(!isEmpty(pq)){
        v = (delMin(pq))->value;
        visited[v] = 1;
        for(i=0;i<g->nV;i++){
            if(g->adj[v][i] != NO_EDGE && visited[i] == -1){
                if(g->adj[v][i] < dist[i]){
                       dist[i] = g->adj[v][i];
                       increasePriority(pq,i,dist[i]);
                       st[i] = v;
                }
            }
        }
    }
}

Trace the execution of Prim’s algorithm on the same graph you traced through Kruskal’s on.

Show the state of the Priority Queue, the dist, st and visited arrays.

Assume the dist array is initialised with the value NO_EDGE (a float representation of infinity) and the st and visited array with -1s.

Graphs

For each of the following graphs:

Show the concrete data structures if the graph was implemented via:

adjacency matrix representation (assume full $V\times V$ matrix)
adjacency list representation (if non-directional, include both $(v,w)$ and $(w,v)$ )

Ivy League

Consider the following map of streets in the Sydney CBD:

Represent this as a directed graph, where intersections are vertices and the connecting streets are edges. Ensure that the directions on the edges correctly reflect any one-way streets (this is a driving map, not a walking map).

You only need to make a graph which includes the intersections marked with red letters

Some things that don’t show on the map: Castlereagh St is one-way heading south and Hunter St is one-way heading west.

For each of the following pairs of intersections, indicate whether there is a path from the first to the second. If there is a path, enumerate it as a set of vertices. If there is more than one path, show two different paths.

from intersection “D” on Margaret St to insersection “L” on Pitt St
from intersection “J” to the corner of Margaret St and York St (intersection “A”)
from the intersection of Margaret St and York St (“A”) to the intersection of Hunter St and Castlereagh St (“M”)
from intersection “M” on Castlereagh St to intersection “H” on York St

Paths and Tours

What is the difference between a Euler path/tour and a Hamilton path/tour? Identify any Euler/Hamilton paths/tours in the following graphs:

Write a function to check whether a path, supplied as an array of edges, is an Euler path.

Assume the function has interface:

bool euler_path_p (Graph g, edge es[], size_t nE);

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

In Russia, Graph Traverses You!

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.

Can you draw a path which crosses each bridge exactly once?
If not, which bridge would you need to remove* to ensure that you could draw such a path?
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.)

Problems of High-Power Executives

Your boss asks you to write a program to find a path in a graph that visits every vertex at least once. Your boss tells you that you may go to lunch after you have run your program on a graph with 100 vertices. Will you ever get to have your lunch?

Your boss asks you write a program to verify whether a given path visits every vertex in a given graph exactly once. Your boss tells you that you may go to lunch after you have run your program on a graph with 100 vertices. Will you ever get to have your lunch?