517编程普及组数学之图论基础
![](https://image.wsq127.top/file/bb91b00c28fd2210948bd.png)
517编程普及组数学之图论基础
wsq127在算法或数学中,图是由若干给定的顶点及连接两顶点的边所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物,连接两顶点的边则用于表示两个事物间具有这种关系。
基本概念
- 节点(或顶点):图中的一个元素,可以用来表示某个实体或概念。在C++中,通常可以用整数或自定义的结构体来表示节点。
- 度:指与一个点相连的节点数量。
- 边:连接图中两个节点的线,可以是有向的(箭头指向)也可以是无向的。
- 边权:指一条边的权值,可以理解为长度。
分类
- 无向图:指每条边都是没有方向的图,可以从任意一边出发,类似双行道。
- 有向图:指每条边都是有方向的,只能按照相应的方向,类似单行道。
- 完全图:只每两个点之间都有一条边。一个有 $n$ 个节点的完全图有 $n*(n-1)/2$ 条边。
- 连通图:指每个点都可以到达另一个点。
- 连通块:一张非连通图中会有多个连通块,每一个连通块中的每个点都可以到达另一个点。
- 树:指 $n$ 个点,$n-1$ 条边的连通图。
表示
在 C++ 中,图有两种表达:
邻接矩阵:
通过矩阵存储图,
a[i][j]
表示点 $i$ 到点 $j$ 是否有边。1
2int a[N][N]//定义
a[u][v]=1//添加一条 u 指向 v 的节点邻接表
使用向量数组存储图,
a[i]
存储所有点 $i$ 指向的点。1
2vector<int> a[N]//定义
a[u].push_back(v)//添加一条 u 指向 v 的节点
算法
拓扑排序
概念
拓扑排序针对于有向无环图(DAG)。
每一个节点在进行拓扑排序后会先于所有它能到达的点。
这样似乎不好理解,用一个简单的图排序一遍就懂了。
对于上面这幅图:
- A->B->C->D->E
- A->B->D->C->E
- A->C->B->D->E
- …
都是这幅图的拓扑排序结果,当然,在很多时候会要求你输出字典序最小的情况。
思路
要实现拓扑排序,我们发现,第一个节点的入度为 $0$,而删去第一个节点后,第二个节点入读仍然为 $0$。
它的大概逻辑就是:
- 找到所有入度为 $0$ 的节点,并加入答案数组
- 删去入度为 $0$ 的节点,并更新其它节点的入度
- 反复 1、2 步,直到没有节点
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
using namespace std;
int n,m;
vector<int> mp[100005];//使用邻接表存图
map<int,int> in;
vector<int> ans;
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
mp[u].push_back(v);//表示 u 有一条指向 v 的边
in[v]++;//统计入度
}
queue<int> q;//存储当前所有入度为 0 的点
for(int i=1;i<=n;i++)
{
if(in[i]==0)//如果入度为 0
q.push(i);//加入队列
}
while(!q.empty())
{
int t=q.front();
q.pop();
ans.push_back(t);//将 t 加入答案数组
for(int i=0;i<mp[t].size();i++)
{
in[mp[t][i]]--;//t 指向的所有节点入度减一
if(in[mp[t][i]]==0)//如果入度为 0
q.push(mp[t][i]);//加入队列
}
}
for(int i=0;i<ans.size();i++)
cout<<ans[i]<<" ";
return 0;
}最短路
概念
字面意思,最短路指的是从一个点到达另一个点的最短路径
思路
这里讲解 Dijkstra 算法。
这个算法运用到了一个贪心的思想,即走到当前节点时路径最优。走到这个节点时,我们去遍历所有下一个节点,如果从这个节点走过去比原来的路径短的话,就更新。当然,一开始都得赋值为极大值。
代码
由于是图论基础,不展示(((
没写出来用vector的,一个邻接矩阵一个前向星
评论
匿名评论隐私政策
✅ 你无需删除空行,直接评论以获取最佳展示效果