A data structure that consists of a set of nodes (vertices) and a set of edges that relate the nodes to each other. The set of edges describes relationships among the vertices.  Array-based implementation can be a 1-D array is used to represent the vertices while a 2-D array (adjacency matrix) is used to represent the edges.

Array representation of Graph

Matrix Representation of a graph (Directed Graph)

Adjacency Matrix of Graphs

Implementation of graph using Adjacency Matrix

A graph with a fixed number of nodes may be implemented simply by using:

struct vertices{
char info[20];
};
vertices graphVertices vertices[MAXNODES];  // to store the vertices
double   matrix[MAXNODES][MAXNODES]; // to store the edges in the graph

Routine to join two nodes with an arc of some weight may be defined as

void  joinwt(double  g[][MAXNODES], int node1, int     node2, double wt)
{
g[node1][node2] = wt;
}
Routine to remove arc between two nodes may be defined as
void removewt(double  g[][MAXNODES], int node1, int node2)
{
g[node1][node2] = -1;
}
Routine to check two adjacent nodes may be defined as
int adjacent(double  g[][MAXNODES], int node1, int node2)
{
if (g[node1][node2]  !=  -1)
return TRUE;
else
return FALSE;
}

Linked-list representation of Graph

  • A 1D array is used to represent the vertices
  • A list is used for each vertex v which contains the vertices which are adjacent from v (adjacency list)

Consider the following example:

Adjacency List of Graph

Implementation of graph using Adjacency List

We can represent each graph node as a struct

struct graphNode {
char info[20];
connVertices * NextEdge;
};

A structure representing edges/links between nodes can be declared as

struct connVertices {
int index;
float weight;
connVertices * Next;
};

 

Adjacency matrix vs. Adjacency list Representation

Adjacency matrix

  • More Memory required
  • Good for dense graphs
  • Connectivity between two vertices can be tested quickly

Adjacency list

  • Less memory required
  • Good for sparse graphs
  • Vertices adjacent to another vertex can be found quickly

 

 

Tagged with: C/C++ languageData structures
 

2 Responses to Graph Implementation in C++

  1. Ali says:

    Hi, thanks for this page. It helped me in my preparation for a job interview.

  2. Alex says:

    Thanks so much.It helped me a lot.

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

 

Looking for something?

Use the form below to search the site:


Still not finding what you're looking for? Drop a comment on a post or contact us so we can take care of it!

Related News Feeds

Set your Twitter account name in your settings to use the TwitterBar Section.