Question

Develop an algorithm which takes node-node incidence matrix as an input and determines whether the graph is connected or not.

Answer 1

// The adjacency matrix and visited array have global declaration

void DFS(int i) {
visited[i] = true;
for (Integer n : adj[i]) {
if (!visited[n])
DFS(n);
}
}

boolean Connectivity() {
// assume you start counting with zero
DFS(0); boolean f=true;
// check each element in the visited array if any is false connectivity does not exist.
for (int j = 0; j < nodecount; ++j)
if (!visited[j]) {
flag = false;
break;
}
return flag;
}