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;
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

One Response to Graph Implementation in C++

  1. Ali says:

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

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.