DEV Community

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

Posted on

Graph (DSA - 7)

#cpp #leetcode #dsa #beginners

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!!