C++ example-Graph


C++ code of Graph data structure

This is a simple graph program written in C++. The program has the basic functions to to initialize graph, add edge, delete an edge, return the first, and next neighbors of a vertex, return the numbers of vertices and edges, return the weight of any edge, set and get the visit status, and traverse through the graph by dept-first search algorithm.

#include
#include
#include
using namespace std;
class graphmatrix{

private:

int numVertices, numEdges;
int **matrix;
bool *visited;

public:
graphmatrix(int n);//constructuer
~graphmatrix();//destructor
void initgr(int v); //inilialize graph
void setEdge(int v1,int v2, int wt); //set edge
void delEdge(int v1, int v2);//delete edge
int first(int v);//return the first neightbor vertex of v
int next(int v,int w);//return the next neightbor vertex of v
int getN(){return numVertices;};//return number of vertices
int getE(){return numEdges;};//return number of edges
int getW(int v1,int v2){return matrix[v1][v2];};//return weight of edge
void setVisited(int v, bool val);//set visit status
bool getVisited(int v){return visited[v];};//return visit status
void dfs(graphmatrix *gm,int v);//graph traversal--dept-first search

};

graphmatrix::graphmatrix(int n){

initgr(n);
}

graphmatrix::~graphmatrix(){
for(int j=0;j

delete [] matrix[j];
delete [] matrix;


}


void graphmatrix::initgr(int n){int i;numVertices=n;numEdges=0;visited=(bool*) new int[numVertices]; //allocate for visitedfor(i=0;i
visited[i]=false;

matrix=(int**) new int*[numVertices];//allocate for matrix arrayfor(i=0;imatrix[i]=new int[numVertices];

for(i=0;i
for(int j=0;j
matrix[i][j]=0; //initialize matrix
}void graphmatrix::setEdge(int v1, int v2, int wt){

if(wt<=0) cout<<"Invlid weight"<

else{
numEdges++;
matrix[v1][v2]=wt;}
}void graphmatrix::delEdge(int v1, int v2){
matrix[v1][v2]=0;
numEdges--;
}int graphmatrix::first(int v){

for(int j=0;jif(matrix[v][j]!=0) return j;
return numVertices;

}int graphmatrix::next(int v,int w){

for(int j=w+1;j

if(matrix[v][j]!=0) return j;return numVertices;}void graphmatrix::setVisited(int v,bool val){
visited[v]=val;


}


void graphmatrix::dfs(graphmatrix *gm,int v){
if(gm->getE()<=0) cout<<"Empty graph"<

else{

setVisited(v,true);
cout<<"Visited:"<
for(int w=first(v);wgetN();w=gm->next(v,w)){
if(gm->getVisited(w)==false)
dfs(gm,w);
}

}

}

int main(int argc, char *argv[])
{

graphmatrix *gm=new graphmatrix(5);
gm->setEdge(0,1,2);
gm->setEdge(0,4,3);
gm->setEdge(1,3,4);
gm->setEdge(3,2,5);
gm->setEdge(2,4,2);
gm->setEdge(4,1,1);
gm->dfs(gm,0);//visit the graph
getch();
return 0;
}




Comments

Vijay comment

 Vijay

Thanks for posting this.


2014-03-02



This website intents to provide free and high quality tutorials, examples, exercises and solutions, questions and answers of programming and scripting languages:
C, C++, C#, Java, VB.NET, Python, VBA,PHP & Mysql, SQL, JSP, ASP.NET,HTML, CSS, JQuery, JavaScript and other applications such as MS Excel, MS Access, and MS Word. However, we don't guarantee all things of the web are accurate. If you find any error, please report it then we will take actions to correct it as soon as possible.