Learning Graphs

Representation :

Using adjacency list :


BFS and DFS 
// Program to print BFS traversal from a given source vertex. BFS(int s) 
// traverses vertices reachable from s.
#include<iostream>
#include <list>

using namespace std;

// This class represents a directed graph using adjacency list representation
class Graph
{
    int V;    // No. of vertices
    list<int> *adj;    // Pointer to an array containing adjacency lists

/*
adj = new list[V];
If you use simply list adj[V] system creates an array of list with size V, so your list constructor will get call V times.
new operator allocates memory and invokes the constructor.

So this statement list* adj= new list[V] allocates memory for V times the size of object of class list and invokes constructor of class list V times, and assigns the starting of the memory location to variable adj.

This kind of statement
x = new X[N];
assigns the result of the expression on the right hand side of the = to x.
So, you are dynamically allocating an array of V objects of type list, ans assigning a pointer to the first element to adj.
*/ 

    void DFSUtil(int v, bool visited[]);  // A function used by DFS
public:
    Graph(int V);  // Constructor
    void addEdge(int v, int w); // function to add an edge to graph
    void BFS(int s,int check);  // prints BFS traversal from a given source s
    void DFS(int v);    // DFS traversal of the vertices reachable from v 
};

Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}

void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w); // Add w to v’s list.
}

void Graph::BFS(int s,int  check)
{
    int ans =1;
    // Mark all the vertices as not visited
    bool *visited = new bool[V];
    for(int i = 0; i < V; i++)
        visited[i] = false;

    // Create a queue for BFS
    list<int> queue;

    // Mark the current node as visited and enqueue it
    visited[s] = true; if(s==check){ans =0;}
    queue.push_back(s);

    // 'i' will be used to get all adjacent vertices of a vertex
    list<int>::iterator i;

    while(!queue.empty())
    {
        // Dequeue a vertex from queue and print it
        s = queue.front();
         if(s==check){ans =0;}
        cout << s << " ";
        queue.pop_front();

        // Get all adjacent vertices of the dequeued vertex s
        // If a adjacent has not been visited, then mark it visited
        // and enqueue it
        for(i = adj[s].begin(); i != adj[s].end(); ++i)
        {
            if(!visited[*i])
            {
                visited[*i] = true;
                queue.push_back(*i);
            }
        }//cout<<endl;
    }cout<<endl<<ans<<endl;
}
void Graph::DFSUtil(int v, bool visited[])
{
    // Mark the current node as visited and print it
    visited[v] = true;
    cout << v << " ";

    // Recur for all the vertices adjacent to this vertex
    list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i])
            DFSUtil(*i, visited);
}

// DFS traversal of the vertices reachable from v. 
// It uses recursive DFSUtil()
void Graph::DFS(int v)
{
    // Mark all the vertices as not visited
    bool *visited = new bool[V];
    for (int i = 0; i < V; i++)
        visited[i] = false;

    // Call the recursive helper function to print DFS traversal
    DFSUtil(v, visited);
}


// Driver program to test methods of graph class
int main()
{

     int nodes, max_edges, origin, destin;
   // cout<<"Enter number of nodes: ";
    cin>>nodes;
    Graph g(nodes);
    max_edges = nodes * (nodes - 1);
    for (int i = 0; i < max_edges; i++)
    {
       
        cin>>origin>>destin;
        
        if((origin == -1) && (destin == -1))
            break;
         g.addEdge(origin, destin);
    }
   
    int verty,checky;
    cin>>verty>>checky;

    g.BFS(verty,checky);
    g.DFS(verty);
}

There is something called as topological sorting , so that you can check which job is scheduled first or next . you can check the order of dfs by  this :

// A C++ program to print topological sorting of a DAG

#include <iostream>

#include <stdio.h>

#include <list>

#include <stack>

using namespace std;

// Class to represent a graph

class Graph

{

    int V;    // No. of vertices'

    // Pointer to an array containing adjacency listsList

    list<int> *adj;

    // A function used by topologicalSort

    void topologicalSortUtil(int v, bool visited[], stack<int> &Stack);

public:

    Graph(int V);   // Constructor

     // function to add an edge to graph

    void addEdge(int v, int w);

    // prints a Topological Sort of the complete graph

    void topologicalSort();

};

Graph::Graph(int V)

{

    this->V = V;

    adj = new list<int>[V];

}

void Graph::addEdge(int v, int w)

{

    adj[v].push_back(w); // Add w to v’s list.

}

// A recursive function used by topologicalSort

void Graph::topologicalSortUtil(int v, bool visited[], 

                                stack<int> &Stack)

{

    // Mark the current node as visited.

    visited[v] = true;

    // Recur for all the vertices adjacent to this vertex

    list<int>::iterator i;

    for (i = adj[v].begin(); i != adj[v].end(); ++i)

        if (!visited[*i])

            topologicalSortUtil(*i, visited, Stack);

    // Push current vertex to stack which stores result

    Stack.push(v);

}

// The function to do Topological Sort. It uses recursive 

// topologicalSortUtil()

void Graph::topologicalSort()

{

    stack<int> Stack;

    // Mark all the vertices as not visited

    bool *visited = new bool[V];

    for (int i = 0; i < V; i++)

        visited[i] = false;

    // Call the recursive helper function to store Topological

    // Sort starting from all vertices one by one

    for (int i = 0; i < V; i++)

      if (visited[i] == false)

        topologicalSortUtil(i, visited, Stack);

    // Print contents of stack

    while (Stack.empty() == false)

    {

        cout << Stack.top() << " ";

        Stack.pop();

    }

}

// Driver program to test above functions

int main()

{

    // Create a graph given in the above diagram

    int V,i,j,k;

    scanf("%d",&V);

    Graph g(V+1);

    for(i=1;i<V;i++)

    {

        scanf("%d%d",&j,&k);

        g.addEdge(j,k);

    }

    cout << "Following is a Topological Sort of the given graph \n";

    g.topologicalSort();

    return 0;

}

There  is a way to traverse a rectangular maze using DFS :

function DFS(x, y, visited, n, m)

    if (x ≥ n OR y ≥ m)

        return

    if(x < 0 OR y < 0)

        return

    if(visisted[x][y] == True)

        return

    visited[x][y] = True

    DFS(x-1, y-1, visited, n, m)

    DFS(x-1, y, visited, n, m)

    DFS(x-1, y+1, visited, n, m)

    DFS(x, y-1, visited, n, m)

    DFS(x, y+1, visited, n, m)

    DFS(x+1, y-1, visited, n, m)

    DFS(x+1, y, visited, n, m)

    DFS(x+1, y+1, visited, n, m)

Difference between a graph and a tree :

In a graph there can be back edge , forward edge , cross edge , tree edge .

DFS of a graph gives you a tree. And if there are more components which are disconnected, then DFS give a tree forest.

1.In a tree  there is aunique  path from every single  vertex to other vertices. Also it is not necessary that degree of all the vertices of a tree is either 1 or 2.

2.There isn't any cycle in a tree.

 How to detect cycle in an undirected graph?

We can either use BFS or DFS. For every visited vertex ‘v’, if there is an adjacent ‘u’ such that u is already visited and u is not parent of v, then there is a cycle in graph. If we don’t find such an adjacent for any vertex, we say that there is no cycle.

3.If we take the sum of all the degrees, each edge will be counted twice. Hence, for a tree with n vertices and n – 1 edges, sum of all degrees should be 2 * (n – 1).

4.Tree has exactly n-1 edges while there is no such constraint for graph.