Check Connectivity of Network using DFS

[gradnu]

Can somebody tell me how to implement(possibly C program) DFS to check whether a network is connected or not. I have network in the form of adjacency matrix.

Thanks

 

[deltawing1]

I'm not sure I understand your question properly, but I can try to explain the DFS in general. I'm no mathematician so I can only really understand graphs and nodes and whatever in lay terms.

First you need to convert the adjacency matrix into some form of data structure you can store on the computer. A 2D array or vector (NOT the mathematical vector) I suppose? What I would do is use an object oriented language such as C++ and have a Graph composed of Nodes and Connections.

With the depth-first-search I think you can just implement a Last In First Out stack as your data structure to hold all the nodes. The LIFO stack is quite simple - the last item that you add into the stack, the first it is to come out.

A computer network can be represented as a graph with nodes. As you are traversing through the graph (with some sort of loop) you add to the stack all the adjacent unvisited nodes to the current node you are on. As you know, with a DFS you go as deeply into the graph until you find your target. If you reach the leaf node and still don't find it, then you need to track back to the previous node and go as deep into that node, and so on.

Once you find your node, you stop the process of looking. Again, if you were applying the OOP paradigm (e.g. Java or C++), you'd have a class Node, Connection, Graph, and Stack. Each Node needs a private data member that knows it's parent Node, so you can track back to the beginning once you've finished the search.

In general that is (to my knowledge) how DFS works.

Here is a good animation
http://www.rci.rutgers.edu/~cfs/472_html/AI_SEARCH/SearchAnimations.html

 

[gradnu]

Thanks