Module 9 - Advanced Graph


1. Introduction

Module 9: Advanced Graph

Author: YP

Learning Objectives

After completing this module, students are expected to be able to:

  1. Explain the basic concepts of Graph (including adjacency list and adjacency matrix representation).
  2. Implement graph traversal using DFS (Depth First Search) and BFS (Breadth First Search).
  3. Understand and implement the Shortest Path algorithm (Dijkstra).
  4. Implement Minimum Spanning Tree (MST) algorithms: Prim and Kruskal.
  5. Compare the efficiency of manual graph algorithms with STL libraries such as priority_queue and disjoint set union (DSU).

2. Graph Concept

2.1 Theory

2.1.1 Definition of Graph

A Graph is a data structure consisting of:

Graphs can be:

2.1.2 Graph Representation

There are two main representations of graphs in programming:

  1. Adjacency Matrix
    A 2D matrix [V][V], where V is the number of vertices. Each element indicates whether an edge exists between two nodes (commonly 1 for an edge, 0 for no edge).

    • Suitable for dense graphs.
    • Edge lookup is efficient with O(1) time complexity.
    int graph[5][5] = {
    {0, 1, 0, 0, 1},
    {1, 0, 1, 1, 0},
    {0, 1, 0, 1, 0},
    {0, 1, 1, 0, 1},
    {1, 0, 0, 1, 0}
};

  2. Adjacency List
    Each vertex stores a list of its adjacent vertices (neighbors).

    • Memory-efficient for sparse graphs, as only existing edges are stored.
    • Edge lookup may take up to O(V) in the worst case.
    vector<int> adj[5];

adj[0].push_back(1);
adj[0].push_back(4);
adj[1].push_back(0);
adj[1].push_back(2);
adj[1].push_back(3);

2.1.3 Graph Traversal

Graph traversal can be performed in two main ways:

2.1.4 Shortest Path Algorithm: Dijkstra

void dijkstra(int V, vector<pair<int,int>> adj[], int src) {
    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 [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    cout << "Jarak terpendek dari " << src << ":\n";
    for (int i = 0; i < V; i++) {
        cout << "Ke " << i << " = " << dist[i] << endl;
    }
}

2.1.5 Minimum Spanning Tree (MST)

Prim’s Algorithm

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

void primMST(int n, vector<vector<pair<int, int>>> &adj) {
    vector<int> key(n, INF);
    vector<bool> inMST(n, false);
    vector<int> parent(n, -1);

    // Mulai dari node 0
    key[0] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push({0, 0}); // {weight, node}

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

        if (inMST[u]) continue;
        inMST[u] = true;

        for (auto &[v, w] : adj[u]) {
            if (!inMST[v] && w < key[v]) {
                key[v] = w;
                pq.push({key[v], v});
                parent[v] = u;
            }
        }
    }

    cout << "Edges in MST (Prim):\n";
    for (int i = 1; i < n; i++) {
        cout << parent[i] << " - " << i << "\n";
    }
}

int main() {
    int n = 5;
    vector<vector<pair<int, int>>> adj(n);

    // contoh graf berbobot (undirected)
    adj[0].push_back({1, 2});
    adj[1].push_back({0, 2});

    adj[0].push_back({3, 6});
    adj[3].push_back({0, 6});

    adj[1].push_back({2, 3});
    adj[2].push_back({1, 3});

    adj[1].push_back({3, 8});
    adj[3].push_back({1, 8});

    adj[1].push_back({4, 5});
    adj[4].push_back({1, 5});

    adj[2].push_back({4, 7});
    adj[4].push_back({2, 7});

    primMST(n, adj);
}

Kruskal’s Algorithm

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int u, v, w;
    bool operator<(const Edge &other) const {
        return w < other.w;
    }
};

struct DSU {
    vector<int> parent, rank;
    DSU(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) {
        if (x != parent[x])
            parent[x] = find(parent[x]);
        return parent[x];
    }

    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;
        if (rank[a] < rank[b]) swap(a, b);
        parent[b] = a;
        if (rank[a] == rank[b]) rank[a]++;
        return true;
    }
};

void kruskalMST(int n, vector<Edge> &edges) {
    sort(edges.begin(), edges.end());
    DSU dsu(n);

    cout << "Edges in MST (Kruskal):\n";
    for (auto &e : edges) {
        if (dsu.unite(e.u, e.v)) {
            cout << e.u << " - " << e.v << "\n";
        }
    }
}

int main() {
    int n = 5;
    vector<Edge> edges = {
        {0, 1, 2}, {0, 3, 6}, {1, 2, 3},
        {1, 3, 8}, {1, 4, 5}, {2, 4, 7}
    };

    kruskalMST(n, edges);
}

2.2 Example of Graph Traversal

Example of an undirected weighted graph:

image