BFS help

[a00706089]

Hey everyone,

I am able to create an adjacency matrix that represents a directed graph. My program uses a 2D array to do so and an example looks like this.

0 1 0 0
0 0 1 0
0 0 0 1
0 0 0 0

My question now is how do I know if the graph has a cycle?

-I have read that I'm to do a modified BFS.

This is the code I have create so far, but I have hit a wall and need some serious help =P Any input would be much appreciated!

code:

enum VertexState {           White, Gray, Black       }          public void DFS()       {             VertexState state[] = new VertexState[numberOfVertices];             for (int i = 0; i < numberOfVertices; i++)             {                   state[i] = VertexState.White;             }             runDFS(0, state);       }             public void runDFS(int u, VertexState[] state)       {             state[u] = VertexState.Gray;             for (int v = 0; v < numberOfVertices; v++)                   if (isEdge(u, v) && state[v] == VertexState.White)                   {                         runDFS(v, state);                   }                        state[u] = VertexState.Black;       }

[Analysis Mode]

I would use DFS. Start at every vertex and see if you can come back to the starting vertex. Don't go to the same vertex more than once (i.e. don't traverse an edge more than once). As long as the adjacency matrix is not too big, this'll be fine.

[bbi5291]

Analysis Mode @ Thu Mar 26, 2009 12:53 pm wrote:

... see if you can come back to the starting vertex. Don't go to the same vertex more than once...

What? You've just contradicted yourself.

[A.J]

Ok, there are either 3 things that could happen :
1). All the states are cycled through, and the initial vertex is eventually reached.
2). There's a cycle that doesn't include the initial vertex (i.e.1 -> 2 -> 3 -> 2 -> 3...).
3). You reach a vertex that doesn't lead to anywhere.

Wait, are your edges traversable (a word I invented ) in both directions?

[a00706089]

Quote:

Wait, are your edges traversable (a word I invented Laughing) in both directions?

It's a directed graph, so only one way.

[A.J]

k, then there are only 3 possibilities, the ones I stated

[Zeroth]

Basically, if you use DFS, and keep track of all visited nodes, and then run into a node you've already visited, you've found a cycle. Same thing happens if you use BFS, and run into a node you've already visited.

[Vermette]

Zeroth @ March 26th 2009, 23:35 wrote:

Basically, if you use DFS, and keep track of all visited nodes, and then run into a node you've already visited, you've found a cycle. Same thing happens if you use BFS, and run into a node you've already visited.

With the caveat that with BFS the first cycle you find is guaranteed to be the shortest. With DFS it's a crapshoot.

[DanielG]

bfs doesn't work for this, since just because you can reach some point in two different ways from 1 other point doesn't mean that you can get a loop in there (since only 1 directional).
dfs would work (check if you have seen it or not), but it's inefficient, with a maximal running time of O(n!).

[Zeroth]

BFS does in fact find cycles. I didn't mention because it should have been obvious. Finding a node that two separate nodes can reach does not make it a cycle. Lets take the absolute base case of a cycle. Node n, and m. n->m->n... Exploring this branch with BFS will see that no matter which node we select in the cycle, if we place it on the bottom, like the root of a tree, we see one in and one out connections. Now, if we construct a cycle with 3 nodes, m, n, p, m->n->p->m... again taking any node in the cycle, we see at minimum 2 connections for each node, one in and one out. Any collection of nodes that is not a cycle will have at least one node that does not satisfy that constraint.

I'll say that again, if the algorithm suspects a cycle, it takes all the nodes in the suspected cycle, and checks to ensure that every single node has an in and out connection at the very least. For n nodes, that is O(n) runtime.

[Vermette]

Another approach would be to find a spanning-tree of the digraph, then examine the remaining edges for a back-edge (an edge that joins a node to its ancestor)