Itsmdshahin's blog

Basic Graph Theory Short Note
By Itsmdshahin, history, 2 years ago, In English

---

Basic Graph Theory Short Note

1. Complexity of Graph

#Space Complexity:

Adjacency Matrix: O(V^2) — where V is the number of vertices. This is because an adjacency matrix is a 2D array of size V x V.
Adjacency List: O(V + E) — where V is the number of vertices and E is the number of edges. This is because an adjacency list is an array of lists, and each vertex is represented by a list containing its neighbors.


#Time Complexity:
 
Graph Traversal (BFS or DFS): O(V + E) — where V is the number of vertices and E is the number of edges. This is because each vertex and edge is visited once during traversal.
Checking for an Edge (Adjacency Matrix): O(1) — constant time access to the matrix.
Checking for an Edge (Adjacency List): O(degree(V)) — where degree(V) is the number of neighbors of vertex V.
Finding Neighbors (Adjacency Matrix): O(V) — need to iterate over an entire row or column.
Finding Neighbors (Adjacency List): O(degree(V)) — directly accessing the list of neighbors.
Specific Graph Algorithms:
 
Dijkstra's Algorithm: O((V + E) * log(V)) with binary heap or Fibonacci heap.
Bellman-Ford Algorithm: O(V * E).
Floyd-Warshall Algorithm: O(V^3).
Topological Sorting: O(V + E).
Finding Articulation Points and Bridges: O(V + E).
Prim's Algorithm (Minimum Spanning Tree): O((V + E) * log(V)) with a binary heap or Fibonacci heap.
Kruskal's Algorithm (Minimum Spanning Tree): O(E * log(V)) with sorting.-

2. Adjacency Matrix

#include<bits/stdc++.h>
using namespace std;
int g[100][100];
int main() {
    int n, e; cin >> n >> e;
    while(e--) {
        int u, v; cin >> u >> v;
        g[u][v] = 1;
        g[v][u] = 1;
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cout << g[i][j] << " ";
        }
        cout << endl;
    }
    if(g[4][2]) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

3. Adjacency List

#include<bits/stdc++.h>
using namespace std;
const int N = 105;
vector<int> g[N];
int indgr[N], outdgr[N];
int main() {
    int n, e; cin >> n >> e;
    while(e--) {
        int u, v; cin >> u >> v;
        indgr[v]++;
        outdgr[u]++;
        g[u].push_back(v);
    }
    for(int i = 0; i <= n; i++) {
        cout << indgr[i] << " ";
    }
    cout << "\n";
    for(int i = 0; i <= n; i++) {
        cout << outdgr[i] << " ";
    }
}

4. DFS

#include<bits/stdc++.h>
#define itsmdshahin ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ll long long
using namespace std;
const int N = 1e5 + 9;
bool vis[N];
vector<int> g[N];
void dfs(int s) {
    vis[s] = true;
    for(auto it : g[s]) {
        if(!vis[it]) {
            cout << "VISITED " << it << endl;
            dfs(it);
        }
    }
}
int main() {
    int n, m; cin >> n >> m;
    while(m--) {
        int x, y; cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    int s; cin >> s;
    dfs(s);
    for(int i = 1; i <= n; i++) {
        if(!vis[i]) {
            cout << "DISCONNECTED GRAPH\n";
            return 0;
        }
    }
}

5. Connected Components

#include<bits/stdc++.h>
#define itsmdshahin ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ll long long
using namespace std;
const int N = 1e5 + 9;
bool vis[N];
vector<int> g[N];
void dfs(int s) {
    vis[s] = true;
    for(auto it : g[s]) {
        if(!vis[it]) {
            dfs(it);
        }
    }
}

int main() {
    int n, m; cin >> n >> m;
    while(m--) {
        int x, y; cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        if(!vis[i]) {
            dfs(i);
            ++ans;
        }
    }
    cout << "Connected Components: " << ans << endl;
}

6. BFS Implementation

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
vector<int> G[N];
bool Vis[N];
int main() {
    int n, e; cin >> n >> e;
    while(e--) {
        int x, y; cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    queue<int> q;
    q.push(1);
    Vis[1] = true;
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(auto it : G[u]) {
            if(!Vis[it]) {
                q.push(it);
                Vis[v] = true;
            }
        }
    }
}

7. BFS Component Find in Graph

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
vector<int> G[N];
bool Vis[N];
queue<int> q;
void bfs(int n) {
    q.push(n);
    Vis[n] = true;
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(auto it : G[u]) {
            if(!Vis[it]) {
                q.push(it);
                Vis[it] = true;
            }
        }
    }
}

int main() {
    int n, e; cin >> n >> e;
    int ans = 0;
    for(int i = 0; i < n; i++) {
        if(!Vis[i]) {
            bfs(i);
            ++ans;
        }
    }
    cout << ans << endl;
}

8. BFS Distance Find in Graph Theory

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
vector<int> G[N];
bool Vis[N];
vector<int> dis(N);
int main() {
    int n, e; cin >> n >> e;
    queue<int> q;
    q.push(1);
    Vis[1] = true;
    dis[1] = 0;
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(auto it : G[u]) {
            if(!Vis[it]) {
                q.push(it);
                dis[it] = dis[u] + 1;
                Vis[it] = true;
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        cout << dis[i] << " ";
    }
    cout << endl;
}

---

9. BFS Path Find in Graph Theory

// Implementation will be added soon...

10. Bicoloring and Bipartite Graph

#include<bits/stdc++.h>
using namespace std;
const int N = 105;
vector<int> g[N];
bool vis[N], col[N], ok;

void dfs(int u) {
    vis[u] = true;
    for(auto v : g[u]) {
        if(!vis[v]) {
            col[v] = col[u] ^ 1;
            dfs(v);
        } else {
            if(col[u] == col[v]) ok = false;
        }
    }
}

int main() {
    int n, e;
    cin >> n >> e;
    while(e--) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    ok = true;
    for(int i = 1; i <= n; i++) {
        if(!vis[i]) dfs(i);
    }
    if(ok) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

11. Articulation Points and Bridges

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;

vector<int> g[N];
bool vis[N];
int in[N], low[N], timer;
set<int> articulationPoints;
set<pair<int, int>> bridges;

void dfs(int u, int par) {
    vis[u] = true;
    in[u] = low[u] = timer++;

    int children = 0;

    for (auto v : g[u]) {
        if (v == par) continue;

        if (vis[v]) {
            low[u] = min(low[u], in[v]);
        } else {
            dfs(v, u);
            low[u] = min(low[u], low[v]);

            if (low[v] >= in[u] && par != -1) {
                articulationPoints.insert(u);
            }

            if (low[v] > in[u]) {
                bridges.insert({min(u, v), max(u, v)});
            }

            children++;
        }
    }

    if (par == -1 && children > 1) {
        articulationPoints.insert(u);
    }
}

int main() {
    int n, e; cin >> n >> e;
    while (e--) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    timer = 0;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            dfs(i, -1);
        }
    }

    cout << "Articulation Points: ";
    for (auto point : articulationPoints) {
        cout << point << " ";
    }
    cout << "\n";

    cout << "Bridges: ";
    for (auto bridge : bridges) {
        cout << bridge.first << "-" << bridge.second << " ";
    }
    cout << "\n";

    return 0;
}

12. Topological Sorting

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
vector<int> g[N];
bool vis[N];
stack<int> order;

void dfs(int u) {
    vis[u] = true;
    for (auto v : g[u]) {
        if (!vis[v]) {
            dfs(v);
        }
    }
    order.push(u);
}

int main() {
    int n, e; cin >> n >> e;
    while (e--) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
    }

    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            dfs(i);
        }
    }

    cout << "Topological Sorting: ";
    while (!order.empty()) {
        cout << order.top() << " ";
        order.pop();
    }
    cout << "\n";

    return 0;
}

13. Dijkstra's Algorithm

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
vector<pair<int, int>> g[N];
vector<int> dis(N, INT_MAX);

void dijkstra(int start) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});
    dis[start] = 0;

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

        if (w > dis[u]) continue;

        for (auto it : g[u]) {
            int v = it.first;
            int weight = it.second;

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

int main() {
    int n, e; cin >> n >> e;
    while (e--) {
        int u, v, w; cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    int start; cin >> start;
    dijkstra(start);

    cout << "Shortest Distances from Node " << start << ":\n";
    for (int i = 1; i <= n; i++) {
        cout << "Node " << i << ": " << dis[i] << "\n";
    }

    return 0;
}

14. Bellman-Ford Algorithm

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
vector<tuple<int, int, int>> edges;
vector<int> dis(N, INT_MAX);

void bellmanFord(int start) {
    dis[start] = 0;

    for (int i = 1; i <= edges.size() - 1; i++) {
        for (auto edge : edges) {
            int u, v, w;
            tie(u, v, w) = edge;

            if (dis[u] != INT_MAX && dis[u] + w < dis[v]) {
                dis[v] = dis[u] + w;
            }
        }
    }
}

int main() {
    int n, e; cin >> n >> e;
    while (e--) {
        int u, v, w; cin >> u >> v >> w;
        edges.push_back({u, v, w});
    }

    int start; cin >> start;
    bellmanFord(start);

    cout << "Shortest Distances from Node " << start << ":\n";
    for (int i = 1; i <= n; i++) {
        cout << "Node " << i << ": " << dis[i] << "\n";
    }

    return 0;
}

15. Floyd-Warshall Algorithm

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
int dis[N][N];

void floydWarshall(int n) {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dis[i][k] != INT_MAX && dis[k][j] != INT_MAX && dis[i][k] + dis[k][j] < dis[i][j]) {
                    dis[i][j] = dis[i][k] + dis[k][j];
                }
            }
        }
    }
}

int main() {
    int n, e; cin >> n >> e;
    memset(dis, 0x3f, sizeof(dis));

    for (int i = 1; i <= n; i++) dis[i][i] = 0;

    while (e--) {
        int u, v, w; cin >> u >> v >> w;
        dis[u][v] = w;
    }

    floydWarshall(n);

    cout << "Shortest Distances between Nodes:\n";
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (dis[i][j] == INT_MAX) cout << "INF ";
            else cout << dis[i][j] << " ";
        }
        cout << "\n";
    }

    return 0;
}

16. Minimum Spanning Tree (Prim's Algorithm)

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
vector<pair<int, int>> g[N];
bool vis[N];

int primMST(int start) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});
    int mstWeight = 0;

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

        if (vis[u]) continue;

        mstWeight += w;
        vis[u] = true;

        for (auto it : g[u]) {
            int v = it.first;
            int weight = it.second;
            if (!vis[v]) {
                pq.push({weight, v});
            }
        }
    }

    return mstWeight;
}

int main() {
    int n, e; cin >> n >> e;
    while (e--) {
        int u, v, w; cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    int start; cin >> start;
    int mstWeight = primMST(start);

    cout << "Minimum Spanning Tree Weight: " << mstWeight << "\n";

    return 0;
}

### ```

Stay tuned for more updates!

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
11 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Happy coding...

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

nice blog

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

use spoiler to let your blog not to long....

→ Reply