This content originally appeared on DEV Community and was authored by Madhav Ganesan
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
2) Directed Graph (Digraph):
Edges have a direction. The connection between any two vertices is unidirectional.
A -> B
↑ ↓
C <- D
3) Weighted Graph
Edges have weights (or costs) associated with them.
A --2-- B
4) Cyclic Graph:
A -- B
| |
C -- D
5) Acyclic Graph
Does not contain any cycles.
A -> B
↓
C -> D
6) Directed Acyclic Graph (DAG)
A -> B
↓
C -> D
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
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
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
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
Graph Representation
1) Adjacency List:
A -- B
| |
C -- D
A: [B, C]
B: [A, D]
C: [A, D]
D: [B, C]
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;
}
2) Adjacency Matrix:
A -- B
| |
C -- D
A B C D
A 0 1 1 0
B 1 0 0 1
C 1 0 0 1
D 0 1 1 0
#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;
}
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
Graph GT
A ← B
↓ ↑
C → D
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;
}
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;
}
Breadth-First Search (BFS)/Level wise:
Explores all neighbors at the present depth before moving on to nodes at the next depth level.
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;
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);
}
}
}
}
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;
}
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;
}
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);
}
}
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;
}
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
This content originally appeared on DEV Community and was authored by Madhav Ganesan
Madhav Ganesan | Sciencx (2024-09-20T16:05:23+00:00) Graph (DSA – 7). Retrieved from https://www.scien.cx/2024/09/20/graph-dsa-7/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.