PROBLEM : Given a directed graph check whether the graph contains a cycle or not.

SOLUTION : In a graph containing a cycle suppose vi,...vk are the vertices that constitute the cycle and suppose that the backedge is from vk to vi then on applying dfs to the graph "when the dfs covers the edge from vk to vi then vi must have already been visited." vi will already be in the recursion stack when the edge will be covered.Hence we know a cycle is present.Thus the given graph will not be cyclic.

Thus for each node visited earlier we need to store the recursion stack to tell whether a edge points to a node already in the recursion stack.Then it would be a back edge.In this way this algorithm can be modified to find in a graph:

• The number of back edges
• The components i.e. the trees in a forest
• The number of cycles = number of back edges .. etc

The cpp code for the following :

#include<iostream>
#include<list>

using namespace std;

class Graph
{
    int V; //number of vertices
    list<int> *adj; //pointer to array containing adjacency lists
    bool isCyclicUtil(int v,bool visited[],bool *rs);

    public:
        Graph(int v);
        void addEdge(int v,int w);
        bool isCyclic();
};

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

void Graph::addEdge(int v,int w)
{
    adj[v].push_back(w);
}

bool Graph::isCyclicUtil(int v,bool visited[],bool *rs)
{
    if(visited[v]==false)
    {
        visited[v]=true;
        rs[v]=true;
        list<int>::iterator i;
        for(i=adj[v].begin();i!=adj[v].end();++i)
        {
            if(!visited[*i] && isCyclicUtil(*i,visited,rs))
            return true;
            else if(rs[*i])
            return true;
        }
    }
    rs[v]=false;
    return false;
}

bool Graph::isCyclic()
{
    bool *visited=new bool[V];
    bool *rs=new bool[V];
    for(int i=0;i<V;i++)
    {
        visited[i]=false;
        rs[i]=false;
    }
    for(int i=0;i<V;i++)
    if(isCyclicUtil(i,visited,rs))
        return true;
    return false;
}

int main()
{
    Graph g(4);
    g.addEdge(0,1);
    g.addEdge(0,2);
    g.addEdge(1,2);
    g.addEdge(2,0);
    g.addEdge(2,3);
    g.addEdge(3,3);

    if(g.isCyclic())
    cout<<"Graph contains a cycle"<<endl;
    else
    cout<<"Graph doesnot contain a cycle"<<endl;
    return 0;
}

#include<stdio.h>
#include<assert.h>
#include<conio.h>
/* maxVertices represents maximum number of vertices that can be present in the graph. */
/*graph is undirected and not weighted*/
#define maxVertices   100
void Dfs(int graph[][maxVertices],int *size,int presentVertex,int *visited)
{
     printf("Now visiting vertex %d\n",presentVertex);
     visited[presentVertex]=1;
     /* Iterate through all the vertices connected to the presentVertex and perform dfs on those
           vertices if they are not visited before */
     int iter;
     for(iter=0;iter<size[presentVertex];iter++)
     {
             if(!visited[graph[presentVertex][iter]])
             Dfs(graph,size,graph[presentVertex][iter],visited);
     }
     return;
}
/* Input Format: Graph is directed and unweighted. First two integers must be number of vertces and edges 
   which must be followed by pairs of vertices which has an edge between them. */
int main()
{
        int graph[maxVertices][maxVertices],size[maxVertices]={0},visited[maxVertices]={0};
        int vertices,edges,iter;
        /* vertices represent number of vertices and edges represent number of edges in the graph. */
        scanf("%d%d",&vertices,&edges);
        int vertex1,vertex2;
        for(iter=0;iter<edges;iter++)
        {
                scanf("%d%d",&vertex1,&vertex2);
                assert(vertex1>=0 && vertex1<vertices);
                assert(vertex2>=0 && vertex2<vertices);
                graph[vertex1][size[vertex1]++] = vertex2;
        }
        int presentVertex;
        for(presentVertex=0;presentVertex<vertices;presentVertex++)
        {
                if(!visited[presentVertex])
                {
                        Dfs(graph,size,presentVertex,visited);
                }
        }
        getche();
        return 0;

}     


--------------------------------------PYTHON IMPLEMENTATION---------------------------------------------

def dfs(graph,p_vertex,visited):
    print("Visiting vertex {0}".format(p_vertex))
    visited[p_vertex]=1
    #print(len(graph[p_vertex]))
    for itr in range(0,len(graph[p_vertex])):
        if(visited[graph[p_vertex][itr]]==0):
            #print("sent to visit vertex {0}".format(graph[p_vertex][itr]))
            dfs(graph,graph[p_vertex][itr],visited)
    return

vertices=int(input("Enter number of vertices::"))
edges=int(input("Enter the number of edges::"))
graph=[]
visited=[0]*vertices

#create the vertices
for i in range(0,vertices):
    v=[]
    graph.append(v)
#take input
for i in range(0,edges):
    v1,v2=input().split()
    v1,v2=int(v1),int(v2)
    assert(v1>=0 and v1<vertices)
    assert(v2>=0 and v2<vertices)
    graph[v1].append(v2)

print(graph)

for p_vertex in range(0,vertices):
    if(visited[p_vertex]==0):
        dfs(graph,p_vertex,visited)

# breadth first search in PYTHON 3.2 #
from queue import *

def bfs(graph,p_vertex,visited):
    q=Queue()
    q.put(p_vertex)
    visited[p_vertex]=1
    while q.qsize()>0:
        t=q.get()
        print("Visiting vertex {0}".format(t))
        #i.e if t is what we want return t
        for child in range(0,len(graph[p_vertex])):
            if(visited[graph[p_vertex][child]]==0):
                visited[graph[p_vertex][child]]=1
                q.put(graph[p_vertex][child])
    return

vertices=int(input("Enter number of vertices::"))
edges=int(input("Enter the number of edges::"))
graph=[]
visited=[0]*vertices

#create the vertices
for i in range(0,vertices):
    v=[]
    graph.append(v)
#take input
for i in range(0,edges):
    v1,v2=input().split()
    v1,v2=int(v1),int(v2)
    assert(v1>=0 and v1<vertices)
    assert(v2>=0 and v2<vertices)
    graph[v1].append(v2)
print(graph)

for p_vertex in range(0,vertices):
    if(visited[p_vertex]==0):
        bfs(graph,p_vertex,visited)


----------->For those interested in C implimentation might find this a little long then python but here it is-------------->


#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
/* maxVertices represents maximum number of vertices that can be present in the graph. */
#define maxVertices   100
typedef struct Queue
{
        int capacity;
        int size;
        int front;
        int rear;
        int *elements;
}Queue;
/* crateQueue function takes argument the maximum number of elements the Queue can hold, creates
   a Queue according to it and returns a pointer to the Queue. */
Queue * CreateQueue(int maxElements)
{
        /* Create a Queue */
        Queue *Q;
        Q = (Queue *)malloc(sizeof(Queue));
        /* Initialise its properties */
        Q->elements = (int *)malloc(sizeof(int)*maxElements);
        Q->size = 0;
        Q->capacity = maxElements;
        Q->front = 0;
        Q->rear = -1;
        /* Return the pointer */
        return Q;
}
void Dequeue(Queue *Q)
{
        /* If Queue size is zero then it is empty. So we cannot pop */
        if(Q->size==0)
        {
                printf("Queue is Empty\n");
                return;
        }
        /* Removing an element is equivalent to incrementing index of front by one */
        else
        {
                Q->size--;
                Q->front++;
                /* As we fill elements in circular fashion */
                if(Q->front==Q->capacity)
                {
                        Q->front=0;
                }
        }
        return;
}
int Front(Queue *Q)
{
        if(Q->size==0)
        {
                printf("Queue is Empty\n");
                exit(0);
        }
        /* Return the element which is at the front*/
        return Q->elements[Q->front];
}
void Enqueue(Queue *Q,int element)
{
        /* If the Queue is full, we cannot push an element into it as there is no space for it.*/
        if(Q->size == Q->capacity)
        {
                printf("Queue is Full\n");
        }
        else
        {
                Q->size++;
                Q->rear = Q->rear + 1;
                /* As we fill the queue in circular fashion */
                if(Q->rear == Q->capacity)
                {
                        Q->rear = 0;
                }
                /* Insert the element in its rear side */
                Q->elements[Q->rear] = element;
        }
        return;
}



void Bfs(int graph[][maxVertices], int *size, int presentVertex,int *visited)
{
        visited[presentVertex] = 1;
        /* Iterate through all the vertices connected to the presentVertex and perform bfs on those
           vertices if they are not visited before */
        Queue *Q = CreateQueue(maxVertices);
        Enqueue(Q,presentVertex);
        while(Q->size)
        {
                presentVertex = Front(Q);
                printf("Now visiting vertex %d\n",presentVertex);
                Dequeue(Q);
                int iter;
                for(iter=0;iter<size[presentVertex];iter++)
                {
                        if(!visited[graph[presentVertex][iter]])
                        {
                                visited[graph[presentVertex][iter]] = 1;
                                Enqueue(Q,graph[presentVertex][iter]);
                        }
                }
        }
        return;


}
/* Input Format: Graph is directed and unweighted. First two integers must be number of vertces and edges
   which must be followed by pairs of vertices which has an edge between them. */
int main()
{
        int graph[maxVertices][maxVertices],size[maxVertices]={0},visited[maxVertices]={0};
        int vertices,edges,iter;
        /* vertices represent number of vertices and edges represent number of edges in the graph. */
        scanf("%d%d",&vertices,&edges);
        int vertex1,vertex2;
        for(iter=0;iter<edges;iter++)
        {
                scanf("%d%d",&vertex1,&vertex2);
                assert(vertex1>=0 && vertex1<vertices);
                assert(vertex2>=0 && vertex2<vertices);
                graph[vertex1][size[vertex1]++] = vertex2;
        }
        int presentVertex;
        for(presentVertex=0;presentVertex<vertices;presentVertex++)
        {
                if(!visited[presentVertex])
                {
                        Bfs(graph,size,presentVertex,visited);
                }
        }
        return 0;
}

------------------------------------------------------->END<------------------------------------------------------------------

Here is another important graph algo for finding the minimum weighted spanning tree imlimented in C.Input is taken from adj matrix with non-conn terms having val in #define MAXVAL & the number of vert changed by changing #define MAXVAL...


/*KRUSKAL ALGORITHM IN C*/
#include<stdio.h>
#define VERT 4 //predefined number of vertices
#define MAXVAL 99
void kruskal(int a[][VERT],int n);
int gethead(int vert,int par[]);
void vertex_union(int v1,int v2,int par[]);

void vertex_union(int v1,int v2,int par[])
{
    if(v1>v2)
    par[v1]=v2;
    else
    par[v2]=v1;
}

int gethead(int vert,int par[])
{
    while(par[vert]!=vert)
    {
        vert=par[vert];
    }
    return vert;
}

void kruskal(int a[][VERT],int n)
{
    int nofedges,i,parent[VERT],min,j,k,u,v,path[VERT-1][2],sum;
    nofedges=k=sum=0;
    for(i=0;i<n;i++)
    parent[i]=i;//sets parent
    while(nofedges<n-1)
    {
        min=MAXVAL;
        for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        if(a[i][j]<min)
        {
            min=a[i][j];
            u=i;
            v=j;
        }//gets the min for each turn
        if(min!=MAXVAL)
        {
            i=gethead(u,parent);
            j=gethead(v,parent);
            /*printf("==>%d %d %d %d\n",i,j,u,v);
            int ii;
            for(ii=0;ii<VERT;ii++)
            printf("%d ",parent[ii]);
            printf("\n");*/
            if(i!=j)
            {
                //printf("-->adding vertex %d %d",u,v);
                path[k][0]=u;
                path[k][1]=v;
                k++;
                sum+=min;
                vertex_union(i,j,parent);
                nofedges+=1;
            }
            a[u][v]=a[v][u]=999;
        }
    }
    if(nofedges!=n-1)
    printf("Invalid Spanning Tree");
    else
    {
        printf("Minimum cost=%d\n",sum);
        printf("The edges included are ::\n");
        for(i=0;i<n-1;i++)
        printf("%d %d \n",path[i][0],path[i][1]);
    }
}

int main()
{
    int cost[VERT][VERT],i,j;
    for(i=0;i<VERT;i++)
    for(j=0;j<VERT;j++)
    scanf("%d",&cost[i][j]);
    //adjacency matrix entered
    kruskal(cost,VERT);

}

Hope you enjoyed this..

Here's a graph algorithm implementation of Dijkstra's Algorithm in C .. input preferences are mentioned in comments in the program....

###########################################################################
/*Dijkrtas algorithm in C*/
#define N 6 //the number of vertices
#include<stdio.h>
#define INFINITY 999
#define TRUE 1
#define FALSE 0

int allvisited(int visits[])//checks if all nodes are visited or not
{
    int i,flag=1;
    for(i=0;i<N;i++)
    {
        if(visits[i]!=1)
        flag=0;
    }
    return flag;
}

int dijkstra(int graph[][N],int target,int source)
{
    int visited[N],dist[N];
    //source -1 in actual matrix ..check row for neighbours
    //init
    int i;
    for(i=0;i<N;i++)
    {
        dist[i]=INFINITY;
        visited[i]=-1;
    }
    int start=source;
    while(!allvisited(visited))
    {
        //printf("--->start=%d\n",start);
        visited[start]=1;
        if(dist[start]==INFINITY)
        {
            dist[start]=0;
        }
        for(i=0;i<N;i++)
        {
            if(graph[start][i]!=INFINITY)//this is a neighbour of start
            {
                int d=dist[start]+graph[start][i];
                if(d<dist[i])
                dist[i]=d;
            }
        }
        //checking
        /*for(i=0;i<N;i++)
        printf("%d ",dist[i]);
        printf("\n");*/
        //get the next node i.e. will be the minimum of tentative dist and unvisited
        int min=INFINITY;
        int pos=INFINITY;
        for(i=0;i<N;i++)
        {
            if(visited[i]!=1)
            {
                if(dist[i]<min)
                {
                    min=dist[i];
                    pos=i;
                }
            }
        }
        //if pos==NULL then over
        if(pos==INFINITY)
        break;
        else
        start=pos;
        //printf("continue..\n");
    }
    return dist[target];
}

int main()
{
    int graph[N][N];
    int i,j;
    printf("Enter the graph::\n");
    for(i=0;i<N;i++)
    for(j=0;j<N;j++)
    scanf("%d",&graph[i][j]);
    //taken input must be symmetric and for i=j should be 0 and for not connected should be infinity as defined
    int src,tar;
    printf("Enter the source and target::");
    scanf("%d %d",&src,&tar);
    int dis=dijkstra(graph,tar-1,src-1);
    printf("min dist=%d",dis);
    return 0;
}
##################################################################################

If anyone wants the python or Java version please mention it in the comments and i will post it..