老程序员博客

编程生涯的最后一舞

当前位置：首页 > 技术 > 正文内容

图论合集

访客 技术 2026年6月8日 1

最小生成树

kruskal

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

struct Edge {
    int from, to, weight;
};

int findParent(vector<int>& parent, int x) {
    if (parent[x] != x) {
        parent[x] = findParent(parent, parent[x]);
    }
    return parent[x];
}

void unionSets(vector<int>& parent, int x, int y) {
    int rootX = findParent(parent, x);
    int rootY = findParent(parent, y);
    parent[rootY] = rootX;
}

int kruskalMST(int vertexCount, vector<Edge>& edges) {
    vector<int> parent(vertexCount + 1);
    for (int i = 1; i <= vertexCount; ++i) {
        parent[i] = i;
    }

    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
        return a.weight < b.weight;
    });

    int totalWeight = 0;
    int selectedEdges = 0;

    for (const auto& edge : edges) {
        if (findParent(parent, edge.from) != findParent(parent, edge.to)) {
            unionSets(parent, edge.from, edge.to);
            totalWeight += edge.weight;
            selectedEdges++;
            if (selectedEdges == vertexCount - 1) {
                break;
            }
        }
    }

    return totalWeight;
}

int main() {
    int vertexCount, edgeCount;
    cin >> vertexCount >> edgeCount;

    vector<Edge> edges(edgeCount);
    for (int i = 0; i < edgeCount; ++i) {
        cin >> edges[i].from >> edges[i].to >> edges[i].weight;
    }

    cout << kruskalMST(vertexCount, edges) << endl;
    return 0;
}

最短路

dijkstra

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

typedef pair<int, int> pii;

void dijkstraShortestPath(int vertexCount, int startNode, const vector<vector<pii>>& graph) {
    vector<int> distances(vertexCount + 1, INT_MAX);
    distances[startNode] = 0;

    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, startNode});

    while (!pq.empty()) {
        int currentDistance = pq.top().first;
        int currentNode = pq.top().second;
        pq.pop();

        if (currentDistance > distances[currentNode]) {
            continue;
        }

        for (const auto& neighbor : graph[currentNode]) {
            int nextNode = neighbor.first;
            int edgeWeight = neighbor.second;
            int newDistance = currentDistance + edgeWeight;

            if (newDistance < distances[nextNode]) {
                distances[nextNode] = newDistance;
                pq.push({newDistance, nextNode});
            }
        }
    }

    for (int i = 1; i <= vertexCount; ++i) {
        if (distances[i] == INT_MAX) {
            cout << "inf ";
        } else {
            cout << distances[i] << " ";
        }
    }
    cout << endl;
}

int main() {
    int vertexCount, edgeCount;
    cin >> vertexCount >> edgeCount;

    vector<vector<pii>> graph(vertexCount + 1);
    for (int i = 0; i < edgeCount; ++i) {
        int from, to, weight;
        cin >> from >> to >> weight;
        graph[from].push_back({to, weight});
    }

    int startNode = 1;
    dijkstraShortestPath(vertexCount, startNode, graph);
    return 0;
}

SPFA

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

struct Edge {
    int to, weight, next;
};

void spfaShortestPath(int vertexCount, int startNode, const vector<Edge>& edges, const vector<int>& head) {
    vector<int> distances(vertexCount + 1, INT_MAX);
    vector<bool> inQueue(vertexCount + 1, false);
    queue<int> q;

    distances[startNode] = 0;
    q.push(startNode);
    inQueue[startNode] = true;

    while (!q.empty()) {
        int currentNode = q.front();
        q.pop();
        inQueue[currentNode] = false;

        for (int i = head[currentNode]; i != -1; i = edges[i].next) {
            int nextNode = edges[i].to;
            int edgeWeight = edges[i].weight;

            if (distances[currentNode] + edgeWeight < distances[nextNode]) {
                distances[nextNode] = distances[currentNode] + edgeWeight;
                if (!inQueue[nextNode]) {
                    q.push(nextNode);
                    inQueue[nextNode] = true;
                }
            }
        }
    }

    for (int i = 1; i <= vertexCount; ++i) {
        if (distances[i] == INT_MAX) {
            cout << "-1 ";
        } else {
            cout << distances[i] << " ";
        }
    }
    cout << endl;
}

int main() {
    int vertexCount, edgeCount, startNode;
    cin >> vertexCount >> edgeCount >> startNode;

    vector<Edge> edges;
    vector<int> head(vertexCount + 1, -1);
    int edgeIndex = 0;

    for (int i = 0; i < edgeCount; ++i) {
        int from, to, weight;
        cin >> from >> to >> weight;
        edges.push_back({to, weight, head[from]});
        head[from] = edgeIndex++;
    }

    spfaShortestPath(vertexCount, startNode, edges, head);
    return 0;
}

缩点

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

struct Edge {
    int to, next;
};

void tarjanSCC(int currentNode, const vector<vector<int>>& graph, vector<int>& discoveryTime, vector<int>& lowLink, vector<bool>& inStack, stack<int>& nodeStack, vector<int>& componentId, int& timestamp, int& componentCount) {
    discoveryTime[currentNode] = lowLink[currentNode] = ++timestamp;
    nodeStack.push(currentNode);
    inStack[currentNode] = true;

    for (int neighbor : graph[currentNode]) {
        if (discoveryTime[neighbor] == -1) {
            tarjanSCC(neighbor, graph, discoveryTime, lowLink, inStack, nodeStack, componentId, timestamp, componentCount);
            lowLink[currentNode] = min(lowLink[currentNode], lowLink[neighbor]);
        } else if (inStack[neighbor]) {
            lowLink[currentNode] = min(lowLink[currentNode], discoveryTime[neighbor]);
        }
    }

    if (lowLink[currentNode] == discoveryTime[currentNode]) {
        int topNode;
        do {
            topNode = nodeStack.top();
            nodeStack.pop();
            inStack[topNode] = false;
            componentId[topNode] = componentCount;
        } while (topNode != currentNode);
        componentCount++;
    }
}

int main() {
    int vertexCount, edgeCount;
    cin >> vertexCount >> edgeCount;

    vector<vector<int>> graph(vertexCount + 1);
    for (int i = 0; i < edgeCount; ++i) {
        int from, to;
        cin >> from >> to;
        graph[from].push_back(to);
    }

    vector<int> discoveryTime(vertexCount + 1, -1);
    vector<int> lowLink(vertexCount + 1);
    vector<bool> inStack(vertexCount + 1, false);
    stack<int> nodeStack;
    vector<int> componentId(vertexCount + 1);
    int timestamp = 0;
    int componentCount = 0;

    for (int i = 1; i <= vertexCount; ++i) {
        if (discoveryTime[i] == -1) {
            tarjanSCC(i, graph, discoveryTime, lowLink, inStack, nodeStack, componentId, timestamp, componentCount);
        }
    }

    // 这里可以添加后续处理强连通分量的代码
    // 例如，构建缩点后的新图，计算入度等

    return 0;
}

例题

[最小生成树]USACO08OCT Watering Hole G

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

struct Edge {
    int from, to, weight;
};

int findParent(vector<int>& parent, int x) {
    if (parent[x] != x) {
        parent[x] = findParent(parent, parent[x]);
    }
    return parent[x];
}

void unionSets(vector<int>& parent, int x, int y) {
    int rootX = findParent(parent, x);
    int rootY = findParent(parent, y);
    parent[rootY] = rootX;
}

int main() {
    int n;
    cin >> n;

    vector<int> wellCost(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> wellCost[i];
    }

    vector<vector<int>> costMatrix(n + 1, vector<int>(n + 1));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> costMatrix[i][j];
        }
    }

    vector<Edge> edges;
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            edges.push_back({i, j, costMatrix[i][j]});
        }
    }

    for (int i = 1; i <= n; ++i) {
        edges.push_back({i, n + 1, wellCost[i]});
    }

    vector<int> parent(n + 2);
    for (int i = 1; i <= n + 1; ++i) {
        parent[i] = i;
    }

    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
        return a.weight < b.weight;
    });

    int totalCost = 0;
    int selectedEdges = 0;

    for (const auto& edge : edges) {
        if (findParent(parent, edge.from) != findParent(parent, edge.to)) {
            unionSets(parent, edge.from, edge.to);
            totalCost += edge.weight;
            selectedEdges++;
            if (selectedEdges == n) {
                break;
            }
        }
    }

    cout << totalCost << endl;
    return 0;
}

[缩点] USACO03FALL / HAOI2006 受欢迎的牛 G

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

struct Edge {
    int to, next;
};

void tarjan(int currentNode, const vector<vector<Edge>>& graph, vector<int>& discoveryTime, vector<int>& lowLink, vector<bool>& inStack, stack<int>& nodeStack, vector<int>& componentId, int& timestamp, int& componentCount) {
    discoveryTime[currentNode] = lowLink[currentNode] = ++timestamp;
    nodeStack.push(currentNode);
    inStack[currentNode] = true;

    for (const auto& edge : graph[currentNode]) {
        int neighbor = edge.to;
        if (discoveryTime[neighbor] == -1) {
            tarjan(neighbor, graph, discoveryTime, lowLink, inStack, nodeStack, componentId, timestamp, componentCount);
            lowLink[currentNode] = min(lowLink[currentNode], lowLink[neighbor]);
        } else if (inStack[neighbor]) {
            lowLink[currentNode] = min(lowLink[currentNode], discoveryTime[neighbor]);
        }
    }

    if (lowLink[currentNode] == discoveryTime[currentNode]) {
        int topNode;
        do {
            topNode = nodeStack.top();
            nodeStack.pop();
            inStack[topNode] = false;
            componentId[topNode] = componentCount;
        } while (topNode != currentNode);
        componentCount++;
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<Edge>> graph(n + 1);
    int edgeIndex = 0;
    for (int i = 0; i < m; ++i) {
        int from, to;
        cin >> from >> to;
        graph[from].push_back({to, edgeIndex++});
    }

    vector<int> discoveryTime(n + 1, -1);
    vector<int> lowLink(n + 1);
    vector<bool> inStack(n + 1, false);
    stack<int> nodeStack;
    vector<int> componentId(n + 1);
    int timestamp = 0;
    int componentCount = 0;

    for (int i = 1; i <= n; ++i) {
        if (discoveryTime[i] == -1) {
            tarjan(i, graph, discoveryTime, lowLink, inStack, nodeStack, componentId, timestamp, componentCount);
        }
    }

    vector<int> componentInDegree(componentCount, 0);
    for (int i = 1; i <= n; ++i) {
        for (const auto& edge : graph[i]) {
            int neighbor = edge.to;
            if (componentId[i] != componentId[neighbor]) {
                componentInDegree[componentId[neighbor]]++;
            }
        }
    }

    int uniqueSource = -1;
    for (int i = 0; i < componentCount; ++i) {
        if (componentInDegree[i] == 0) {
            if (uniqueSource != -1) {
                cout << 0 << endl;
                return 0;
            }
            uniqueSource = i;
        }
    }

    if (uniqueSource == -1) {
        cout << 0 << endl;
    } else {
        int nodeCountInComponent = 0;
        for (int i = 1; i <= n; ++i) {
            if (componentId[i] == uniqueSource) {
                nodeCountInComponent++;
            }
        }
        cout << nodeCountInComponent << endl;
    }

    return 0;
}

[基环树] NOIP2018 提高组 旅行

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

vector<int> graph;
vector<int> visited;
vector<int> path;
int n, m;

void dfs(int currentNode, int parent) {
    visited[currentNode] = 1;
    path.push_back(currentNode);

    for (int neighbor : graph[currentNode]) {
        if (neighbor == parent) continue;
        if (visited[neighbor] == 0) {
            dfs(neighbor, currentNode);
        } else if (visited[neighbor] == 1) {
            // Found a cycle
            int cycleStart = neighbor;
            int cycleEnd = currentNode;
            // ... (cycle processing logic)
        }
    }

    visited[currentNode] = 2;
    path.pop_back();
}

int main() {
    cin >> n >> m;
    graph.resize(n + 1);
    visited.resize(n + 1, 0);

    for (int i = 0; i < m; ++i) {
        int from, to;
        cin >> from >> to;
        graph[from].push_back(to);
        graph[to].push_back(from);
    }

    // Sort adjacency lists for deterministic output
    for (int i = 1; i <= n; ++i) {
        sort(graph[i].begin(), graph[i].end());
    }

    if (n == m + 1) {
        // It's a tree, perform a simple DFS
        dfs(1, -1);
        for (int node : path) {
            cout << node << " ";
        }
        cout << endl;
    } else {
        // It's a unicyclic graph, need to handle the cycle
        // ... (unicyclic graph processing logic)
    }

    return 0;
}
标签: 图论
返回列表

上一篇：Kotlin 函数机制与高阶编程深度解析

下一篇：ESP32外设深度解析：寄存器级控制与工业级工程实践

相关文章

Linux crontab 详解

1) crontab 是什么cron 是 Linux 的定时任务守护进程；crontab 是用来编辑/查看“按时间周期执行命令”的表（cron table）。常见两类：用户 crontab：每个用户一份（crontab -e 编辑）系统级 crontab / cron.d：可指定执行用户（/etc/crontab、/etc/cron.d/*）2) crontab 时间...

富文本里可以允许的 HTML 属性

一、所有标签默认允许的安全属性（极少）class        （可选）id           （通常建议禁用）title️ 注意：id 容易被滥用做锚点注入，很多系统直接禁用class 允许的话最好只允许固定前缀（如 editor-*）二、a 标签允许属性<a href="" t...

Mac 安装 Node.js 指南

方法一：通过官网安装包（最简单，适合初学者）如果你只是想快速安装并开始使用，这是最直接的方法。访问 Node.js 官网。页面会显示两个版本：LTS (Recommended For Most Users)：长期支持版，最稳定。建议选这个。Current：最新特性版，包含最新功能但可能不够稳定。下载 .pkg 安装包并运行。按照安装向导点击“下一步”即可完成。方法二：使用 Homebrew 安装（...

Dom\HTML_NO_DEFAULT_NS 的副作用：自动加闭合标签

在使用Dom\HTMLDocument时，Dom\HTML_NO_DEFAULT_NS 将禁止在解析过程中设置元素的命名空间, 此设置是为了与DOMDocument向后兼容而存在的。当使用它时，已知的一个副作用就是：自动加闭合标签例如 </img> 为什么会这样？当你使用：Dom\HTML_NO_DEFAULT_NS文档会变成 无命名空间模式，此时内部更接近 XML...

Laravel 事件和监听器创建

在 Laravel 中，使用 Artisan 命令创建 Events（事件） 和 Listeners（监听器） 是非常高效的。你可以通过以下几种方式来实现：1. 手动创建单个 Event如果你只想创建一个事件类，可以使用 make:event 命令：Bashphp artisan make:event UserRegistered执行后，文件将生成在 app/Even...

自定义域名解析神器 dnsmasq

什么是 dnsmasq？dnsmasq 是一个轻量级、功能强大的网络服务工具，专为小型和中等规模网络设计。它是一个综合的网络基础设施解决方案[1]。dnsmasq 能做什么？功能说明应用场景DNS 转发与缓存将 DNS 查询转发到上游服务器（ISP、Google DNS 等），并在本地缓存结果加快 DNS 查询速度，减少外部 DNS 流量本地 DNS解析本地网络设备的主机名，无需编辑&n...

发表评论

访客

◎欢迎参与讨论，请在这里发表您的看法和观点。

Copyright © agingcoder.cn

Powered By Z-BlogPHP. Theme by TOYEAN.