Number of Linked list for node n in a graph is

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.

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.

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.

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

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.

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.

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.

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.

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.

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.

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