Table of Contents:

  1. Graph Representation
  2. Graph Terminologies
  3. Applications of Graph
  4. Advantages of Using Graphs in C++
  5. Disadvantages of Using Graphs in C++

Directed & In-Directed 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.

Graph C++

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:

  1. Adjacency Matrix
  2. 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.

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 the weighted graphs. In this case, the weights of the edges are stored as the lists of pairs.

Example

Following is an example of an undirected graph and its Adjacency List.

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.

C++ Directed Graph

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.

C++ Indirected Graph

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

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)

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.