Code States # 1 - Depth First Search (DFS) algorithm for Graph

People get bogged down to writing codes, when all they want is the implementation. Not everyone wants to be a true coder, but wants its benefits. Coding is fun and i suggest all to go this line at some point of their life if not now. This is a new series of blog for those who need reference for various coding algorithm and for those who need all together coding modules. Please feel free to use these codes and distribute it.

This is a code for Depth First Search algorithm for Graph. It is quite an intuitive algorithm and has quite a crisp code. 

Depth First Search algorithm is used in many applications, some of them are as follows:

1. To find if the graph is bipartite or not. A graph is bipartite if it can be divided into two mutually exclusive sets whose union is the set itself, and any edge of the graph joins vertex of one set to that of other.
2. For an unweighted graph, DFS traversal of the graph produces the minimum spanning tree.
3. Detecting cycle in a graph 
   A graph has cycle if and only if we see a back edge during DFS. So we can run DFS for the graph and check for back edges. 
4. Maze Solving - Heard of that famous Mouse and cheese problem on the Maze. We can use DFS for that purpose. It is how we would have done it, if we were a mouse.
5. Path finding - To find a path between two points.

There are many more, but i will give you the chance to Google them yourself. For example, search google for what is a Minimum Spanning Tree (MST).

So here is the code. Enjoy. 

Edit ---- The parsing for blogspot is just something i wont appreciate a lot. You can instead find the codes in my github repository. Fork me there, to get the code. The link is just below.
harpribotics.blogspot
 

# include
# define max_node 50
using namespace std;

struct adjlist{
 int vertex;
 adjlist* next;
};

adjlist *adj[max_node];

int visited[max_node];  // exclusive for recursive DFS

int totNodes;

// creat the adjascency list of the graph

void createGraph(){
 adjlist *newl,*last;
    int neighbours,neighbour_value;
    cout<<"\n\n---Graph Creation---\n\n";
    cout<<"Enter total nodes in graph : ";
    cin>>totNodes;
    for(int i=1;i<=totNodes;i++){
        last=NULL;
        visited[i] = 0; // exclusively for recursive DFS 
        cout<<"\nEnter no. of nodes in the adjacency list of node "< That is Total Neighbours of "<>neighbours;
        for(int j=1;j<=neighbours;j++){
            cout<<"Enter neighbour #"<>neighbour_value;
            newl=new adjlist;
            newl -> vertex = neighbour_value;
            newl -> next = NULL;
            if(adj[i] == NULL){
             adj[i] = newl;
             last = newl;
            }
            else{
             last -> next = newl;
             last = newl;
            }
        }
    }
}
// this quite an intellectual and crisp code instead of the lengthy recursion
void TrueDFS_Traversal(int w){
 visited[w] = 1; cout<<" "<vertex]) TrueDFS_Traversal(adj[w] -> vertex);
 adj[w] = adj[w] -> next;
 } 
}
int main(){
    
    cout<<"*****Depth First Search Traversal*****\n";
    createGraph();
    cout<<"\n===True DFS traversal using recursion is as under==\n";
    // ask for the start node
    int start_node;
    cout<<"Enter starting node : ";
    cin>>start_node;
    TrueDFS_Traversal(start_node);
    int n;
    cin>>n;
}