GRAPH

Graph is a collection of nodes and arcs that are mathematically expressed as:
G = (V, E)
where
G = Graph
V = Vertex or Vertex, or Node, or Point
E = arc or edge, or arc
A graph may consist of only one node
A graph is not necessarily all the vertices connected by arcs
A graph may have vertices are not connected to another node
A graph may be all the vertices are interconnected
Not trending graph (undirected graph or non-directed graph):
Sequence of vertices in an arc does not matter. Mis e1 arc can be called an arc AB or BA
Directed graph (directed graph):
Knot sequence has meaning. Mis arc AB is the arc while the BA is e1 e8.
Weighted graph (Weighted Graph)
If each arc has a value expressing the relation between 2 pieces of a node, then the arc is expressed as a weight.
The weight of an arc to the length of a path of 2 pieces of the point, the average number of vehicles per day through a street, etc..

#include <iostream.h>

#include <conio.h>

class graph{

        private:int n;

               int **a;

               int *reach;

               int *pos;

        public:graph(int k=10);

               void create();

               void dfs();

               void dfs(int v,int label);

               int begin(int v);

               int nextvert(int v);

};

void graph::graph(int k){

        n=k;

        a=new int *[n+1];

        reach=new int[n+1];

        pos=new int [n+1];

        for(int i=1;i<=n;i++)

               pos[i]=0;

        for(int j=1;j<=n;j++)

               a[j]=new int[n+1];}

void graph::create(){

        for(int i=1;i<=n;i++){

               cout<<"Enter the "<<i<<"th row of matrix a:";

               for(int j=1;j<=n;j++)

                       cin>>a[i][j];}

        for(int k=1;k<=n;k++)

               reach[k]=0;}

void graph::dfs(){

        int label=0;

        for(int i=1;i<=n;i++)

               if(!reach[i]){

                       label++;

                       dfs(i,label);}

        cout<<"The contents of the reach array is:”;

        for(int j=1;j<=n;j++)

               cout<<reach[j]<<"      ";}

void graph::dfs(int v,int label){

        cout<<v<<"     ";

        reach[v]=label;

        int u=begin(v);

        while(u){

               if(!reach[u])

                       dfs(u,label);

               u=nextvert(v);}

}

int graph::begin(int v){

        if((v<1)&&(v>n))

               cout<<"Bad input";

        else

               for(int i=1;i<=n;i++)

                       if(a[v][i]==1){

                               pos[v]=i;

                               return i;}

        return 0;}

int graph::nextvert(int v){

        if((v<1)&&(v>n))

               cout<<"Bad input";

        else

               for(int i=pos[v]+1;i<=n;i++)

                       if(a[v][i]==1){

                               pos[v]=i;

                               return i;}

        return 0;}

void main(){

        clrscr();

        int x;

        cout<<"Enter the no of vertices:";

        cin>>x;

        graph g(x);

        g.create();

        cout<<"dfs is.....";

        g.dfs();

        getch();}