Graph Data Structure in C++.

A graph is a data structure that is used to represent a collection of interconnected objects, called vertices or nodes, and the connections between them, called edges.

Vertex (or Node): A vertex represents a single entity in the graph, such as a person in a social network or a city in a transportation network.
Edge: An edge represents a connection between two vertices, such as a friendship between two people or a road between two cities.

Let's understand graphs through an example, Social networks are a collection of individuals or entities, connected by various relationships or interactions, such as friendships, followings, and likes.

A social network can be represented using a graph, where each individual or entity is represented as a node, and each relationship or interaction is represented as an edge.

Graph Important Terminology.

Directed Graph: A directed graph is a graph in which each edge has a direction associated with it, indicating the flow or direction of the connection between the vertices.

Undirected Graph: An undirected graph is a graph in which each edge does not have a direction associated with it, indicating that the connection between the vertices is bidirectional.

Weighted Graph: A weighted graph is a graph in which each edge has a weight or cost associated with it, indicating the strength or importance of the connection between the vertices.

Degree: The degree of a vertex is the number of edges connected to it. In a directed graph, the degree is further divided into in-degree and out-degree, which represent the number of incoming and outgoing edges, respectively.

Path: A path in a graph is a sequence of vertices and edges that connects two vertices. The length of a path is the number of edges in the path.

Cycle: A cycle is a path in a graph that starts and ends at the same vertex.

Connected Graph: A connected graph is a graph in which there is a path between every pair of vertices.

Spanning Tree: A spanning tree is a subset of the edges in a graph that connects all vertices without forming a cycle.

Graph Representation.

There are two common ways to represent a graph data structure: the adjacency list and the adjacency matrix.

Adjacency Matrix.

In the adjacency matrix representation, we use a two-dimensional array for size VxV to represent the edges between vertices. The value at matrix[i][j] represents the weight or existence of the edge between vertices i and j.

C++ Code to Print the Adjacent Matrix of the above graph.

#include <iostream>
using namespace std;

const int MAX_SIZE = 100;
int adj_matrix[MAX_SIZE][MAX_SIZE];

int main() {
    int n, m; // n: number of vertices, m: number of edges
    cin >> n >> m;
    
    // initialize adjacency matrix
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            adj_matrix[i][j] = 0;
        }
    }
    
    // add edges to the graph
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        // since the graph is undirected
        adj_matrix[u][v] = 1;
        adj_matrix[v][u] = 1;
    }
    
    // print adjacency matrix
    cout << "Adjacency matrix:\n";
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << adj_matrix[i][j] << " ";
        }
        cout << "\n";
    }
    
    return 0;
}

Output:

5 6
0 1
0 2
0 4
1 4
1 2
2 3
Adjacency matrix:
0 1 1 0 1
1 0 1 0 1
1 1 0 1 0
0 0 1 0 0
1 1 0 0 0

Adjacency List.

In the adjacency list representation, we store each vertex and its neighbors in a dictionary or hash map. The keys of the dictionary represent the vertices, and the values represent the neighboring vertices as a list or set.

C++ Code to Print the Adjacent List of the above graph.

#include <iostream>
#include <vector>
using namespace std;

const int MAX_SIZE = 100;
vector<int> adj_list[MAX_SIZE];

int main() {
    int n, m; // n: number of vertices, m: number of edges
    cin >> n >> m;
    
    // add edges to the graph
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        // since the graph is undirected
        adj_list[u].push_back(v);
        adj_list[v].push_back(u);
    }
    
    // print adjacency list
    cout << "Adjacency list:\n";
    for (int i = 0; i < n; ++i) {
        cout << i << " -> ";
        for (int j = 0; j < adj_list[i].size(); ++j) {
            cout << adj_list[i][j] << " ";
        }
        cout << "\n";
    }
    
    return 0;
}

Output:

5 6
0 1
0 2
0 4
1 2
1 4
2 3
Adjacency list:
0 -> 1 2 4
1 -> 0 2 4
2 -> 0 1 3
3 -> 2
4 -> 0 1

Advantage of Adjacency Matrix and Adjacency List.

The adjacency list is more memory-efficient for sparse graphs (where the number of edges is much less than the number of vertices) and allows for faster iteration over the neighbors of a vertex.(alert-passed)

The adjacency matrix is more efficient for dense graphs (where the number of edges is close to the number of vertices) and allows for constant-time access to the weight or existence of an edge between any two vertices.(alert-passed)