图论总结

x1007 · 2025-07-03 09:01:53 · 算法·理论

图的存储

#include<bits/stdc++.h>
using namespace std;
#define x1007
vector<int>g[100000];
bool a[10001][10001];//用于存储图的邻接矩阵
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        g[v].push_back(u);
        g[u].push_back(v);//读取输入的顶点数n和边数m。
通过循环读取每条边的两个顶点u和v，并将它们添加到邻接表和邻接矩阵中
        a[u][v]=1;
        a[v][u]=1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<<a[i][j]<<' ';//双重循环遍历邻接矩阵，输出每个顶点之间的连接关系。如果顶点i和顶点j之间有边，则输出 1，否则输出 0。
        }
        cout<<endl;
    }
    for(int i=1;i<=n;i++){
        cout<<g[i].size()<<' ';
        sort(g[i].begin(),g[i].end());
        for(int j=0;j<g[i].size();j++){
            cout<<g[i][j]<<' ';
        }
        cout<<endl;

    }   
    x1007
    return 0;
}

图的遍历

#include<cstdio>
using namespace std;
#define x1007
const int maxn=1e5+10;
int edge[maxn],next[maxn];
int head[maxn],cnt;     //采用链式前向星实现邻接表存图
inline void Init(){     //邻接表初始化
    for(int i=0;i<maxn;i++)
        head[i]=next[i]=-1;
    cnt=0;
}
inline void addedge(int u,int v){   //加入边(u,v)
    edge[cnt]=v;
    next[cnt]=head[u];
    head[u]=cnt++;
}
int n,m;            //n为点数，m为边数
int ans[maxn];          //ans数组存答案，ans[i]即A(i)
void dfs(int n,int a){      //dfs实现
    if(ans[n]) return;      //如果访问过直接返回
    ans[n]=a;           //记录答案
    for(int i=head[n];~i;i=next[i]) //~i也可以写作i!=-1
        dfs(edge[i],a);
}
int main(){
    Init();
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        addedge(v,u);       //反向建图
    }
    for(int i=n;i;i--)      //从大到小dfs
        if(!ans[i]) dfs(i,i);
    for(int i=1;i<=n;i++)
        printf("%d ",ans[i]);
    return 0;
}

完美二叉树

每个节点只有左右两个子节点，所以可以用结构体。

Floyd

#include<bits/stdc++.h>
using namespace std;
#define x1007
const int maxn=101,maxw=100001;
int d[maxn][maxn];
int n,m;
void intit(){
    int i,j,k;
    cin>>n>>m;
    for(i=1;i<=n;i++)//初始化邻接链表矩阵 
        for(j=1;j<=n;j++)
            if(i==j)d[i][j]=0;
            else d[i][j]=maxw;
    for(int t=1;t<=m;t++){//邻接链表矩阵 存储 
        cin>>i>>j>>k;
        if(k<d[i][j]){
            d[i][j]=k;
            d[j][i]=k;
        }

    }
}
void floyed(){//Floyd算法 
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(d[i][k]+d[k][j]<d[i][j])
                    d[i][j]=d[i][k]+d[k][j];
}
void print(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<<d[i][j]<<' ';
        }
        cout<<endl;
    }
}
int main(){
    intit();
    floyed();
    print();
    x1007
    return 0;
}

电车

#include<bits/stdc++.h>
using namespace std;
#define x1007
const int maxn=101,maxw=100001;
int d[maxn][maxn];
int n,A,B;
void intit(){
    int i,j,k,m;
    cin>>n>>A>>B;
    for(i=1;i<=n;i++)//初始化邻接链表矩阵 
        for(j=1;j<=n;j++)
            if(i==j)d[i][j]=0;
            else d[i][j]=maxw;
    for(int i=1;i<=n;i++){//邻接链表矩阵 存储 
        cin>>m;
        if(m==0){
            continue;
        }
        cin>>j;
        d[i][j]=0;
        for(k=1;k<m;k++){
            cin>>j;
            if(1<d[i][j])
                d[i][j]=1;
        }
    }
}
void floyed(){//Floyd算法 
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(d[i][k]+d[k][j]<d[i][j])
                    d[i][j]=d[i][k]+d[k][j];
}
void print(){
    if(d[A][B]==maxw)
        cout<<-1<<endl;
    else
        cout<<d[A][B]<<endl;
}
int main(){
    intit();
    floyed();
    print();
    x1007
    return 0;
}

Cow Hurdles S

#include<bits/stdc++.h>
using namespace std;
#define x1007
const int maxn=305,inf=1e9;
int d[maxn][maxn];
int n,m,t;
void intit(){
    int i,j,k,m;
    cin>>n>>m>>t;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i==j)d[i][j]=0;
            else d[i][j]=inf;
    for(int i=0;i<m;i++){ 
        int s,e,h;
        cin>>s>>e>>h;
        d[s][e]=min(d[s][e],h);
    }
}
void floyed(){//Floyd算法 
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(d[i][k]!=inf&&d[k][j]!=inf)
                    d[i][j]=min(d[i][j],max(d[i][k],d[k][j]));
}
void print(){
     for(int i=0;i<t;i++){
        int a,b;
        cin>>a>>b;
        if(d[a][b]==inf)cout<<-1<<endl;
        else cout<<d[a][b]<<endl;
    }
}
int main(){
    intit();
    floyed();
    print();
    x1007
    return 0;
}

dijkstra

只需要求一个点到所有点的距离

#include<iostream>
#include<queue>
#include<cstring>
#define pir pair<int,int>  //typedef pair<int,int> pii
using namespace std;
const int maxn=1e6+5;
struct edge{
    int to,nxt,w;
}e[maxn];

int head[maxn], cnt, dis[maxn], vis[maxn],n, m, s;
void addedge(int u,int v,int w){
    e[++cnt].to=v;
    e[cnt].w=w;
    e[cnt].cnt=head[u];
    head[u]=cnt;
}

void dij(int s){
    priority_queue<pir, vector<pir>, greater<pir> >q;
    int vis[maxn];
    memset(vis,0,sizeof(vis)) ;
    memset(dis,0x3f3f3f3f,sizeof(dis));//距离数组
    dis[s]=0;
    q.push(pir(0,s));//q.push(make_pari(0,s));
    int u;
    while(!q.empty()){
        pir x=q.top();
        q.pop();
        if(vis[x.second]) continue;
        u=x.second;
        vis[u]=true;//表示点u标记
        for(int i=head[u];i;i=e[i].nxt)
            if(dis[e[i].to] > dis[u]+e[i].w){
                dis[e[i].to] = dis[u]+e[i].w;
                q.push(pir(dis[e[i].to], e[i].to));
            }
    }
}

P1821 [USACO07FEB] Cow Party S


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

const int MAXN = 1005;
const int INF = INT_MAX;

struct Edge {
    int to, w;
};

vector<Edge> graph[MAXN];   // 原图
vector<Edge> revGraph[MAXN]; // 反向图
int distToX[MAXN];          // 各点到x的最短距离（去程）
int distFromX[MAXN];        // x到各点的最短距离（回程）
bool vis[MAXN];

void dijkstra(int start, vector<Edge> g[], int dist[]) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    fill(dist, dist + MAXN, INF);
    fill(vis, vis + MAXN, false);
    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (auto &e : g[u]) {
            int v = e.to;
            int w = e.w;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

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

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
        revGraph[v].push_back({u, w});
    }

    // 计算回程路径（x到各点）
    dijkstra(x, graph, distFromX);

    // 计算去程路径（各点到x，使用反向图）
    dijkstra(x, revGraph, distToX);

    int maxDist = 0;
    for (int i = 1; i <= n; i++) {
        if (i != x) {
            maxDist = max(maxDist, distToX[i] + distFromX[i]);
        }
    }

    cout << maxDist<<endl;
    return 0;
}

Bellman-Ford 算法

同 Dijkstra 算法相比，Bellman-Ford 算法能够在图中存在负权边的情况下，解决单源最短路问题。思路：如果两点之间有最短路，那么最多经过图中所有顶点各一次（如果经过某个顶点两次，那么我们走出了一个环。如果环的权值为非负，显然不划算；如果权值为负，则最短路不存在），也就是说，这条路最多有 n-1 条边。根据最短路的最优子结构性质，最多包含 k 条边的最短路可以由最多包含 k-1 条边的最短路 “加一条边” 来求得，因此通过反复松弛每条边 n-1 遍，即可求得源点到所有点的最短路。

P3905 道路重建

#include<bits/stdc++.h>
using namespace std;
#define x1007
int h[105][105],d[105][105];
void floyd(int n)
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                h[i][j]=min(h[i][j],h[i][k]+h[k][j]);
}
int main()
{
    memset(h,0x3f3f3f3f,sizeof(h));
    int n,m,k;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int s,e;
        cin>>s>>e;
        cin>>d[s][e];
        d[e][s]=d[s][e];
        h[s][e]=h[e][s]=0;
    }
    cin>>k;
    for(int i=1;i<=k;i++)
    {
        int s,e;
        cin>>s>>e;
        h[s][e]=h[e][s]=d[s][e];
    }
    floyd(n);
    int st,en;
    cin>>st>>en;
    cout<<h[st][en];
    return 0;
}

int main()
{
    memset(h,0x3f3f3f3f,sizeof(h));
    int n,m,k;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int s,e;
        cin>>s>>e;
        cin>>d[s][e];
        d[e][s]=d[s][e];
        h[s][e]=h[e][s]=0;
    }

初始化 h 数组为无穷大，表示所有点对之间初始不可达读取 m 条边的信息，存储原始权重到 d 数组将这些边的初始状态设为可用（权重为 0），意味着初始时这些边不需要代价即可通过

    cin>>k;
    for(int i=1;i<=k;i++)
    {
        int s,e;
        cin>>s>>e;
        h[s][e]=h[e][s]=d[s][e];
    }

读取 k 条边的状态变化将这些边的权重设为其原始权重，表示这些边变为 "不可用" 状态，需要花费原始代价才能通过图中提取的文字内容如下：

SPFA算法简介‌

SPFA是Bellman-Ford算法的一种队列优化。利用每个点不会更新次数太多的特点，减少不必要的冗余计算。

主要思想‌

初始时将起点加入队列。每次从队列中取出一个元素，对所有与它相邻的顶点进行修改。若某个相邻的顶点修改成功，则将其入队，直到队列为空时算法结束。

算法特点‌

与广度优先搜索类似，但顶点可能多次进出队列。一个顶点修改过其它顶点后，可能会再次获得更短路径，于是再次用来修改其它顶点。

算法时间复杂度‌

O(kE)，其中E是边数，k是常数，平均值为2。

实现方法‌

建立队列，初始时队列里只有起始点。记录起始点到所有点的最短路径。执行松弛操作，依次用队列中的点去更新所有后继结点的最短路径。

实现方法

建立一个队列，初始时，队列里只有起始点。
然后执行松弛操作，依法用队列里有的点 U 去更新所有后继结点 vi 的最短路，如果 vi被更新成功，且不在队列中，则把该点加入到队列最后。重复执行直到队列为空。
结点可能被多次更新，可以多次进队列。 $If d[u]+w<d[v] then d[v]=d[u]+w
如果 v被更新了，如果队列不存在，再一次进入队列中。
Prim算法

Prim算法是一种贪心算法，用于在加权无向图中求解最小生成树（MST）。其核心思想是逐步扩展一棵树，每次添加连接树与非树顶点的最小权重边。

算法原理详解

目标：构造一棵连接所有顶点的树，使得总边权最小。

算法流程

初始化
- 随机选择一个顶点（如顶点1）作为起始点加入生成树集合S
- 初始化数组：
  - vis[]：标记顶点是否在集合S中（初始仅起点为true)
  - cost[]：存储集合S到其他顶点的最小边权（初始化为∞，起点设为0）
迭代扩展（重复 |V|-1 次）
- 步骤1：遍历所有顶点，找出满足以下条件的顶点u
  - 不在集合S中（vis[u] = false）
  - 具有最小的cost[u]值
- 步骤2：将顶点u加入集合S（vis[u] = true)
- 步骤3：更新u的邻接顶点v的代价：
```
for (每个与u相邻的顶点v) {
 if (!vis[v] && edge(u,v) < cost[v]) {
     cost[v] = edge(u,v);  // 更新最小边权
 }
}
```
终止条件
- 当所有顶点都加入集合S时结束

关键数据结构

数组	作用	初始值
`vis[]`	标记顶点是否在生成树集合中	全`false`（起点`true`)
`cost[]`	集合S到顶点的最小边权	起点`0`，其余`∞`

时间复杂度

实现方式	时间复杂度	适用场景
邻接矩阵+遍历	O(V²)	稠密图
邻接表+最小堆	O(E log V)	稀疏图

实例演示（图例）

       2
   A ----- B
   | \     |
  3|  \4   |1
   |   \   |
   C ----- D
       5

执行步骤：

选起点 A → cost=[A:0, B:2, C:3, D:4]
选最小边权顶点 B → 加入集合
更新邻点：D的代价更新为1（原为4）
选顶点 D → 加入集合
选最后顶点 C（通过边A-C:3）

最小生成树：
A-B(2), B-D(1), A-C(3)
总权重 = 6

模板

void prim(){
    bool.vis[maxn];//集合内外的标志
    int cost[maxn];//存储集合内到集合外顶点的最小值
    int minc,next,ans=0;//next最小值对应的顶点.
    memset(vis,0,sizeof(vis)); 
    memset(cost,0x3f,sizeof(cost)); 
    cost[1]=0;//初始化起始顶点1的花费.从任何一个顶点 开始都可以
    for(int i=1;i<=n;i++){
        minc=0x3f3f3f3f;
        for(int j=1;j<=n;j++)//找出集合内外连接的最短距离,和所连接的顶点mini
            if (!vis[j]&&cost[j]<minc){
                minc=cost[j];
                next=j;
            }
            vis[next]=true;//选中顶点j并入集合内
            for(j=1;i<=n;j++)//更新集合内集合外最短距离数组cost;
                if(!vis[j]&&cost[j]<map[next][j])
                    cost[j]=map[next][j];
    }
    return;
}

图论 总结