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