Graph Implementation In C++ Using Adjacency List

This Tutorial Explains The Implementation of Graphs In C++. You Will Also Learn About Different Types, Representations, and Applications of Graphs:

A graph is a non-linear data structure. A graph can be defined as a collection of Nodes which are also called “vertices” and “edges” that connect two or more vertices.

A graph can also be seen as a cyclic tree where vertices do not have a parent-child relationship but maintain a complex relationship among them.

=> Click Here For The Absolute C++ Training Series.

C++ Data Structure Graph

Whats Is A Graph In C++?

As stated above, a graph in C++ is a non-linear data structure defined as a collection of vertices and edges.

Following is an example of a graph data structure.

Example of a graph data structure

Given above is an example graph G. Graph G is a set of vertices {A,B,C,D,E} and a set of edges {(A,B),(B,C),(A,D),(D,E),(E,C),(B,E),(B,D)}.

Types of Graphs – Directed And Undirected Graph

A graph in which the edges do not have directions is called the Undirected graph. The graph shown above is an undirected graph.

A graph in which the edges have directions associated with them is called a Directed graph.

Given below is an example of a directed graph.

2.directed graph example

In the directed graph shown above, edges form an ordered pair wherein each edge represents a specific path from one vertex to another vertex. The vertex from which the path initiates is called “Initial Node” while the vertex into which the path terminates is called the “Terminal Node”.

Thus in above graph, the set of vertices is {A, B, C, D, E} and the set of edges is {(A,B),(A,D),(B,C),(B,E),(D,E)(E,C)}.

We will discuss the graph terminology or the common terms used in relation to the graph below.

Graph Terminology

Graph Terminology

  1. Vertex: Each node of the graph is called a vertex. In the above graph, A, B, C, and D are the vertices of the graph.
  2. Edge: The link or path between two vertices is called an edge. It connects two or more vertices. The different edges in the above graph are AB, BC, AD, and DC.
  3. Adjacent node: In a graph, if two nodes are connected by an edge then they are called adjacent nodes or neighbors. In the above graph, vertices A and B are connected by edge AB. Thus A and B are adjacent nodes.
  4. Degree of the node: The number of edges that are connected to a particular node is called the degree of the node. In the above graph, node A has a degree 2.
  5. Path: The sequence of nodes that we need to follow when we have to travel from one vertex to another in a graph is called the path. In our example graph, if we need to go from node A to C, then the path would be A->B->C.
  6. Closed path: If the initial node is the same as a terminal node, then that path is termed as the closed path.
  7. Simple path: A closed path in which all the other nodes are distinct is called a simple path.
  8. Cycle: A path in which there are no repeated edges or vertices and the first and last vertices are the same is called a cycle. In the above graph, A->B->C->D->A is a cycle.
  9. Connected Graph: A connected graph is the one in which there is a path between each of the vertices. This means that there is not a single vertex which is isolated or without a connecting edge. The graph shown above is a connected graph.
  10. Complete Graph: A graph in which each node is connected to another is called the Complete graph. If N is the total number of nodes in a graph then the complete graph contains N(N-1)/2 number of edges.
  11. Weighted graph: A positive value assigned to each edge indicating its length (distance between the vertices connected by an edge) is called weight. The graph containing weighted edges is called a weighted graph. The weight of an edge e is denoted by w(e) and it indicates the cost of traversing an edge.
  12. Diagraph: A digraph is a graph in which every edge is associated with a specific direction and the traversal can be done in specified direction only.

Graph Representation

The way in which graph data structure is stored in memory is called “representation”. The graph can be stored as a sequential representation or as a linked representation.

Both these types are described below.

Sequential Representation

In the sequential representation of graphs, we use the adjacency matrix. An adjacency matrix is a matrix of size n x n where n is the number of vertices in the graph.

The rows and columns of the adjacency matrix represent the vertices in a graph. The matrix element is set to 1 when there is an edge present between the vertices. If the edge is not present then the element is set to 0.

Given below is an example graph that shows its adjacency matrix.

Adjacency matrix in Sequential Representation

We have seen the adjacency matrix for the above graph. Note that since this is an undirected graph, and we can say that the edge is present in both directions. For Example, as edge AB is present, we can conclude that edge BA is also present.

In the adjacency matrix, we can see the interactions of the vertices which are matrix elements that are set to 1 whenever the edge is present and to 0 when the edge is absent.

Now let us see the adjacency matrix of a directed graph.

Directed graph in Sequential Representation

As shown above, the intersection element in the adjacency matrix will be 1 if and only if there is an edge directed from one vertex to another.

In the above graph, we have two edges from vertex A. One edge terminates into vertex B while the second one terminates into vertex C. Thus in adjacency matrix the intersection of A & B is set to 1 as the intersection of A & C.

Next, we will see the sequential representation for the weighted graph.

Given below is the weighted graph and its corresponding adjacency matrix.

Weighted graph and its adjacency matrix

We can see that the sequential representation of a weighted graph is different from the other types of graphs. Here, the non-zero values in the adjacency matrix are replaced by the actual weight of the edge.

The edge AB has weight = 4, thus in the adjacency matrix, we set the intersection of A and B to 4. Similarly, all the other non-zero values are changed to their respective weights.

The adjacency list is easier to implement and follow. Traversal i.e. to check if there is an edge from one vertex to another takes O(1) time and removing an edge also takes O(1).

Whether the graph is sparse (fewer edges) or dense, it always takes more amount of space.

Linked Representation

We use the adjacency list for the linked representation of the graph. The adjacency list representation maintains each node of the graph and a link to the nodes that are adjacent to this node. When we traverse all the adjacent nodes, we set the next pointer to null at the end of the list.

Let us first consider an undirected graph and its adjacency list.

undirected graph and its adjacency list

As shown above, we have a linked list (adjacency list) for each node. From vertex A, we have edges to vertices B, C and D. Thus these nodes are linked to node A in the corresponding adjacency list.

Next, we construct an adjacency list for the directed graph.

Adjacency list for the directed graph

In the above-directed graph, we see that there are no edges originating from vertex E. Hence the adjacency list for vertex E is empty.

Now let us construct the adjacency list for the weighted graph.

Adjacency list for the weighted graph

For a weighted graph, we add an extra field in the adjacency list node to denote the weight of the edge as shown above.

Adding vertex in the adjacency list is easier. It also saves space due to the linked list implementation. When we need to find out if there is an edge between one vertex to another, the operation is not efficient.

Basic Operations For Graphs

Following are the basic operations that we can perform on the graph data structure:

  • Add a vertex: Adds vertex to the graph.
  • Add an edge: Adds an edge between the two vertices of a graph.
  • Display the graph vertices: Display the vertices of a graph.

C++ Graph Implementation Using Adjacency List

Now we present a C++ implementation to demonstrate a simple graph using the adjacency list.

Here we are going to display the adjacency list for a weighted directed graph. We have used two structures to hold the adjacency list and edges of the graph. The adjacency list is displayed as (start_vertex, end_vertex, weight).

The C++ program is as follows:

#include <iostream>
using namespace std;
// stores adjacency list items
struct adjNode {
	int val, cost;
	adjNode* next;
};
// structure to store edges
struct graphEdge {
	int start_ver, end_ver, weight;
};
class DiaGraph{
	// insert new nodes into adjacency list from given graph
	adjNode* getAdjListNode(int value, int weight, adjNode* head) 	{
		adjNode* newNode = new adjNode;
		newNode->val = value;
		newNode->cost = weight;
		
		newNode->next = head;   // point new node to current head
		return newNode;
	}
	int N;  // number of nodes in the graph
public:
	adjNode **head;                //adjacency list as array of pointers
	// Constructor
	DiaGraph(graphEdge edges[], int n, int N)  {
		// allocate new node
		head = new adjNode*[N]();
		this->N = N;
		// initialize head pointer for all vertices
		for (int i = 0; i < N; ++i)
			head[i] = nullptr;
		// construct directed graph by adding edges to it
		for (unsigned i = 0; i < n; i++)  {
			int start_ver = edges[i].start_ver;
			int end_ver = edges[i].end_ver;
			int weight = edges[i].weight;
			// insert in the beginning
			adjNode* newNode = getAdjListNode(end_ver, weight, head[start_ver]);
			
                        // point head pointer to new node
			head[start_ver] = newNode;
       		 }
	}
      // Destructor
     ~DiaGraph() {
	for (int i = 0; i < N; i++)
 		delete[] head[i];
		delete[] head;
     }
};
// print all adjacent vertices of given vertex
void display_AdjList(adjNode* ptr, int i)
{
	while (ptr != nullptr) {
		cout << "(" << i << ", " << ptr->val
			<< ", " << ptr->cost << ") ";
		ptr = ptr->next;
	}
	cout << endl;
}
// graph implementation
int main()
{
	// graph edges array.
	graphEdge edges[] = {
		// (x, y, w) -> edge from x to y with weight w
		{0,1,2},{0,2,4},{1,4,3},{2,3,2},{3,1,4},{4,3,3}
	};
	int N = 6;      // Number of vertices in the graph
	// calculate number of edges
	int n = sizeof(edges)/sizeof(edges[0]);
	// construct graph
	DiaGraph diagraph(edges, n, N);
	// print adjacency list representation of graph
	cout<<"Graph adjacency list "<<endl<<"(start_vertex, end_vertex, weight):"<<endl;
	for (int i = 0; i < N; i++)
	{
		// display adjacent vertices of vertex i
		display_AdjList(diagraph.head[i], i);
	}
	return 0;
}

Output:

Output:

Graph adjacency list

(start_vertex, end_vertex, weight):

(0, 2, 4) (0, 1, 2)

(1, 4, 3)

(2, 3, 2)

(3, 1, 4)

(4, 3, 3)

Graph Output

Applications Of Graphs

Let us discuss some of the applications of graphs.

  • Graphs are used extensively in computer science to depict network graphs, or semantic graphs or even to depict the flow of computation.
  • Graphs are widely used in Compilers to depict allocation of resources to processes or to indicate data flow analysis, etc.
  • Graphs are also used for query optimization in database languages in some specialized compilers.
  • In social networking sites, graphs are main the structures to depict the network of people.
  • Graphs are extensively used to build the transportation system especially the road network. A popular example is Google maps that extensively uses graphs to indicate directions all over the world.

Conclusion

A graph is a popular and extensively used data structure which has many applications in the computer science field itself apart from other fields. Graphs consist of vertices and edges connecting two or more vertices.

A graph can be directed or undirected. We can represent graphs using adjacency matrix which is a linear representation as well as using adjacency linked list. We also discussed the implementation of the graph in this tutorial.

=> See Here To Explore The Full C++ Tutorials list.