graph theory

nobodythere

Hi, I'm learning about graph theory as I was reading up about routing protocols on the internet and such. I've seen shortest path algorithms (bellman-ford and djikstra) to find the shortest route from a to b.

I'm wondering if anyone knows any name (or general name) for an algorithm that simply confirms that there IS a path from A to B?

rjt

grasshopa wrote:

Hi, I'm learning about graph theory as I was reading up about routing protocols on the internet and such. I've seen shortest path algorithms (bellman-ford and djikstra) to find the shortest route from a to b.

I'm wondering if anyone knows any name (or general name) for an algorithm that simply confirms that there IS a path from A to B?

There are probably better ways, but try a Depth First Search.

Professor_Fink

grasshopa wrote:

I'm wondering if anyone knows any name (or general name) for an algorithm that simply confirms that there IS a path from A to B?

I don't know any, but I can think one up fairly easily. To do it, we need to maintain some lists (which I'll call LIST1 and LIST2).

1) Select vertex A
2) Let A=C
3) Add all vertices D for which an edge C->D exists to LIST1
4) Add D to LIST2
5) If B is in LIST1, stop (there exists a route)
6) Remove all vertices in LIST2 from LIST1
7) If LIST1 if empty, stop (a route does not exist)
8) Assign some vertex from LIST1 to C
9) Goto 3

Should give you the answer in <N^2 repetitions, where N is the total number of vertices in the graph.

I have assumed you were talking about a directed graph. If you just meant a simple non-directed graph, then you can work it out directly from the adjacency matrix.