グラフの冗長接続検出

無向グラフにおいて、ツリー構造を維持しながら冗長な接続を特定する方法について説明します。

Union-Findによる冗長接続の検出

#include <iostream>
#include <vector>
using namespace std;

class UnionFind {
private:
    vector<int> parent;
public:
    UnionFind(int n) : parent(n + 1) {
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
        }
    }
    
    int findRoot(int x) {
        if (parent[x] != x) {
            parent[x] = findRoot(parent[x]);
        }
        return parent[x];
    }
    
    void unionNodes(int x, int y) {
        int rootX = findRoot(x);
        int rootY = findRoot(y);
        if (rootX != rootY) {
            parent[rootY] = rootX;
        }
    }
    
    bool connected(int x, int y) {
        return findRoot(x) == findRoot(y);
    }
};

int main() {
    int n;
    cin >> n;
    UnionFind uf(n);
    
    for (int i = 0; i < n; i++) {
        int u, v;
        cin >> u >> v;
        if (uf.connected(u, v)) {
            cout << u << " " << v << endl;
            return 0;
        } else {
            uf.unionNodes(u, v);
        }
    }
    return 0;
}

Python実装例

class GraphConnector:
    def __init__(self, size):
        self.parent = list(range(size + 1))
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def connect(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            self.parent[root_y] = root_x
            return False
        return True

def detect_redundant():
    n = int(input())
    connector = GraphConnector(n)
    edges = []
    
    for _ in range(n):
        a, b = map(int, input().split())
        edges.append((a, b))
    
    for a, b in edges:
        if connector.connect(a, b):
            print(f"{a} {b}")
            return

有向グラフの冗長接続問題

有向グラフにおける冗長接続の特定と、有向ツリーへの変換について考察します。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class DirectedGraphAnalyzer {
private:
    vector<int> parent;
    vector<int> inDegree;
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    bool connects(int x, int y) {
        return find(x) == find(y);
    }
    
    void merge(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootY] = rootX;
        }
    }
    
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        parent.resize(n + 1);
        inDegree.resize(n + 1, 0);
        
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
        
        vector<int> candidate;
        for (int i = n - 1; i >= 0; i--) {
            int to = edges[i][1];
            if (inDegree[to] == 1) {
                candidate.push_back(i);
            }
            inDegree[to]++;
        }
        
        if (!candidate.empty()) {
            if (validateTree(edges, candidate[0])) {
                return edges[candidate[0]];
            } else {
                return edges[candidate[1]];
            }
        }
        
        return detectCycle(edges);
    }
};

最小全域木アルゴリズム

Primアルゴリズムを用いた最小全域木の構築方法について説明します。

Primアルゴリズムの実装

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

class PrimMST {
public:
    int calculateMST(int vertices, vector<vector<int>>& graph) {
        vector<int> minDistance(vertices + 1, INT_MAX);
        vector<bool> inMST(vertices + 1, false);
        minDistance[1] = 0;
        int totalWeight = 0;
        
        for (int i = 1; i < vertices; i++) {
            int current = selectMinVertex(minDistance, inMST);
            inMST[current] = true;
            totalWeight += minDistance[current];
            
            updateDistances(current, graph, minDistance, inMST);
        }
        return totalWeight;
    }
    
private:
    int selectMinVertex(vector<int>& dist, vector<bool>& inTree) {
        int minVal = INT_MAX;
        int selected = -1;
        for (int i = 1; i < dist.size(); i++) {
            if (!inTree[i] && dist[i] < minVal) {
                minVal = dist[i];
                selected = i;
            }
        }
        return selected;
    }
    
    void updateDistances(int current, vector<vector<int>>& graph, 
                        vector<int>& dist, vector<bool>& inTree) {
        for (int i = 1; i < graph.size(); i++) {
            if (!inTree[i] && graph[current][i] != INT_MAX) {
                if (graph[current][i] < dist[i]) {
                    dist[i] = graph[current][i];
                }
            }
        }
    }
};

Kruskalアルゴリズムによる最小全域木

辺の重みに基づいて最小全域木を構築するKruskalアルゴリズムを紹介します。

#include <algorithm>
#include <vector>
using namespace std;

struct GraphEdge {
    int source, destination, weight;
    bool operator<(const GraphEdge& other) const {
        return weight < other.weight;
    }
};

class KruskalMST {
private:
    vector<int> parent;
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootY] = rootX;
        }
    }
    
public:
    int buildMST(int vertices, vector<GraphEdge>& edges) {
        parent.resize(vertices + 1);
        for (int i = 1; i <= vertices; i++) {
            parent[i] = i;
        }
        
        sort(edges.begin(), edges.end());
        int mstWeight = 0;
        
        for (const auto& edge : edges) {
            if (find(edge.source) != find(edge.destination)) {
                unite(edge.source, edge.destination);
                mstWeight += edge.weight;
            }
        }
        return mstWeight;
    }
};

トポロジカルソート

有向非巡回グラフにおけるノードの依存関係を解決するトポロジカルソートアルゴリズム。

#include <queue>
#include <vector>
using namespace std;

class TopologicalSorter {
public:
    vector<int> sort(int n, vector<vector<int>>& dependencies) {
        vector<int> inDegree(n, 0);
        vector<vector<int>> adjacency(n);
        
        for (const auto& dep : dependencies) {
            adjacency[dep[0]].push_back(dep[1]);
            inDegree[dep[1]]++;
        }
        
        queue<int> q;
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                q.push(i);
            }
        }
        
        vector<int> result;
        while (!q.empty()) {
            int current = q.front();
            q.pop();
            result.push_back(current);
            
            for (int neighbor : adjacency[current]) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    q.push(neighbor);
                }
            }
        }
        
        return result.size() == n ? result : vector<int>{-1};
    }
};

Dijkstraアルゴリズム

非負の重みを持つグラフにおける単一始点最短経路問題を解決するDijkstraアルゴリズム。

#include <vector>
#include <climits>
using namespace std;

class ShortestPathFinder {
public:
    int findShortestPath(int n, vector<vector<int>>& graph, int start, int end) {
        vector<int> distances(n + 1, INT_MAX);
        vector<bool> visited(n + 1, false);
        distances[start] = 0;
        
        for (int i = 1; i <= n; i++) {
            int current = findMinDistance(distances, visited);
            if (current == -1) break;
            
            visited[current] = true;
            for (int j = 1; j <= n; j++) {
                if (!visited[j] && graph[current][j] != INT_MAX) {
                    if (distances[current] + graph[current][j] < distances[j]) {
                        distances[j] = distances[current] + graph[current][j];
                    }
                }
            }
        }
        
        return distances[end] == INT_MAX ? -1 : distances[end];
    }
    
private:
    int findMinDistance(vector<int>& dist, vector<bool>& visited) {
        int minVal = INT_MAX;
        int minIndex = -1;
        for (int i = 1; i < dist.size(); i++) {
            if (!visited[i] && dist[i] < minVal) {
                minVal = dist[i];
                minIndex = i;
            }
        }
        return minIndex;
    }
};