---

CIS 3223 Lab08 – Implementing Depth-First Graph (DFG) Search

DUE: (before the next lab, 10:30am Friday, March 28, 2008)

---

Depth-First Approach for Discovery of Reachable Graph Nodes

The pseudo-code of the algorithm is given in 3.2 Section of the Dasgupta textbook.

TASKS

1. Your goal is to implement in Matlab a DFG algorithm that, given a graph and a node, finds all nodes reachable from the node. We will consider the undirected graphs. The function definition is:

function visited = dfs(G, index)

You should assume:

G to be the adjacency matrix of dimension N*N, where N is the number of graph nodes.

index to be an index of the node

visited to be an array of size N*1 with value 1 if the node is reachable from index node

2. Evaluate the DFS function

2.a. Use graph from figure 3.2 in the textbook. Its edges are

E = {(A,B), (A,C), (A,D), (B,F), (B,E), (C,F), (D,G), (D,H), (E,I), (E,J), (G,H), (I,J), (K,L)}.

Use DFS function to check what nodes are reachable from node A, and what nodes are reachable from node K.

2.b. Generate graphs G of size N = {5, 10, 20, 50, 100, 200, 500, 1000} and with alpha = {0, 0.1, 0.2} using the following code:

tmp = rand(N);

tmp = (tmp + transpose(tmp))/2;

G = round(tmp - alpha);

Note that alpha determines how many edges there are in the graph. Write the code that checks how many edges there are in graph G. Run DFS 10 times for each possible combination of N and alpha, and for index = 1. For each run, save the total number of edges, number of reachable nodes, and time needed to run the DFS. Analyze the results and explore if the runtime confirms the theoretical result O(|V| + |E|).