图相关操作

1 图的相关概念

1.1 简单通路与初级通路区别

可以认为初级通路的限制条件比简单通路更强，简单通路包含初级通路

例如：

A —— B
 \   /
   C

A->B->C->A是一条简单通路
A->B->C是一条初级通路

概念	是否允许重复顶点	是否允许重复边
通路（walk）	✅	✅
简单通路（simple path）	✅	❌
初级通路（elementary path）	❌	❌

1.2 握手定理

• 对于无向图： 一个图的所有顶点的度数之和为其边数的两倍
• 对于有向图： 一个图的所有顶点的入度之和等于边数，一个图的所有顶点的出度之和等于边数，一个图的所有顶点的度数之和（入度之和+出度之和）为其边数的两倍
• 度数为奇数的顶点的个数为偶数

1.3 点割集与边割集

点割集

如果在一个连通图中删去一个或多个点，这个图就不再连通（多了连通分支），那么这些点组成的集合就是点割集

• 如果点割集只有一个点，那么这个点就被称作割点
• 一个图的顶点数最少的点割集的顶点数称为其点连通度，简称连通度

比如：

A — B — C — D

• 删除顶点 A：
  • 剩下 B–C–D 仍连通
  • {A} 不是点割集
• 删除顶点 C：
  • 剩下 A–B 和 D（断开）
  • {C} 是点割集（割点）

边割集

如果在一个连通图中删去一条或多条边后，这个图就不再连通，那么这些边组成的集合就是边割集

• 如果边割集只有一个点，那么这个点就被称作桥（割边）
• 与点割集相同，一个图的边最少的边割集的边数成为边连通度

1.4 连通的相关概念

对于有向图而言：

• 若G中任意两个顶点u,v，有u到v的通路，也有v到u的通路，则称其为强连通有向图
• 若G中任意两个顶点u,v，至少有u到v的通路或v到u的通路，则称其为单向连通有向图
• 若G的基图是无向连通图，则称其为弱连通有向图

1.5 邻接矩阵中元素的含义

图在此时以邻接矩阵A来存储

\(A^n\) 的含义

\(A^n\)中每个元素\(A_{ij}\) 表示从顶点\(i\)到顶点\(j\)的长度为n的通路的数量

例如：

\[ A^2= \begin{bmatrix} 1&1&0&1\\ 0&1&1&0\\ 2&0&0&0\\ 0&1&1&0 \end{bmatrix} \]

其中\(A_{31}\) 为2，说明从顶点3到顶点1有两个长度为2的通路

2 图的几种存储方式

存储方式	是否最常用	适合什么图	常见算法
邻接表（vector 存边）	⭐⭐⭐⭐⭐	稀疏图 / 大图	DFS / BFS / 拓扑排序 / 最短路 / 关键路径
邻接矩阵	⭐⭐	稠密图 / 点数很小	Floyd / 传递闭包 / 简单判边
边集（Edge List）	⭐⭐⭐	只关心边	Kruskal / Bellman-Ford
前向星（数组版邻接表）	⭐⭐⭐⭐	超大图 / 性能敏感	竞赛中所有图算法
反向图 / 双图	⭐⭐	强连通 / 入边操作	SCC / 拓扑 / DP
隐式图（不显式存边）	⭐⭐	状态图 / 搜索	BFS / DFS

2.1 邻接表

最常用的还是邻接表，因此主要介绍邻接表这一存储方式

若存储的是无向图

vector<vector<int>>G(n);//n代表节点数，若是从节点编号从1开始可设为n+1

void addEdge(int u,int v)//每条边需存两次
{
    G[u].push_back(v);
    G[v].push_back(u);
}

若存储的是有向无权图

vector<vector<int>>G(n)//n代表节点数，若是从节点编号从1开始可设为n+1

void addEdge(int u,int v)//存一次即可
{
    G[u].push_back(v);
}

若存储的是有向带权图，由于每条边上还附带了权重的信息，因此在存储时要附加一个东西，考虑用结构体构成一条边，或者使用pair<int,int>

结构体版

//这里to其实就是原来的v，w代表权重
struct Edge{
    int to;
    int w;
}

vector<vector<Edge>>G(n);

void addEdge(int u,int v,int w)
{
    G[u].push_back({v,w});//注意里面得用{}包裹
}

pair版

vector<vector<pair<int,int>>>G(n);

void addEdge(int u,int v,int w)
{
    G[u].push_back({v,w});//其实可以把pair理解为一种简化的二元结构体
}

存储结果

G[u]: (v1,w1), (v2,w2), ...

Note

看到“无向” → 边加两次

看到“有向” → 只加一次

看到“权值” → Edge 里多一个 w

3 图的DFS及BFS遍历

图的遍历方式，几乎完全由“如何枚举一个点的所有出边”决定

而在邻接表中，这一句话对应的是：

for (auto e : G[u]) {
    int v = e.to; // 或 int v = e
}

所有图遍历算法，本质上都是：

• 选择一个“当前点 u”

• 顺着 G[u] 找到所有 v

• 决定“什么时候、以什么顺序”访问这些 v

3.1 DFS

代码骨架

递归版

vector<bool>visited(n+1,false);//由于题目节点编号常从1开始，故此处容量设为n+1

void dfs(int u)
{
    visited[u]=true;//访问u

    //A.这里做刚访问到u时的操作

    for(auto e:G[u])
    {
        int v=e.to//这是对于有向带权图，如果是有向无权图、无向图，用int v=e即可

        //B.此时状态为检查u与v的关系，u已访问，v可能访问过，也可能没访问过

        if(!visited[v])
        {
            dfs(u);
        }
    }

    //C.此时状态为u的整个子树已经全部遍历完成，bfs独有的"回溯时刻"
}

上述的ABC三个位置分别是遍历中可以操作的地方

非递归版(栈)

vector<bool>visited(n+1,false);

void dfs(int start)
{
    stack<int>S;
    S.push(start);
    visited[start];//入栈即标记

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

        for(auto e:G[u])
        {
            int v=e.to//或int v=e;
            if(!visited[v])
            {
                S.push(v);
                visited[v]=true;//入栈即标记
            }
        }
    }
}

3.2 BFS

代码骨架

vector<bool>visited(n+1,false);
queue<int>q;

void bfs(int s)
{
    visited[s]=true;
    q.push(s);

    while(!q.empty())
    {
        int u=q.front();q.pop();
        //A.对u做事
        for(auto e:G[u])
        {
            int v=e.to//或int v=e;
            if(!visited[v])
            {
                visited[v]=true;
                //B.此时为u->v的最短路径(无权图)
                q.push(v);
            }
        }
    }

}

Look familiar?是的，bfs的遍历方式与dfs的非递归版的遍历方式的代码骨架几乎完全相同，只是把stack换成了queue而已

而bfs可操作的位置只有两个，分别是代码中的AB处

4 图的应用

4.1 Floyd算法

• 用于求解全源最短路问题：“求图中任意两点间的最短路径”(一次性求出任意两个顶点之间的最短距离。)
• 时间复杂度为 \(O(n^3)\)，空间复杂度为 \(O(n^2)\)
• 适用于有向图/无向图，只要没有负权回路即可
• 模拟的过程类似于Warshall

核心思想是 动态规划：

逐步允许更多的“中转点”，看看路径能不能变得更短。

设 dist[i][j] = 当前已知从 i 到 j 的最短距离

枚举一个中转点 k，判断：

i → j 直接走
vs
i → k → j 经过 k

如果经过 k 更短，就更新：

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

三层循环的含义是：

for k 所有中转点
  for i 起点
    for j 终点

代码模板如下：

const int INF = 1e9;//设置INF为无穷大

void Floyd(vector<vector<int>>&G,int n)//以邻接矩阵形式存储
{
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(G[i][k]!=INF&&G[k][j]!=INF)//这里加个if语句是为了防止两个无穷相加导致溢出
                {
                    G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
                }
            }
        }
    }
}

4.2 Dijkstra算法

• 用于求解单源最短路问题：“在“无负权边”的图中，求“某一个起点”到其他所有顶点的最短路径”
• 不能有负权边
• 适用于无向图/有向图（因为无向图可看作是双向有向图）
• 每一步都“贪心地”选当前距离起点最近、且尚未确定的点，并“永久确定”它的最短路。

核心思想是 贪心：

dist[v] = min(dist[v], dist[u] + w(u,v));

与Floyd的对比如下：

对比点	Floyd	Dijkstra
最短路类型	任意两点	单源
算法思想	动态规划	贪心
负权边	✔ 可	❌ 不可
时间复杂度	O(n³)	O(n²) / O(m log n)
适合点数	少	多

代码模板如下：

数组版

const int INF=1e9;

vector<int> Dijkstra(vector<vector<int>>&G,int n,int begin)
{
    vector<int>dist(n+1,INF);
    vector<bool>visited(n+1,false);
    dist[begin]=0;
    int u=0;
    //n个点都被遍历到后得到的就是从begin点出发的到各个点的最短路径
    for(int k=1;k<=n;k++)
    {
        //此循环为了确定dist最小的未访问点u
        for(int i=1;i<=n;i++)
        {
            if(!visited[i]&&(u==0||dist[i]<dist[u]))
            {
                u=i;
            }
        }
        visited[u]=true;
        for(int v=1;v<=n;v++)
        {
            if(G[u][v]!=INF&&visited[v]==false)
            {
                dist[v]=min(dist[v],dist[u]+G[u][v]);//此处G[u][v]记录的为权重
            }
        }
    }
    return dist;
}

优先队列版

const int INF=1e9;

vector<int> Dijkstra(vector<vector<int>>& G, int n, int begin)
{
    vector<int> dist(n+1, INF);
    dist[begin] = 0;

    // 小根堆：{dist, node}
    priority_queue<pair<int,int>,
                   vector<pair<int,int>>,
                   greater<pair<int,int>>> pq;

    pq.push({0, begin});

    while (!pq.empty())
    {
        auto [d, u] = pq.top();
        pq.pop();

        // 如果不是当前最优状态，跳过
        if (d > dist[u]) continue;

        // 松弛所有邻居
        for (int v = 1; v <= n; v++)
        {
            if (G[u][v] != INF)
            {
                if (dist[v] > d + G[u][v])
                {
                    dist[v] = d + G[u][v];
                    pq.push({dist[v], v});
                }
            }
        }
    }
    return dist;
}

4.3 拓扑排序

适用对象:DAG(有向无环图、不用考虑是否带权)

//由于拓扑排序需要点的入度信息，而它不好通过扫描邻接表来得到，因此在建图的时候就应该顺便把indegs数组维护好:
/*
    vector<int>indegs(n+1,0);
    G[u].push_back(v);
    indegs[v]++;
*/
//在拓扑排序中不需要visited数组，因为节点是否入队仅由其入度决定，入度为0时才入队

vector<int> topologicalSort(vector<vector<int>>&G,vector<int>indegs,int n)
{
    queue<int>q;
    vector<int>ans;

    for(int i=1;i<=n;i++)
    {
        if(indegs[i]==0)
        {
            q.push(i);
            visited[i]=true;
        }
    }

    while(!q.empty())
    {
        int u=q.front();q.pop();

        ans.push_back(u);

        for(auto e:G[u])
        {
            int v=e.to;//或int v=e
            indegs[v]--;
            if(indegs[v]==0)
            {
                q.push(v);
            }
        }
    }

    if(ans.size()<n)
    {
        //说明图中有环，执行相应的操作
    }
    return ans;
}

4.4 关键路径

求关键路径

手动模拟求解

大致思路：

• 先求点：先利用拓扑排序求出每个事件的最早开始时间\(v_e\)（越大才更新），再用逆拓扑排序求出每个事件的最晚开始时间\(v_l\)（越小才更新）

• 再求边：\(e\)等于发出点的\(v_e\)，\(l\)等于指向点的\(v_l\textrm{边权}\)，比较\(e\)和\(l\)，若二者相同，这就是一个关键活动，关键活动相连便构成了关键路径

• 直觉判断：整个图中代价最高的从起点到终点的路径就是关键路径

4.5 路径枚举

Note

在图相关操作中，常常出现"列出所有路径"的提问，这时候就涉及到对图从一个点u到target的所有访问序列的枚举

大致的思路是使用DFS+回溯的方法记录这些路径

代码模板如下:

vector<int>path;

void dfs(vector<vector<int>>&G,int u,int target)
{
    path.push_back(u);

    if(u==target)
    {
        for(int x:path)
        {
            cout<<x<<" ";
        }
        cout<<endl;
    }else{
        for(auto e:G[u])
        {
            int v=e;
            dfs(G,v,target)
        }
    }

    path.pop_back();
}

4.6 并查集

主要包含基本操作、路径压缩、按秩合并三个部分

首先是两个基本函数find和union

这里假设parent已经初始化好

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

以上为find的基础实现，在else中的return语句改为一个赋值语句可实现路径压缩，即每次查找后，查找路径上的元素都指向根

//路径压缩
int find(int x)
{
    if(parent[x]==x)
    {
        return x;
    }else{
        return parent[x]=find(parent[x]);
    }
}

然后是基本的union函数，即将两个元素合并进同一个集合里

void union(int x,int y)
{
    int rootx=find(x);
    int rooty=find(y);
    if(rootx!=rooty)
    {
        parent[rootx]=rooty;
    }
}
//这里的谁合并至谁可以任意

然后由于将节点少的树合并到节点多的树效率更高，因此可以依据节点数对齐进行优化，这里使用到size数组，表示该树的节点总数，和parent数组一起初始化，因此初始化的代码如下：

int initial(int n)//n表示总共多少个元素
{
    for(int i=0;i<n;i++)
    {
        parent[i]=i;
        size[i]=1;
    }
}

这就是按秩合并，则union函数可改为：

//注意不能用union，和关键字冲突
void Union(int x,int y)
{
    int rootx=find(x);
    int rooty=find(y);
    if(rootx!=rooty)
    {
        if(size[rootx]<=size[rooty])
        {
            parent[rootx]=rooty;
            size[rooty]+=size[rootx];
        }else{
            parent[rooty]=rootx;
            size[rootx]+=size[rooty];
        }
    }
}