DEV Community

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

Posted on

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

Top comments (1)

Collapse
 
hys01 profile image
ys01

incredibly helpful, thanks!!