Graph and its types

In C++, graphs are a way of representing a set of objects where some pairs of objects are connected (or 'related') to each other. A graph can be thought of as a collection of vertices (nodes) and edges. The edges connect the vertices and represent the relationships between them.

There are two main ways of representing a graph in C++: adjacency matrix and adjacency list.

An adjacency matrix is a 2D array where each row and column represent a vertex in the graph. The value in cell matrix[i][j] represents whether there is an edge between vertex i and vertex j. If there is an edge, the value will be the weight of the edge. If there is no edge, the value will be a special value (often -1 or 0).

An adjacency list is a vector (or array) of linked lists, where each linked list represents the vertices that are adjacent to a particular vertex. For example, adj_list[i] represents the list of vertices that are adjacent to vertex i.

Using these representations, we can perform various operations on the graph such as traversals (e.g. Breadth-First Search, Depth-First Search), finding shortest paths (e.g. Dijkstra's Algorithm), and finding Minimum Spanning Trees (e.g. Kruskal's Algorithm).

There are several types of graphs in C++ which are defined by the nature of their edges and vertices. Here are some of the most common types of graphs and their implementation in C++.

Undirected Graphs: An undirected graph is a graph in which each edge is bi-directional. An edge represents a connection between two vertices and can be traversed in both directions.

Implementation:

We can represent an undirected graph as an adjacency list in C++. Here is a basic implementation using a vector of STL to represent the adjacency list.


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

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> graph(n + 1);

    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    return 0;
}

Directed Graphs: A directed graph is a graph in which each edge is uni-directional. The edge represents a connection between two vertices that can be traversed only in a single direction.

Implementation:

We can represent a directed graph as an adjacency list in C++. Here is a basic implementation using a vector of STL to represent the adjacency list.


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

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> graph(n + 1);

    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
    }
    return 0;
}

Weighted Graphs: A weighted graph is a graph in which each edge has a weight associated with it. It can be either an undirected or directed graph.

Implementation:

We can represent a weighted graph as an adjacency list of tuples in C++. Here is a basic implementation using a vector of STL to represent the adjacency list.


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

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<tuple<int, int>>> graph(n + 1);

    for (int i = 0; i < m; ++i) {
        int a, b, w;
        cin >> a >> b >> w;
        graph[a].emplace_back(make_tuple(b, w));
        graph[b].emplace_back(make_tuple(a, w));
    }

   return 0;
}

Tree Graphs: A tree graph is a connected and acyclic graph. It is a type of undirected graph where there is exactly one path between any two vertices.

Implementation:

We can represent a tree graph using an adjacency list in C++. Here is a basic implementation using a vector of STL to represent the adjacency list.


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

int main() {
    int n;
    cin >> n;
    vector<vector<int>> graph(n + 1);

    for (int i = 2; i <= n; i++) {
        int x;
        cin >> x;
        graph[x].push_back(i);
    }
    return 0;
}

These are some of the most common types of graphs. We can implement each type using different approaches. The most common implementation is using an adjacency list or adjacency matrix.

TRAVERSAL IN A GRAPH:

Traversing a graph means visiting each of the vertices (nodes) in the graph exactly once. We can traverse the graph by using two algorithms: Breadth-First Search (BFS) and Depth-First Search (DFS). The main difference between these two algorithms is the order in which they visit the vertices in the graph.

Breadth-First Search (BFS): Breadth-First Search (BFS) is an algorithm used for traversing or searching a graph. It traverses the graph in a breadth-first order (i.e., it visits all the vertices at a particular depth first, before moving onto the vertices at the next depth).

Algorithm:

Create a queue and enqueue the starting vertex into it

Mark the starting vertex as 'visited'

While the queue is not empty, do the following:

Dequeue a vertex from the queue

Visit all the adjacent (unvisited) vertices of the dequeued vertex

Mark each adjacent vertex as 'visited' and enqueue it into the queue

Implementation:

We can implement BFS using a queue in C++. Here is a basic implementation for an unweighted graph using an adjacency list.


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

void bfs(int start, vector<int> adj[], bool visited[]) {
    queue<int> q;

    q.push(start);
    visited[start] = true;

    while(!q.empty()) {
        int curr = q.front();
        q.pop();

        cout << curr << " ";

        for(auto neighbour: adj[curr]) {
            if(!visited[neighbour]) {
                visited[neighbour] = true;
                q.push(neighbour);
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    /* adjacency list */
    vector<int> adj[n+1];

    /* initializing visited array */
    bool visited[n+1];
    for(int i = 1; i <= n; i++) {
        visited[i] = false;
    }

    /* adding edges */
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    /* BFS traversal */
    bfs(1, adj, visited);

    return 0;
}

Depth-First Search (DFS): Depth-First Search (DFS) is an algorithm used for traversing or searching a graph. It traverses the graph in a depth-first order (i.e., it explores as far as possible along each branch before backtracking).

Algorithm:

Mark the starting vertex as 'visited'

Visit all the adjacent (unvisited) vertices of the starting vertex

Repeat step 2 for each unvisited vertex until all vertices have been visited

Implementation:

We can implement DFS using recursion or a stack in C++. Here is a basic implementation for an unweighted graph using an adjacency list and recursion.


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

void dfs(int start, vector<int> adj[], bool visited[]) {
    visited[start] = true;

    cout << start << " ";

    for(auto neighbour : adj[start]) {
        if(!visited[neighbour]) {
            dfs(neighbour, adj, visited);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    /* adjacency list */
    vector<int> adj[n+1];

    /* initializing visited array */
    bool visited[n+1];
    for(int i = 1; i <= n; i++) {
        visited[i] = false;
    }

    /* adding edges */
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    /* DFS traversal */
    dfs(1, adj, visited);

    return 0;
}

In summary, traversing a graph is important for understanding and processing the graph's structure and information. We can perform graph traversal using two popular algorithms, BFS and DFS, which have different characteristics in visiting the vertices.

PRACTICE PROBLEMS :

Clone Graph

Is Graph Bipartite?