In mathematics, and more specifically in graph theory, a graph is a representation of a set of objects where some pairs of objects are connected by links. Graphs are incredibly important part of Modern day life. We come across them almost daily. For example we can reach our office via separate ways possible but which one to take(Considering distance, traffic). Whole of social media like Facebook, twitter, linkedin is nothing but a huge graph with people acting as node and their relationship(friendship) acting like links or edges. Computer networks, electricity distribution network, city pipeline network, road network, airline network, Internet are nothing but a form of a Graph. There are several types of Graphs such as Directed, Undirected, Tree, Weighted, Cyclic, Acyclic etc to name a few of them. And we find examples of almost all of them in real life.
There are several real life problems revolving around Graph theory. This post is not aimed at explaining what a graph is and what are their types or applications rather I want to cover the most basic but also most important algorithm applied to a graph. That is searching a Graph or traversing a Graph(Visiting all nodes). Depth first Search(DFS) and Breadth First Search(BFS) are two such algorithm who accomplish the same task(ie visiting all nodes and doing some action on them) but in a different way. We depict the example using an undirected graph but same logic should apply to directed Graph as well. We also demonstrate use of search algorithm to connect an unconnected graph.
Modeling a Graph into Programming Data Structure
There are various ways to model a Graph for a computer to understand. The most common and simple one is an adjacency matrix. Other ways are adjacency list or as two Sets containing Nodes and Edges. For the example in this post, I represented a graph as an adjacency matrix as well as set of nodes and edges. Lets take a Graph
So a
Graph Data Structure can be as simple as an adjacency matrix which is nothing but two dimensional Array
0, 2, 0,
5, 0
2, 0, 14, 5, 4
0, 14, 0, 0, 34
5, 5,
0, 0, 58
0, 4, 34, 58, 0
Same
Can be represented as a Set as shown below.
GraphNodes={1,2,3,4,5} GraphEdges={{1,2,2},{1,4,5},{2,3,14},{2,5,4},{2,4,5},{3,5,34},{4,5,58}}
About the example used for Demonstration
To
demonstrate DFS, BFS and Graph Connect Algorithms visually I have developed a
widows application using C# language that will generate a Graph randomly given
the number of nodes and then display them. Then from the starting node DFS and
BFS algorithm are depicted. If the graph is unconnected then an algorithm finds
and edge that belongs to two unconnected parts of the Graph. Connecting that
edge makes the nodes in each unconnected section reachable from one another. Doing so repeatedly connects the graph completely. Lets see the demo.
The graph below is taken as input. We can clearly see that the graph is not connected. When we click 'AddOneEdge' then at the background DFS algorithm is invoked that colors all the edges that can be reached from the start node. Now a search is made from for a node that is not colored. Clearly that node if gets connected with one of the colored nodes then the two disconnected sets of nodes will become connected.
The following video captures the snapshot of operation for connecting the graph.
Search Algorithm Details
Both DFS and BFS accomplish same goal but is a slightly different fashion. For BFS as name suggest the entire breadth of current node gets visited first and then after that their neighbors are explored. Where as in case of DFS entire depth of a node gets selected recursively and then the call returns to explore the neighboring nodes. To algorithms for implementing them is similar except for the fact in BFS we need to use a que where in we need to push all the neighbouring nodes of current nodes and visit them one by one.
Where in case of DFS we need to use a stack, where all the node visited along the path have to be pushed back in stack and if the depth is exhausted then pop the node from the back and visit it. Their pseudo code are provided in following document. pseudoCode
For demonstration lets take a Graph shown in the image below as starting point.
First connect it by clicking 'AddOneEdge' or 'AddTillConnect'. Then click on 'DFS' Button. Observe that one by one the nodes are getting colored, that is our activity when we visit a particulr node. It is implemented as a C# delegate, which is equivalent to a function pointer or boost function object. The status label will show the progress.
First connect it by clicking 'AddOneEdge' or 'AddTillConnect'. Then click on 'DFS' Button. Observe that one by one the nodes are getting colored, that is our activity when we visit a particulr node. It is implemented as a C# delegate, which is equivalent to a function pointer or boost function object. The status label will show the progress.
Once DFS is complete we can click 'ReInitialize' and then run BFS by clicking 'BFS' Button. This algorithm colors the nodes as well but their is a difference in the order in which the nodes are visited. Observe closely to understand the difference.
Details
about the source Files Shared
File
|
Details
|
Source File Implementing the Graph Algorithms BFS and DFS
|
|
Source File used for generating a Graph gven number of nodes and model it into a Datastructure
|
|
| The complete C# Project |
Conclusion and Next in line
This is the first post on explaining various Graph algorithms to get started. There are many interesting algorithms such as Minimum Spanning Tree, Shortest Path Problems, TSP, Graph coloring etc that I would love to demonstrate. Keep watching this space. Thanks for visiting this blog would love to hear your feedback.
No comments:
Post a Comment