Navigating the Directed Maze: Finding the Minimum Spanning Tree

When we think of graphs, we often picture the vast and intricate networks connecting cities, data points, or even social interactions. But what happens when we add direction to our edges? Enter directed graphs, where the edges have a one-way street feel.

The Dilemma: Can We Have an MST in Directed Graphs?

(I know, I know we already have famous algorithms for the same but let's not go that way and explore other options too😁)

The traditional MST focuses on undirected graphs, ensuring that every node is reachable from every other node. However, in directed graphs, we face a fork in the road. Directed graphs can be categorized into two types:

1. Strongly Connected Graphs: Here, every node can reach every other node. No problem—finding an MST is straightforward!

2. Weakly Connected Graphs: In this scenario, while the graph is connected when we ignore direction, not all nodes can reach each other directly. This raises a question: How do we find an MST when we have multiple starting points?

In weakly connected graphs, we must begin our journey from a root node that can reach all other nodes. But wait—there might be several potential roots that satisfy this condition! Our goal is to determine the minimum weight spanning tree, so we need a strategy to compare these roots and pick the one that gives us the least weight.

My solution works for strongly connected ones but for weakly connected ones we have to modify this solution.

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

int spanningTreeForDirectedGraphs(int V, vector<vector<int>> adj, int e) {
    vector<int> weight(V, INT_MAX);
    vector<vector<int>> mat(V, vector<int>(V, -1));

    // Construct the adjacency matrix
    for (int i = 0; i < e; i++) {
        mat[adj[i][0]][adj[i][1]] = adj[i][2];
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    // Assuming source node 0 if not given
    q.push({0, 0});
    weight[0] = 0;
    int ans = 0;

    while (!q.empty()) {
        int node = q.top().second;
        int dis = q.top().first;
        q.pop();

        for (int i = 0; i < V; i++) {
            int wei = mat[node][i];
            if (weight[i] > wei && wei != -1) {
                q.push({wei, i});
                if (weight[i] != INT_MAX) {
                    ans -= weight[i];
                }
                weight[i] = wei;
                ans += wei;
            }
        }
    }
    return ans;
}

int main() {
    int v, e;
    cin >> v >> e;
    vector<vector<int>> adj(e);

    for (int i = 0; i < e; i++) {
        int u, v, wt;
        cin >> u >> v >> wt;
        adj[i].push_back(u);
        adj[i].push_back(v);
        adj[i].push_back(wt);
    }

    cout << spanningTreeForDirectedGraphs(v, adj, e);
    return 0;
}

Let’s Test Our Method with a Simple Case

Imagine a directed graph with 3 vertices and the following edges:

3 3
0 2 5
2 1 3
1 0 1

This represents a graph where:

• An edge goes from node 0 to node 2 with a weight of 5.
• An edge goes from node 2 to node 1 with a weight of 3.
• An edge goes from node 1 back to node 0 with a weight of 1.

After running our algorithm, we see that by removing the edge (1,0), we create a spanning tree with a total weight of 8. Voilà! We have successfully navigated through the directed maze!

Here’s the challenge💪: Can we find an MST for weakly connected ones too? Feel free to modify my solution or come up with your own unique approach(remember new and unique is the trend🤌).