Table of Contents:
- Graph Representation
- Types of Representation
- Types of Graphs
- Graph Terminologies
- C++ Graph Implementation
- Applications of Graph
- Advantages of Using Graphs in C++
- Disadvantages of Using Graphs in C++
Graph Representation
A graph is a non-linear data form. A graph is a set of nodes often referred to as “vertices” and “edges” that bind two or more vertices.
A graph may also represent a cyclic tree in which vertices do not have a relationship between parent and child but retain a dynamic relationship.
above is an example graph. Graph is a set of vertices {P,Q,R,S,T} and a set of edges {(P,Q),(Q,R),(P,S),(S,T),(T,R),(Q,T),(Q,S)}.
The vertices are set as boxes or circles, and drawing the edges are set as lines or arcs between boxes or circles.
Types of Representation
The graph representation indicates a pattern in which the memory registers the relevant data structure. Usually, there are two types in which the memory stores the graphs. Following are the types of graph representation:
- Adjacency Matrix
- Adjacency List
There can also be other graph representations, for example, the Incidence Matrix and the Incidence List. However, the representation of the graph entirely depends upon the underlying situation. Hence the situation-specific representation helps in carrying out the required operations without complexity.
Adjacency Matrix
Adjacency Matrix is also known as the sequential representation of the graph. Adjacency Matrix is like a 2D array. If there are N vertices in a graph, then the size of the array is N*N. The rows and columns in the adjacency matrix are responsible for representing the vertices in a graph. If there is an edge between two vertices, then number 1 represents the edge as the matrix element. However, if there is no edge between the graph’s vertices, the element is set to 0 for simplification.
Example
Following is an example of an undirected graph and its Adjacency Matrix.
As the above-shown graph is undirected, it is safe to assume that the edge between any two vertices is present in both directions. For example, there is an edge between vertices A and B. Therefore, the elements AB and BA are labeled as number 1. Similarly, there is no edge between vertices A and E. Therefore, the elements AE and EA are 0. This assumption is similar for all other vertices.
Adjacency List
Adjacency List is also known as the linked representation of a graph. An array of lists represents the graph, and the size of that array equals the number of present vertices. This representation carries each vertice of the graph and a link to its adjacent vertices. After the complete traversal, the next pointer is set to null at the end of the list. Moreover, the linked representation is also helpful while working with weighted graphs. In this case, the weights of the edges are stored as lists of pairs.
Example
Following is an example of an undirected graph and its Adjacency List.
The above graph possesses a linked list or an adjacency list for each of its vertices. For example, there are edges from vertex A to vertices B, C, and D. Therefore, there is a link between these vertices of the adjacency list corresponding to A; moreover, after the traversal completes after vertex D, so the next pointer is set to null at the end.
Types of Graphs
Directed Graph
It is a set of vertices (nodes) linked by edges, with a path connected with each node. Typically, edges may represent by arrows pointing in the direction in which the graph crosses.
The graph may traverse from vertex ‘A’ -> ‘B’ in the illustration on the right, but not from vertex B -> A.
Edges form an ordered pair in the directed graph seen above, wherein each edge represents a particular path from one vertex to another vertex. The vertex that the path initiates from is considered the “Original Node.” Whereas the vertex where the path ends is called the “Terminal Node.”
Undirected Graph
The edges are bidirectional in an undirected graph, with no path connected with them. The graph should, thus, traverses in any direction. An arrow’s absence informs us that the graph is undirected.
Graph Terminologies
Vertex: Each graph node is called a vertex. X Y, Z, and D are the vertices of the graph in the graph above.
Edge: An edge is considered the link or path between two vertices. It connects two vertices or more. AB, BC, AD, and DC are the multiple edges in the graph above.
Adjacent node: If an edge joins two nodes, it refers to adjacent nodes or neighbors in a graph. Edge AB in the above table relates vertices A and B. So, A and B are neighboring nodes.
Degree of the node: The degree of the node is called the number of edges. It is related to a particular node. Node A has a degree of 2 in the above table.
Path: The path is called the chain of nodes. Users need to pursue when moving in a graph from a vertex to another. If the user needs to go from node A to C in our example list, then the path is, A->B->C.
Closed path: If the initial node is similar to the terminal node, it is considered the closed path.
Simple path: A closed path is considered a simple path through which all the other nodes are separate.
Cycle: A cycle is considered a path along which there are no repeating edges or vertices, and the first and last vertices are similar. A->B->C->D->A in the above graph is a cycle.
Connected Graph: Itis the one between the vertices where there is a path. It suggests that a single vertex is not alone or without a linking edge. A related graph is the graph shown above.
Complete Graph: A graph that links each node to another is called the Complete Graph. If M is the total number of nodes in a graph, then N(N-1)/2 is the number of edges in the complete graph.
Weighted graph: The positive value assigned to each edge representing its length is called weight (the distance between the vertices bound by the edge). A weighted graph is considered a graph with weighted edges. An edge’s weight is denoted by w(e) and shows the expense of crossing an edge.
Diagraph: It is a graph in which a particular direction connects with each edge, and the transformation can only be achieved in a given direction.
C++ Graph Implementation
Below is the implementation of a graph using the adjacency List and adjacency matrix in C++.
1. Graph Implementation C++ – Adjacency List
A C++ execution to illustrate a basic graph using the adjacency list is below. For a weighted directional graph, the user can display the adjacency list here. There are two constructs to carry the graph’s adjacency list and edges. The adjacency list is: (start vertex, weight, end vertex).
#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
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)
2. Graph Implementation Using Adjacency Matrix C++
Below is the coding example of an undirected graph using the adjacency matrix in C++. The user begins by including the necessary libraries, such as “iostream.” Then, he declares a class named “Graph” to create and manage the user-defined graphs. The class has two private variables to store the adjacency matrix and the vertex count. Moreover, it has public functions to initialize the graph, add edges, remove edges and print them on the user’s screen.
Graph Functions
Below are the public functions of the graph class:
1. Constructor
The class’s constructor takes the number of vertices as its parameter and declares the 2-day array or matrix to store the values. Initially, it sets all the indices to zero or false.
2. Add Edge Function
The add edges function takes the starting and ending vertices of an edge to add an edge between the two vertices. For instance, the edge between vertex “1” and ”2” means that the function should modify the value of “matrix[1][2]” and “matrix[2][1]” to be “true” or “one.” The graph is undirected; therefore, if there is a path from vertex “1” to vertex “2”, then there is a path from vertex “2” to vertex “1” as well.
3. Remove Edge Function
The remove function works on the same principle as the add edge function. It takes an edge’s starting and ending vertices and removes the path by modifying the indices to false or zero.
4. Print Graph Function
The print graph function prints the graph using the private variables of the class. It runs the nested loop to the number of vertices and prints the whole matrix on the user’s screen.
Main Function
The user declares the graph with pre-defined vertex numbers. He then adds the edges to the graph using the “addEdge” function and prints the graph using the “printGraph” function.
Note: In this example, the user tells the number of vertices beforehand; therefore, the graph class declares the matrix accordingly. However, the users can use the link-list of link-list, i.e., hashmap, to implement the graph in which the user has not pre-defined the vertex number and create the new nodes whenever the user adds the new vertex.
Code
Below is the C++ code to implement the graph by adjacency matrix:
// Adjacency Matrix representation in C++
#include <iostream>
using namespace std;
class Graph {
private:
bool** adjMatrix;
int numVertices;
public:
// Initialize the matrix to zero
Graph(int numVertices) {
this->numVertices = numVertices;
adjMatrix = new bool*[numVertices];
for (int i = 0; i < numVertices; i++) {
adjMatrix[i] = new bool[numVertices];
for (int j = 0; j < numVertices; j++)
adjMatrix[i][j] = false;
}
}
// Add edges
void addEdge(int i, int j) {
adjMatrix[i][j] = true;
adjMatrix[j][i] = true;
}
// Remove edges
void removeEdge(int i, int j) {
adjMatrix[i][j] = false;
adjMatrix[j][i] = false;
}
// Print the martix
void printGraph() {
for (int i = 0; i < numVertices; i++) {
cout << i << " : ";
for (int j = 0; j < numVertices; j++)
cout << adjMatrix[i][j] << " ";
cout << "\n";
}
}
};
int main() {
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.printGraph();
}
Output
Below is the output of the above coding example, i.e., the adjacency matrix:
0: 0 1 1 0 1: 1 0 1 0 2: 1 1 0 0 3: 0 0 2 0
Directed Graph using the Above Example
The users can create a directed graph by not creating the double paths in the addEdge function and similarly not removing the double edges in the removeEdge function.
Applications of Graph
In computer science, graphs are widely used to represent network graphs, semantic graphs, or even illustrate computational flow.
Graphs are used in Compilers to depict resource allocation to processes or indicate data flow analysis.
It extensively creates the transportation infrastructure, especially the road network. Google maps that widely use graphs to indicate directions all over the world are a typical example.
Graphs are critical mechanisms for describing the network of entities on social networking sites.
Advantages of Using Graphs in C++
It adapts easily to different kinds of graphs.
Graphs are efficient in access and accessible in the representation of the data.
Disadvantages of Using Graphs in C++
Requires that graph access be a Command rather than a computation.
Vertices’ domain must be a form that exists in an array as an index.
A graph is a standard and widely used data form that, apart from other areas, has many uses in computer science. Graphs consist of vertices and edges where two or more vertices are connected. It is possible to steer or undirect a graph. Using the adjacency matrix, which is a linear representation, the user represents graphs using the adjacency-connected list.
