Directed and Undirected Graphs (Implementation)

By LoganGraphs

A graph consists of two sets, namely V (vertices) and E (Edges). V represents a non-empty sets of vertices present in the graph. While E, represents the set of edges (joining two vertices) in the graph.

Implementation

The two most common ways to represent a graph are:

  • Adjacency Matrix
  • Adjacency List

Consider the following graph and its representation in Adjacency Matrix and Adjacency List:

Adjacency Matrix
Fig. 1

Adjacency Matrix a[n][n] is an nxn matrix, where a[i][j] = 1, if there’s an edge between vertices i and j. Also a[i][j] = 0, if there is no edge between vertices (i & j).

Adjacency List
Fig. 2

Adjacency List a[n] is an array of n linked lists, where linked list a[i] represent the vertices connecting the vertex i. For instance,
a[0] (Vertex 1) is connected to the node 2, since there’s an edge between vertex 1 and vertex 2.
Note: We could also use an array of C++ Vector class instead of a linked list.

Directed Graph

In a Directed graph, each edge ie. pair <V1, V2> represent that there’s an edge from V1 to V2 where V1 is the tail and V2 is the head. For instance,

Corresponding Adjacency Matrix & Adjacency List

Undirected Graph

In an Undirected graph, each edge ie. pair <V1, V2> represent that there’s an edge between vertices V1 & V2. This implies that both pair <V1, V2> and pair <V2, V1> are same and both represent that there’s an edge between V1 & V2.
Undirected graph’s representation is shown in Fig.1 and Fig. 2.

Adjacency Matrix Implementation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//
//  main.cpp
//  Adjacency Matrix
//
//  Created by Himanshu on 26/11/22.
//
  
#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
#define N 5
using namespace std;
 
//N = number of nodes in graph
void printAdjacencyMatrix(int G[][N]) {
      
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            cout<<G[i][j]<<" ";
        }
        cout<<endl;
    }
}
 
int main() {
    int G[N][N] = {{0, 1, 0, 0, 0},
                   {1, 0, 0, 1, 0},
                   {0, 0, 0, 1, 1},
                   {0, 1, 1, 0, 1},
                   {0, 0, 1, 1, 0}};
  
      
    cout<<"Graph G (Adjacency Matrix):"<<endl;
    printAdjacencyMatrix(G);
     
    return 0;
}

Output

Graph G (Adjacency Matrix):
0 1 0 0 0 
1 0 0 1 0 
0 0 0 1 1 
0 1 1 0 1 
0 0 1 1 0

Here’s a working example: Adjacency Matrix

Adjacency List Implementation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//
//  main.cpp
//  Adjacency List
//
//  Created by Himanshu on 26/11/22.
//
 
#include <iostream>
#include <vector>
using namespace std;
#define N 5
  
//N = number of nodes in graph
void printAdjacencyList (vector<int> graph[N+1]) {
      
    for (int i=1; i<=N; i++) {
        cout<<i<<": ";
        for (int j=0; j<graph[i].size(); j++) {
            cout<<graph[i][j]<<" ";
        }
        cout<<endl;
    }
}
  
int main() {
    vector<int> graph[N+1];
      
    graph[1].push_back(2);
    graph[2].push_back(1);
    graph[2].push_back(4);
    graph[3].push_back(4);
    graph[3].push_back(5);
    graph[4].push_back(2);
    graph[4].push_back(3);
    graph[4].push_back(5);
    graph[5].push_back(3);
    graph[5].push_back(4);
 
    cout<<"Graph G (Adjacency List):"<<endl;
    printAdjacencyList(graph);
     
    return 0;
}

Output

Graph G (Adjacency List):
1: 2 
2: 1 4 
3: 4 5 
4: 2 3 5 
5: 3 4

Here’s a working example: Adjacency List

Leave a Reply

Your email address will not be published. Required fields are marked *