Graph Implementation in C++

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

void removewt(double  g[][MAXNODES], int node1, int node2)
{
g[node1][node2] = -1;
}

int adjacent(double  g[][MAXNODES], int node1, int node2)
{
if (g[node1][node2]  !=  -1)
return TRUE;
else
return FALSE;
}

Linked-list representation of Graph

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

Adjacency list

Related Posts

• Queue Implementation in C++
• Binary Search Trees and Data Structure
• Bucket Sort (Bin Sort) with Example
• Quick Sort Algorithm with Graphical Explanation
• Heap Sort with Graphical Explanation
• Merge Sort with Graphical explanation
• Graphical Path Finding System using Dijkstra Algorithm
• Applications of Dijkstra Algorithm
• The OpenGL Programming Guide
• Introduction to Recursion in C++