Introduction
Graphs represent relationship between objects - consists of
Nodes (a.k.a Vertices) and
Edges.
Edges could be:
- weighted or unweighted.
- directed or undirected.
Graphs could be:
- cyclic
- acyclic
- a tree
How to represent Graphs?
-
adjacency matrix: build a 2D matrix (N * N) and insert weight of matrix if node i & node j have a edge
Look up time: O(1)
Space: O(N*N)
-
adjacency list: build list of size N. ith node will contain all its edges as a list element
Look up time: O(N)
Space: O(N+E)
Graph Traversals:
- bfs : can be done with a queue data structure
- dfs: can be done with recursion or using stack data structure
Selected Graph Algorithms:
Minimum Spanning Tree: min(sum of edges) such that all the nodes are visited.
- edges are undirected & all nodes are connected
- MST is not unique: there can be many MST for a particular Graph
a. Kruskal's Algorithm for finding MST: greedily add the lowest edge weight to the spanning tree
Algorithm:
- sort edge weights and add one by one to MST
- only add edge if there is no cycle (edges that connect unvisited nodes)
How to check if there is no cycle in graph? Optimized ans: Union Find.
Implementation:
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
// find common ancestor which represents a set
int find (int x, vector<int> &parent) {
return parent[x] == x ? x : find(parent[x], parent);
}
int kruskal (vector<vector<int>> &G, int n) {
int edges = G.size();
int x, y, cost, mincost = 0;
// Step1: sort edge according to weights/cost to add one by one to MST
sort(G.begin(), G.end(), [](vector<int> a, vector<int> b) { return a[2] < b[2];});
//initialize parent vector for union find
vector<int> parent (n,0);
for(int i = 0; i < n; i++) {
parent[i] = i;
}
//iterate through the edge list from lowest to highest cost
for(int i = 0; i < edges; i++) {
x = G[i][0];
y = G[i][1];
cost = G[i][2];
int a = find(x-1, parent);
int b = find(y-1, parent);
//check if a cycle is formed using union find. If yes, don't add.
if(a != b) {
mincost += cost;
parent[a] = b;
}
}
return mincost;
}
int main() {
// initialize the graph for MST
// {vertexi, vertexj, cost/weight}
vector<vector<int>> MST = {{1,2,7},{1,4,6},{4,2,9},{4,3,8},{2,3,6}};
int MST_nodes = 4;
cout << "Kruskal MST size = " << kruskal(MST, MST_nodes);
}
Time complexity: sorting the elements is O(NlogN) or overall complexity of Union find which is O(ElogV)
b. Prim's Algorithm for finding MST: same greedy approach as Kruskal, but instead of edge add vertex.
Algorithm:
- keep 2 sets of vertices - one part of growing MST, other that doesn't belong
- select vertices from the lowest edge first and add it to MST, then find the connecting next cheapest to visit vertex and add it to the MST, ensuring there are no cycles. (priority queue sorted by edge weight)
Implementation:
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
vector<vector<pair<int,int>>> convertEdgeListToAdjacencyList (vector<vector<int>> &G, int n) {
// n is vertices
vector<vector<pair<int, int>>> adj (n);
int edges = G.size();
for(int i = 0; i < edges; i++) {
adj[G[i][0]-1].push_back({G[i][2], G[i][1]-1});
adj[G[i][1]-1].push_back({G[i][2], G[i][0]-1});
}
return adj;
}
int prim (vector<vector<int>> &G, int n) {
int edges = G.size();
/*
// Step1: find smallest edge - no need to sort
int minedge = INT_MAX; int x = 0, y = 0;
for(int i = 0; i < edges; i++) {
if(G[i][2] < minedge) {
minedge = G[i][2];
x = G[i][0];
y = G[i][1];
}
}
*/
vector<vector<pair<int, int>>> adj = convertEdgeListToAdjacencyList (G, n);
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
int x = 0, y = 0, mincost = 0;
vector<bool> visited (n, 0);
q.push({0,1}); // start from a random vertex and go from there, also assign it 0 weight
while(!q.empty()) {
pair<int,int> p = q.top(); //select the item with lowest weight
q.pop();
x = p.second;
// check for cycle by checking visited
if(visited[x]) continue;
mincost += p.first;
visited[x] = 1;
for(int i = 0; i < adj[x].size(); i++) {
int cost = adj[x][i].first;
y = adj[x][i].second;
if(!visited[y]) q.push({cost,y});
}
}
return mincost;
}
int main() {
// initialize the graph for MST
// {vertexi, vertexj, cost/weight}
vector<vector<int>> MST = {{1,2,7},{1,4,6},{4,2,9},{4,3,8},{2,3,6}};
int MST_nodes = 4;
cout << "Prim's MST size = " << prim(MST, MST_nodes) << endl;
}
Time complexity: priority queue insertion is logN time and iterating thru all edges and vertices. Total: O((V+E) logV).