DEV Community

Cover image for Graph (DSA - 7)
Madhav Ganesan
Madhav Ganesan

Posted on

1 1 1 1 1

Graph (DSA - 7)

Definition:

It is a non linear data structure used to represent relationships between nodes(vertices) through edges(links)

Formulas

No of Edges: n*(n-1)/2

Types of Graphs:

1) Undirected
Edges have no direction. The connection between any two vertices is bidirectional.

A -- B
|    |
C -- D
Enter fullscreen mode Exit fullscreen mode

2) Directed Graph (Digraph):
Edges have a direction. The connection between any two vertices is unidirectional.

A -> B
    
C <- D
Enter fullscreen mode Exit fullscreen mode

3) Weighted Graph
Edges have weights (or costs) associated with them.

A --2-- B
Enter fullscreen mode Exit fullscreen mode

4) Cyclic Graph:

A -- B
|    |
C -- D
Enter fullscreen mode Exit fullscreen mode

5) Acyclic Graph
Does not contain any cycles.

A -> B

C -> D
Enter fullscreen mode Exit fullscreen mode

6) Directed Acyclic Graph (DAG)

A -> B
 
C -> D
Enter fullscreen mode Exit fullscreen mode

7) Connected Graph
A graph is said to be connected if there is a path between every pair of vertices. In other words, every vertex is reachable from every other vertex.

  A ---- B
  |      |
  D ---- C
  |
  E
Enter fullscreen mode Exit fullscreen mode

8) Disconnected Graph
A graph is said to be disconnected if it is not connected, meaning there exist at least two vertices such that there is no path between them.

  A      B
   \    / \
    C  D   E
Enter fullscreen mode Exit fullscreen mode

9) Complete Graph
A complete graph is a type of graph in which every pair of distinct vertices is connected by a unique edge. If a complete graph has n vertices, it has (n(n−1))/2 edges, as every vertex is connected to every other vertex exactly once.

  A ---- B
  |\    /|
  | \  / |
  |  \/  |
  |  /\  |
  | /  \ |
  |/    \|
  D ---- C
Enter fullscreen mode Exit fullscreen mode

10) Bipartite Graph
A bipartite graph is a type of graph whose vertices can be divided into two disjoint sets U and V such that no two vertices within the same set are adjacent. The edges only connect vertices from different sets.
Sets of vertices: U={A,B}, V={C,D,E}
Edges: (A,C),(A,D),(B,D),(B,E)

  A      B
  |\    /|
  | \  / |
  |  \/  |
  |  /\  |
  | /  \ |
  C      D
   \    /
    \  /
     E
Enter fullscreen mode Exit fullscreen mode

Graph Representation

1) Adjacency List:

A -- B
|    |
C -- D
Enter fullscreen mode Exit fullscreen mode
A: [B, C]
B: [A, D]
C: [A, D]
D: [B, C]
Enter fullscreen mode Exit fullscreen mode

SC: O(2E)

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n = 5; // Number of vertices
    vector<int> adj[n]; // Adjacency list for the graph

    // Adding edges to the graph
    adj[0].push_back(1); // Edge from vertex 0 to vertex 1
    adj[0].push_back(4); // Edge from vertex 0 to vertex 4
    adj[1].push_back(2); // Edge from vertex 1 to vertex 2
    adj[1].push_back(3); // Edge from vertex 1 to vertex 3
    adj[2].push_back(3); // Edge from vertex 2 to vertex 3
    adj[3].push_back(4); // Edge from vertex 3 to vertex 4

    // Print the adjacency list
    for (int i = 0; i < n; ++i) {
        cout << "Adjacency list of vertex " << i << ": ";
        for (int v : adj[i]) {
            cout << v << " ";
        }
        cout << endl;
    }

    return 0;
}
Enter fullscreen mode Exit fullscreen mode

2) Adjacency Matrix:

A -- B
|    |
C -- D
Enter fullscreen mode Exit fullscreen mode
  A B C D
A 0 1 1 0
B 1 0 0 1
C 1 0 0 1
D 0 1 1 0
Enter fullscreen mode Exit fullscreen mode
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n = 5; // Number of vertices
    vector<vector<int>> adjMatrix(n, vector<int>(n, 0)); 

    // Adding edges to the graph
    adjMatrix[0][1] = 1; // Edge from vertex 0 to vertex 1
    adjMatrix[0][4] = 1; // Edge from vertex 0 to vertex 4
    adjMatrix[1][0] = 1; // Edge from vertex 1 to vertex 0
    adjMatrix[1][2] = 1; // Edge from vertex 1 to vertex 2
    adjMatrix[1][3] = 1; // Edge from vertex 1 to vertex 3
    adjMatrix[2][1] = 1; // Edge from vertex 2 to vertex 1
    adjMatrix[2][3] = 1; // Edge from vertex 2 to vertex 3
    adjMatrix[3][1] = 1; // Edge from vertex 3 to vertex 1
    adjMatrix[3][2] = 1; // Edge from vertex 3 to vertex 2
    adjMatrix[3][4] = 1; // Edge from vertex 3 to vertex 4
    adjMatrix[4][0] = 1; // Edge from vertex 4 to vertex 0
    adjMatrix[4][3] = 1; // Edge from vertex 4 to vertex 3

    return 0;
}
Enter fullscreen mode Exit fullscreen mode

SC: O(n2)

Transpose

The transpose (reverse) of a directed graph G, denoted as GT, is a graph that has the same set of vertices as G but all the edges are reversed.

Graph G

  A  B
     
  C  D
Enter fullscreen mode Exit fullscreen mode

Graph GT

  A  B
     
  C  D
Enter fullscreen mode Exit fullscreen mode

Degree of a Vertex

The degree of a vertex is the number of edges connected to it. For a vertex v, the degree is denoted as deg(v).

Sum of degrees = 2 * |E|

In-Degree: The number of edges coming into a vertex.
Out-Degree: The number of edges going out from a vertex.

Common Graph Algorithms

Depth-First Search (DFS):
DFS explores as far as possible along each branch before backtracking.

#include <iostream>
#include <vector>

using namespace std;

void DFS(int v, vector<bool>& visited, const vector<vector<int>>& adjList) {
    visited[v] = true;
    cout << v << " ";

    for (int u : adjList[v]) {
        if (!visited[u]) {
            DFS(u, visited, adjList);
        }
    }
}

int main() {
    int V = 5; // number of vertices
    vector<vector<int>> adjList(V);

    // Example graph
    adjList[0] = {1, 2};
    adjList[1] = {0, 3, 4};
    adjList[2] = {0};
    adjList[3] = {1};
    adjList[4] = {1};

    vector<bool> visited(V, false);

    cout << "DFS starting from vertex 0:" << endl;
    DFS(0, visited, adjList);

    return 0;
}
Enter fullscreen mode Exit fullscreen mode

Ex. No of islands

void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int i, int j) {
    // Base cases
    if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] == 0 || visited[i][j])
        return;

    // Mark the cell as visited
    visited[i][j] = true;

    // Explore all 4 directions
    dfs(grid, visited, i + 1, j);
    dfs(grid, visited, i - 1, j);
    dfs(grid, visited, i, j + 1);
    dfs(grid, visited, i, j - 1);
}

int numIslands(vector<vector<int>>& grid) {
    if (grid.empty()) return 0;
    int rows = grid.size();
    int cols = grid[0].size();
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));
    int count = 0;

    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (grid[i][j] == 1 && !visited[i][j]) {
                // Start a DFS from this cell
                dfs(grid, visited, i, j);
                count++;
            }
        }
    }

    return count;
}
Enter fullscreen mode Exit fullscreen mode

Breadth-First Search (BFS)/Level wise:
Explores all neighbors at the present depth before moving on to nodes at the next depth level.

Image description

Image description

        queue<int> q;
        vector<int> visit(V,0);
        visit[0]=1;
        q.push(0);
        vector<int> res;

        while(!q.empty()){
            int node=q.front();
            q.pop();
            res.push_back(node);

            for(auto it: adj[node]){
                if(visit[it]!=1){
                    visit[it]=1;
                    q.push(it);
                }
            }
        }
        return res;
Enter fullscreen mode Exit fullscreen mode
void bfs(const vector<vector<int>>& adjacencyMatrix, int startVertex) {
    int numVertices = adjacencyMatrix.size();
    vector<bool> visited(numVertices, false);
    queue<int> q;

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

    while (!q.empty()) {
        int currentVertex = q.front();
        q.pop();
        cout << currentVertex << " ";

        for (int i = 0; i < numVertices; ++i) {
            if (adjacencyMatrix[currentVertex][i] == 1 && !visited[i]) {
                visited[i] = true;
                q.push(i);
            }
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

Dijkstra's Algorithm:
Finds the shortest path between nodes in a graph with weighted edges.

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

void Dijkstra(int src, const vector<vector<pair<int, int>>>& adjList) {
    int V = adjList.size();
    vector<int> dist(V, INT_MAX);
    dist[src] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, src});

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        for (auto& neighbor : adjList[u]) {
            int v = neighbor.first;
            int weight = neighbor.second;

            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }

    cout << "Vertex \t Distance from Source\n";
    for (int i = 0; i < V; ++i) {
        cout << i << " \t\t " << dist[i] << "\n";
    }
}

int main() {
    int V = 5; // number of vertices
    vector<vector<pair<int, int>>> adjList(V);

    // Example graph
    adjList[0] = {{1, 10}, {4, 3}};
    adjList[1] = {{0, 10}, {2, 2}};
    adjList[2] = {{1, 2}, {3, 9}};
    adjList[3] = {{2, 9}, {4, 2}};
    adjList[4] = {{0, 3}, {3, 2}};

    cout << "Dijkstra's shortest path starting from vertex 0:\n";
    Dijkstra(0, adjList);

    return 0;
}
Enter fullscreen mode Exit fullscreen mode

Minimum Spanning Tree

A Minimum Spanning Tree (MST) is a subset of the edges of a connected, weighted, and undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. There are two well-known algorithms for finding the MST of a graph: Kruskal's algorithm and Prim's algorithm.

Kruskal's Algorithm:
Finds the minimum spanning tree of a graph.

Prim's Algorithm:
Another algorithm to find the minimum spanning tree of a graph.

Floyd-Warshall Algorithm
It is used to find the shortest paths between all pairs of vertices in a weighted graph. It can handle negative weights but not negative weight cycles.

Bellman-Ford Algorithm
It is used to find the shortest paths from a single source vertex to all other vertices in a weighted graph. It can handle negative weights and detect negative weight cycles.

Topological Sorting:
Topological sorting is used for ordering vertices in a directed acyclic graph (DAG)

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

void topologicalSortUtil(int v, vector<bool>& visited, stack<int>& Stack, const vector<vector<int>>& adjList) {
    visited[v] = true;

    for (int u : adjList[v]) {
        if (!visited[u]) {
            topologicalSortUtil(u, visited, Stack, adjList);
        }
    }

    Stack.push(v);
}

void topologicalSort(const vector<vector<int>>& adjList) {
    stack<int> Stack;
    vector<bool> visited(adjList.size(), false);

    for (int i = 0; i < adjList.size(); i++) {
        if (!visited[i]) {
            topologicalSortUtil(i, visited, Stack, adjList);
        }
    }

    while (!Stack.empty()) {
        cout << Stack.top() << " ";
        Stack.pop();
    }
}

int main() {
    int V = 6; // number of vertices
    vector<vector<int>> adjList(V);

    // Example graph
    adjList[5] = {2, 0};
    adjList[4] = {0, 1};
    adjList[3] = {1};
    adjList[2] = {3};
    adjList[1] = {};
    adjList[0] = {};

    cout << "Topological Sort of the graph:\n";
    topologicalSort(adjList);

    return 0;
}
Enter fullscreen mode Exit fullscreen mode

Important Questions

1) Search in BST

    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) {
            return root;
        }

        if (root.val ==  val) {
            return root;
        }

        if (root.val < val) {
            return searchBST(root.right, val);
        } else {
            return searchBST(root.left, val);
        }
    }
Enter fullscreen mode Exit fullscreen mode

2) Ceil in BST

int findCeil(Node* root, int input) {

    int ceil=-1;
    while(root){
        if(root->data==input){
            return root->data;
        }
        if(input>root->data){
            root=root->right;
        }
        else{
            ceil=root->data;
            root=root->left;
            }
    }
    return ceil;
}
Enter fullscreen mode Exit fullscreen mode

Stay Connected!
If you enjoyed this post, don’t forget to follow me on social media for more updates and insights:

Twitter: madhavganesan
Instagram: madhavganesan
LinkedIn: madhavganesan

Image of Datadog

Create and maintain end-to-end frontend tests

Learn best practices on creating frontend tests, testing on-premise apps, integrating tests into your CI/CD pipeline, and using Datadog’s testing tunnel.

Download The Guide

Top comments (1)

Collapse
 
hys01 profile image
ys01

incredibly helpful, thanks!!

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up