23考研王道图（第六章）自用笔记
图基本概念图的概念图G由顶点集V和边集E组成，记为G = (V, E)，其中V(G)表示图G中顶点的有限非空集；E(G)表示图G中顶点之间的关系（边）集合。若V = {v1, v2, … , vn}，则用 |V| 表示图G中顶点的个数，也称图G的阶==，E = {(u, v) | uÎV, vÎV}，用 |E| 表示图G中边的条数。注意：线性表可以是空表，树可以是空树，但图不可以是空，即V一定是非
·
图
基本概念
-
图的概念
图G由顶点集V和边集E组成，记为G = (V, E)，其中V(G)表示图G中顶点的有限非空集；E(G)
表示图G中顶点之间的关系（边）集合。若V = {v1, v2, … , vn}，则用 |V| 表示图G中顶点的个
数，也称图G的阶==，E = {(u, v) | uÎV, vÎV}，用 |E| 表示图G中边的条数。
注意：线性表可以是空表，树可以是空树，但图不可以是空，即V一定是非空集
-
无向图、有向图
若E是 无向边 （简称边）的有限集合时，则图G为无向图。边是顶点的无序对，记为 (v, w)或(w, v) ，因为(v, w) = (w, v)，其中v、w是顶点。可以说顶点w和顶点v互为邻接点。边(v, w)依附于顶点w和v，或者说边(v, w)和顶点v、w相关联。
G2 = (V2, E2)
V2 = {A, B, C, D, E}
E2 = {(A, B), (B, D), (B, E), (C, D), (C, E), (D, E)}
若E是有向边（也称弧）的有限集合时，则图G为有向图。弧是顶点的有序对，记为<v, w>，其中v、w是顶点，v称为弧尾，w称为弧头，<v, w>称为从顶点v到顶点w的弧，也称v邻接到w，或w邻接自v， <v, w> ≠ <w, v>
G1 = (V1, E1)
V1 = {A, B, C, D, E}
E1 = {<A, B>, <A, C>, <A, D>, <A, E>, <B, A>, <B, C>, <B, E>, <C, D>} -
简单图、多重图
简单图——① 不存在重复边；② 不存在顶点到自身的边
多重图——图G中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联，则G为多重图 -
顶点的度、入度、出度
无向图：
有向图：
-
顶点-顶点的关系描述
- 路径——顶点Vp到顶点Vq,之间的一条路径是指顶点序列，Vp,Vi1,Vi2…Vim , Vq
- 回路——第一个顶点和最后一个顶点相同的路径称为回路或环
- 简单路径——在路径序列中，顶点不重复出现的路径称为简单路径。
- 简单回路——除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
- 路径长度——路径上边的数目
- 点到点的距离——从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。若从u到v根本不存在路径，则记该距离为无穷(oo）。
- 无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的
- 有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的
- 连通图、强连通图
- 若图G中任意两个顶点都是连通的，则称图G为连通图，否则称为非连通图。
常见考点：
对于n个顶点的无向图G，
若G是连通图，则最少有 n-1 条边
若G是非连通图，则最多可能有C2 n-1条边 - 若图中任何一对顶点都是强连通的，则称此图为强连通图。
常见考点：
对于n个顶点的有向图G，
若G是强连通图，则最少有 n 条边（形成回路）
- 研究图的局部——子图
设有两个图G = (V, E)和G’ = (V’, E’)，若V’是V的子集，且E’是E的子集，则称G’是G的子图。
若有满足V(G’) = V(G)的子图G’，则称其为G的生成子图
- 连通分量与强连通分量
- 无向图中的极大连通子图（子图必须连通，且包含尽可能多的顶点和边）称为 连通分量
- 有向图中的极大强连通子图（子图必须强连通，同时保留尽可能多的边）称为有向图的强连通分量
- 生成树与生成森林
- 连通图的生成树是包含图中全部顶点的一个极小连通子图（边尽可能的少，但要保持连通）
若图中顶点数为n，则它的生成树含有n-1条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。
- 在非连通图中，连通分量的生成树构成了非连通图的生成森林。
- 边的权、带权图/网
边的权——在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。
带权图/网——边上带有权值的图称为带权图，也称网。
带权路径长度——当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度
几种特殊的图
图的存储
邻接矩阵法
- 非带权图
#define MaxVertexNum 100 //顶点数目最大值
typedef char VertexType; //顶点类型
typedef int EdgeType; //边的权值得类型
typedef struct {
VertexType Vex[MaxVertexNum]; //顶点表
EdgeType Edge[MaxVertexNum][MaxVertexNum]; //邻接矩阵/边表
int vexnum, arcnum; //当前顶点数和边数
} MGraph;
思考：如何求顶点的度、入度、出度？如何找到与一个顶点相连的边/弧？
第i个结点的出度 = 第i行的非零元素个数
第i个结点的入度 = 第i列的非零元素个数
第i个结点的度 = 第i行、第i列的非零元素个数之和
邻接矩阵法求顶点的度/出度/入度的时间复杂度为 O(|V|)
- 带权图
#define MaxVertexNum 无穷大/int的最大值 //顶点数目最大值
typedef char VertexType; //顶点类型
typedef int EdgeType; //边的权值得类型
typedef struct {
VertexType Vex[MaxVertexNum]; //顶点表
EdgeType Edge[MaxVertexNum][MaxVertexNum]; //邻接矩阵/边表
int vexnum, arcnum; //当前顶点数和边数
} MGraph;
- 邻接矩阵法的性能分析
- 空间复杂度：O(|V|2)——只和顶点数相关，和实际的边数无关
- 适合用于存储稠密图
- 无向图的邻接矩阵是对称矩阵，可以压缩存储（只存储上三角区/下三角区）
- 邻接矩阵法的性质
邻接表(顺序+链式存储)
#define MaxVertexNum 100 //顶点数目最大值
typedef char VertexType; //顶点类型
typedef int EdgeType; //边的权值得类型
//边/弧
typedef struct ArcNode {
int adjvex; //边/弧指向哪个结点
struct ArcNode *next; //指向下一条弧的指针
//InfoType info; //边权值
} ArcNode;
//顶点
typedef struct VNode {
VertexType data; //顶点信息
ArcNode *first; //第一条边/弧
} VNode, AdjList[MaxVertexNum];
//用邻接表存储的图
typedef struct {
AdjList vertices;
int vexnum, arcnum;
} ALGraph;
十字链表——存储有向图
- 邻接表和邻接矩阵的弊端
- 邻接表
- 十字链表法性能分析
空间复杂度:O(IVI+IEI)
如何找到指定顶点的所有出边?——顺着绿色线路找
如何找到指定顶点的所有入边?——顺着橙色线路找
注意:十字链表只用于存储有向图
邻接多重表——存储无向图
- 十字链表的弊端
- 邻接多重表
- 十字链表法性能分析
空间复杂度：O(|V|+|E|)（每条边只对应一份数据）
删除边、删除节点等操作很方便
注意：邻接多重表只适用于存储无向图
图的基本操作
- Adjacent(G,x,y)：判断图G是否存在边<x, y>或(x, y)。
- Neighbors(G,x)：列出图G中与结点x邻接的边。
- InsertVertex(G,x)：在图G中插入顶点x。
- DeleteVertex(G,x)：从图G中删除顶点x。
- AddEdge(G,x,y)：若无向边(x, y)或有向边<x, y>不存在，则向图G中添加该边。
- RemoveEdge(G,x,y)：若无向边(x, y)或有向边<x, y>存在，则从图G中删除该边。
- FirstNeighbor(G,x)：求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1。
- NextNeighbor(G,x,y)：假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1。
- Get_edge_value(G,x,y)：获取图G中边(x, y)或<x, y>对应的权值。
- Set_edge_value(G,x,y,v)：设置图G中边(x, y)或<x, y>对应的权值为v。
- 邻接矩阵
//返回顶点值所在对应的顶点数组G.Vex[]的下标
int LocateVex(MGraph G, VertexType e) {
for (int i = 0; i < G.vexnum; i++) {
if (e == G.Vex[i]) {
return i;
}
}
}
//创建图
void CreateGraph(MGraph &G) {
cin >> G.vexnum >> G.arcnum; //输入图的顶点个数和边数
for (int i = 0; i < G.vexnum; i++) { //初始化邻接矩阵
cin >> G.Vex[i]; //输入顶点的值
for (int j = 0; j < G.vexnum; j++) {
G.Edge[i][j] = 0; //初始化为0;
}
}
for (int k = 0; k < G.arcnum; k++) {
VertexType a, b;
cin >> a >> b; //输入边<a,b>
int i = LocateVex(G, a); //找对应的下标
int j = LocateVex(G, b);
G.Edge[i][j] = 1;
//G.Edge[j][i] = G.Edge[i][j]; //无向图
}
}
//判断图G是否存在边<x, y>或(x, y)
bool Adjacent(MGraph G, VertexType x, VertexType y) {
for (int i = 0; i < G.vexnum; i++) {
for (int j = 0; j < G.vexnum; j++) {
if (G.Edge[LocateVex(G, x)][LocateVex(G, y)] == 1) {
return true;
}
}
}
return false;
}
//输出图
void output(MGraph G) {
for (int i = 0; i < G.vexnum; i++) {
cout << G.Vex[i] << " ";
for (int j = 0; j < G.vexnum; j++)
cout << G.Edge[i][j] << " ";
cout << endl;
}
}
- 邻接表
#define MaxVertexNum 100 //顶点数目最大值
typedef char VertexType; //顶点类型
typedef int EdgeType; //边的权值得类型
//边/弧
typedef struct ArcNode {
int adjvex; //边/弧指向哪个结点
struct ArcNode *next; //指向下一条弧的指针
//InfoType info; //边权值
} ArcNode;
//顶点
typedef struct VNode {
VertexType data; //顶点信息
ArcNode *first; //第一条边/弧
} VNode, AdjList[MaxVertexNum];
//用邻接表存储的图
typedef struct {
AdjList vertices;
int vexnum, arcnum;
} ALGraph;
int LocateVex(ALGraph G, VertexType v) {
for (int i = 0; i < G.vexnum; i++) {
if (v == G.vertices[i].data) {
return i;
}
}
}
void CreateGraph(ALGraph &G) {
cin >> G.vexnum >> G.arcnum; //输入点数和边数
for (int i = 0; i < G.vexnum; i++) {
cin >> G.vertices[i].data; //输入顶点值
G.vertices[i].first = NULL; //初始化指针指向空
}
for (int k = 0; k < G.arcnum; k++) {
VertexType v1, v2;
cin >> v1 >> v2; //输入边<v1,v2>
int i = LocateVex(G, v1); //定位对应定点的下标值
int j = LocateVex(G, v2);
ArcNode *p1, *p2; //头差法，详细见线性表一章
p1 = new ArcNode(); //生成p1结点
p1->adjvex = j; //p1的值为v1指向的顶点v2的下标
p1->next = G.vertices[i].first; //p1的指针指向前一个指针指的空
G.vertices[i].first = p1; //前一个顶点指向p1
//无向图时，再次插入另一个结点
p2 = new ArcNode();
p2->adjvex = i;
p2->next = G.vertices[j].first;
G.vertices[j].first = p2;
}
}
void OutputGraph(ALGraph G) {
ArcNode *p;
for (int i = 0; i < G.vexnum; i++) {
if (G.vertices[i].first != NULL)
cout << i << "| " << G.vertices[i].data << "->";
else
cout << i << G.vertices[i].data;
p = G.vertices[i].first;
while (p) {
if (p->next != NULL)
cout << p->adjvex << "->";
else
cout << p->adjvex;
p = p->next;
}
cout << endl;
}
}
图的广度优先遍历（辅助队列实现）
手算时采用辅助队列进行操作，详细见树的层序遍历动画，同时与之对应的邻接矩阵/邻接表做参考，切忌看图
与树的广度优先遍历之间的联系
树的广度优先遍历:
通过根节点，可以找到下一层的结点2，3，4.通过234又可以找到再下一层的结点5678
上图的广度优先遍历
从顶点1出发得到的广度优先遍历序列:
1，2，5，6，3，7，4，8
从顶点3出发得到的广度优先遍历序列:
3，4，6，7，8，2，1，5
算法实现
⼴度优先遍历（Breadth-First-Search, BFS）要点：
- 找到与⼀个顶点相邻的所有顶点
- 标记哪些顶点被访问过
- 需要⼀个辅助队列
- FirstNeighbor(G,x)：求图G中顶点x的第⼀个邻接点，若有则返回顶点号。
若x没有邻接点或图中不存在x，则返回-1。 - NextNeighbor(G,x,y)：假设图G中顶点y是顶点x的⼀个邻接点，返回除y之外
顶点x的下⼀个邻接点的顶点号，若y是x的最后⼀个邻接点，则返回-1。 - bool visited [MAX_VERTEX_NUM];//访问标记数组
例子
- 从图中某个顶点 v 出发， 访问 v, 并置 visited[v]的值为 true, 然后将 v 进队。
- 只要队列不空， 则重复下述操作：
①队头顶点 u 出队；
②依次检查 u 的所有邻接点 w, 如果 visited[w]的值为 false, 则访问 w, 并置 visited[w]的值为 true, 然后将 w 进队。
代码
1.邻接矩阵
#include "queue"
bool visited[MaxVertexNum];//访问标记数组,默认初始化是false，恰好如此
//求图G中顶点x的第一个邻接点，若有则返回顶点号。
// 若x没有邻接点或图中不存在x，则返回-1
int FirstNeighbor(MGraph G, int v) { //v为第一个未访问的邻接点
for (int k = 0; k < G.vexnum; k++) {
if (G.Edge[v][k] == 1 && !visited[k]) { //确保k是为被访问的
return k;
}
}
return -1;
}
//假设图G中顶点y是顶点x的一个邻接点，返回除y之外
//顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1。
int NextNeighbor(MGraph G, int v, int w) {
if (w >= G.vexnum - 1) { //j越界
return -1;
}
for (int k = w + 1; k < G.vexnum; k++) { //w是v的一个邻接点，继续寻找w后面的邻接点
if (G.Edge[v][k] == 1 && !visited[k]) {
return k;
}
}
return -1;
}
//从v开始广度优先遍历连通图
void BFS(MGraph G, int v) {
queue<int> Q; //定义一个队列
cout << G.Vex[v] << " ";
visited[v] = true;
Q.push(v);
while (!Q.empty()) { //队不为空
v = Q.front();
Q.pop(); //顶点v出队
//依次检查v的所有邻接点w, FirstNeighbor(G,v)表示u的第一个邻接点
//NextNeighbor(G,v,w)表示v相对于w的下一个邻接点，w>=0表示存在邻接点
for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
if (!visited[w]) {
cout << G.Vex[w] << " ";
visited[w] = true;
Q.push(w);
}
}
}
}
//从0开始广度优先遍历非连通图
void BFSTraverse(MGraph G) {
for (int i = 0; i < G.vexnum; i++) {
visited[i] = false;
}
for (int i = 0; i < G.vexnum; i++) {
if (!visited[i]) {
BFS(G, i); //从G.Vex[]中第一个未被访问的顶点开始
}
}
}
//从V开始广度优先遍历非连通图
void BFS_AM(MGraph G, int v) {
BFS(G, v);
for (int i = 0; i < G.vexnum; i++) {
if (!visited[i]) {
BFS(G, i);
}
}
}
2.邻接表
努力吧少年
复杂度分析
广度优先生成树
图的深度优先遍历（递归实现）
手算时参考邻接矩阵/邻接表利用函数调用栈实现
与树的深度优先遍历之间的联系
算法实现
树的深度优先遍历（先根、后根）：
从根节点出发，能往更深处⾛就尽量往深处⾛。每当访问⼀个结点的时候，要检查是否还有与当前结点相邻的且没有被访问过的结点，如果有的话就往下⼀层钻。
图的深度优先遍历类似于树的先根遍历。
例子
参考邻接矩阵手算深度优先
从2出发的深度遍历序列:2，1，5，6，3，4，7，8（邻接矩阵）
从1出发的深度遍历序列:1，2，6，3，4，7，8，5（邻接矩阵）
从3出发的深度遍历序列:3，4，7，6，2，1，5，8（邻接矩阵）
同一个图的邻接矩阵表示方式唯一，因此深度优先遍历序列唯一
同一个图邻接表表示方式不唯一，因此深度优先遍历序列不唯一
- 代码
- 邻接矩阵
//深度优先遍历连通图
void DFS(MGraph G, int v) {
cout << G.Vex[v] << " ";
visited[v] = true;
for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
if (!visited[w]) {
DFS(G, w);
}
}
}
//深度优先从0开始遍历非连通图
void DFSTraverse(MGraph G){
for( int v=0; v<G.vexnum;v++)
visited[v]= false;
for(int v=0; v<G.vexnum; v++)
if( !visited[v])
DFS(G,v);
}
//深度优先从V开始遍历非连通图
void DFS_AM(MGraph G, int v) {
cout << G.Vex[v] << " ";
visited[v] = true;
for (int i = 0; i < G.vexnum; i++) {
if (G.Edge[v][i] != 0 && !visited[i]) {
DFS(G, i);
}
}
}
2.邻接表
加油少年！！！
复杂度分析
深度优先生成树
图的遍历和图的连通性
最小生成树(最小代价树)
最小生成树概念
对于⼀个带权连通⽆向图G = (V, E)，⽣成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同。设R为G的所有⽣成树的集合，若T为R中边的权值之和最⼩的⽣成树，则T称为G的最⼩⽣成树（Minimum-Spanning-Tree, MST）
- 最小生成树可能有多个，但边的权值之和总是唯一且最小的
- 最小生成树的边数=顶点数–1。砍掉一条则不连通，增加一条边则会出现回路
- 如果⼀个连通图本身就是⼀棵树，则其最⼩⽣成树就是它本身
- 只有连通图才有⽣成树，⾮连通图只有⽣成森林
Prim算法——对点操作
Prim 算法（普⾥姆）：
从某⼀个顶点开始构建⽣成树；每次将代价最⼩的新顶点纳⼊⽣成树，直到所有顶点都纳⼊为⽌（最小生成树不唯一）。
struct {
VertexType adjvex; //顶点值
int lowcost; //边值
} closedge[MaxVertexNum];
//普利姆（Prim）算法,从v开始生成
void MiniSpanTree_Prim(MGraph G, VertexType u) {
int k = LocateVex(G, u); //获取v的下标
for (int j = 0; j < G.vexnum; j++) {
if (j != k) {
//初始化，除k以外，全部adjvex=u,lowcost=G.Edge[k][j](u到各个顶点（G.Vex[j]）的边值)
//此时图中不连通的顶点间边值为无穷大
对v-u 的每一个顶点 Vj, 初始化 closedge[j]
closedge[j] = {u, G.Edge[k][j]};
}
}
closedge[k].lowcost = 0; //初始， U={u}
for (int j = 1; j < G.vexnum; j++) {
//选择其余 n-1 个顶点，生成 n-1 条边(n=G.vexnum)
int min = MaxInt;
for (int j = 0; j < G.vexnum; j++) {
//值不为零且到G.Vex[j]的距离小于最小值
if (closedge[j].lowcost != 0 && closedge[j].lowcost < min) {
min = closedge[j].lowcost; //找到最小的值
k = j; //将其顶点下标赋值给k
}
}
VertexType u0 = closedge[k].adjvex; //最小的一个顶点
VertexType v0 = G.Vex[k]; //最小的另一个顶点
cout << u0 << " " << v0 << " " << endl;
closedge[k].lowcost = 0; //第k下标的顶点并入u集
for (int j = 0; j < G.vexnum; ++j)
if (G.Edge[k][j] < closedge[j].lowcost) //新顶点并入u 后重新选择最小边
closedge[j] = {G.Vex[k], G.Edge[k][j]};
}
}
时间复杂度：O(|V|2)适合⽤于边稠密图
Kruskal（克鲁斯卡尔）算法——对边操作
图参考Prim的用例图
Kruskal 算法（克鲁斯卡尔）：
每次选择⼀条权值最⼩的边，使这条边的两头连通（原本已经连通的就不选）直到所有结点都连通
算法的实现要引入以下辅助的数据结构。
①结构体数组Edge:
存储边的信息，包括边的两个顶点信息和权值。
struct {
VertexType Head; //边的始点
VertexType Tail; //边的终点
EdgeType lowcost; //边上的权值
} Edge[MaxVertexNum];//应该是边的大小
(2) Vexset[i]: 标识各个顶点所属的连通分量。对每个顶点Vi属于V, 在辅助数组中存在一个相应元
素Vexset[i]表示该顶点所在的连通分量。初始时Vexset[i] = i, 表示各顶点自成一个连通分量。
//辅助数组 Vexset 的定义
int Vexset[MVNum];
其中Edge数组需要按照权值大小排序
步骤
//辅助数组Edges 的定义
struct Edges {
VertexType Head; //边的始点
VertexType Tail; //边的终点
EdgeType lowcost; //边上的权值
} Edge[MaxVertexNum];//应该是边的大小
//辅助数组 Vexset 的定义
int Vexset[MaxVertexNum];
//Edge的创建在创建图时同时创建
//创建图
void CreateGraph(MGraph &G) {
cin >> G.vexnum >> G.arcnum; //输入图的顶点个数和边数
for (int i = 0; i < G.vexnum; i++) { //初始化邻接矩阵
cin >> G.Vex[i]; //输入顶点的值
for (int j = 0; j < G.vexnum; j++) {
G.Edge[i][j] = MaxInt; //初始化为无穷大;
}
}
for (int k = 0; k < G.arcnum; k++) {
VertexType a, b;
int num;//Edge[]数组下标;
cin >> a >> b >> num; //输入边<a,b>
int i = LocateVex(G, a); //找对应的下标
int j = LocateVex(G, b);
G.Edge[i][j] = num;
//同时创建Edge[],克鲁斯卡尔辅助数组
Edge[k] = {G.Vex[i], G.Vex[j], num};//头尾权值一次赋值
G.Edge[j][i] = G.Edge[i][j]; //无向图
}
}
//按照权值小——大排序Edge[]数组
void MySort(Edges edges[], MGraph G) {
for (int i = 0; i < G.arcnum - 1; i++) {
for (int j = i+1; j < G.arcnum; j++) {
if (edges[i].lowcost > edges[j].lowcost) {
Edges p = edges[i];
edges[i] = edges[j];
edges[j] = p;
}
}
}
}
void OutPut_Edge(Edges edges[], int m) {
for (int i = 0; i < m; i++) {
cout << edges[i].Head << " " << edges[i].Tail << " " << edges[i].lowcost << endl;
}
}
//克鲁斯卡尔Kruskal
void MiniSpanTree_Kruskal(MGraph G) {
//排序Edge[]数组
MySort(Edge, G);
//初始化Vexset数组
for (int i = 0; i < G.arcnum; i++) {
Vexset[i] = i;
}
for (int i = 0; i < G.arcnum; i++) {
//获取头尾结点的数组下标
int v1 = LocateVex(G, Edge[i].Head);
int v2 = LocateVex(G, Edge[i].Tail);
//获取Vexset数组的值以比较判断是否在同一连通分量
int vs1 = Vexset[v1];
int vs2 = Vexset[v2];
if (vs1 != vs2) {
cout << Edge[i].Head << Edge[i].Tail << endl; //输出头尾
//循环判断在Vexset数组中是否含有与Vs2相同的，有则改成与vs1相同的值
for (int j = 0; j < G.arcnum; ++j) {
if (Vexset[j] == vs2) {
Vexset[j] = vs1;
}
}
}
}
}
时间复杂度：O( |E|log2|E| )适合⽤于边稀疏图
最短路径问题
最短路径类型
- “G港”是个物流集散中心,经常需要往各个城市运东西，怎么运送距离最近?——单源最短路径问题
BFS算法（无权图)和Dijkstra算法（带权图、无权图) - 各个城市之间也需要互相往来，相互之间怎么走距离最近?——每对顶点间的最短路径
Floyd算法（带权图、无权图)
图例
Dijkstra算法（不适用于带负权值的图）
算法步骤
//辅助数组
struct SDPath {
bool S; //判断是否求出权值
EdgeType D; //权值
int path; //记录到该点的的前驱
} SDPath[MaxVertexNum];//应该是点的大小
//迪杰斯特拉
void ShortestPath_DIJ(MGraph G, int v0) {
int n = G.vexnum;
//SDPath的初始化操作
for (int v = 0; v < n; v++) {
SDPath[v].S = false; //初始化全为false
SDPath[v].D = G.Edge[v0][v]; //记录V0出发到各个点的权值
//如果有边，path为前驱v0的下标0，反之为-1；
if (SDPath[v].D < MaxInt) {
SDPath[v].path = v0;
} else {
SDPath[v].path = -1;
}
}
SDPath[v0].S = true; //v0出发，已记录权值
SDPath[v0].D = 0; //（v0,v0）权值为0
int v;
//求最短路径
for (int i = 1; i < n; ++i) {
int min = MaxInt;
//找到最小值并记录v，v为最小值对应的点的下标；
for (int w = 0; w < n; ++w) {
if (!SDPath[w].S && SDPath[w].D < min) {
v = w;
min = SDPath[w].D;
}
}
SDPath[v].S = true; //此时的V为新求出来的点的下标
//判断新求出来的点+以前的路径权值是否比之前的小，如果小则替换同时path为true
for (int w = 0; w < n; w++) {
if (!SDPath[w].S && (SDPath[v].D + G.Edge[v][w]) < SDPath[w].D) {
SDPath[w].D = SDPath[v].D + G.Edge[v][w];
SDPath[w].path = v;
}
}
}
}
已知path[ ]可以求起到各个终点的最短路径
Floyd算法
不能解决带有“负权回路"的图（有负权值的边组成回路)，这种图有可能没有最短路径，可以解决带负权值的图
找到起点和终点，逐步在起点终点之间加点，然后判断路径权值，直至找到最短路径
代码
//Floyd算法
void shortestPath_Floyd(MGraph G) {
int D[G.vexnum][G.vexnum], P[G.vexnum][G.vexnum];
//各对结点之间初始已知路径及距离
for (int i = 0; i < G.vexnum; ++i) {
for (int j = 0; j < G.vexnum; ++j) {
D[i][j] = G.Edge[i][j];
if (D[i][j] < MaxInt) {
P[i][j] = i;
} else {
P[i][j] = -1;
}
}
}
for (int k = 0; k < G.vexnum; ++k) {
for (int i = 0; i < G.vexnum; ++i) {
for (int j = 0; j < G.vexnum; ++j) {
//从1经k到］的一条路径更短
if (D[i][k] + D[k][j] < D[i][j]) {
D[i][j] = D[i][k] + D[k][j];//更新D[i) [j J
P[i][j] = P[k][j]; //更改］的前驱为K
}
}
}
}
//已知D[][]和P[][]数组求最短路径，加油少年！！！
}
有向无环图
概念
若一个有向图中不存在环，则称为有向无环图，简称DAG图(Directed Acyclic Graph)
DAG描述表达式，由表达式写出化简后的图
-
（方法一）根据表达式画出对应的二叉树
（方法一）相同项合并
-
（方法二）
Step 1:把各个操作数不重复地排成一排
Step 2:标出各个运算符的生效顺序（先后顺序有点出入无所谓)
Step 3:按顺序加入运算符，注意“分层”
Step 4:从底向上逐层检查同层的运算符是否可以合体
拓扑排序
AOV⽹
AOV⽹(Activity On Vertex NetWork，⽤顶点表示活动的⽹)：
⽤DAG图（有向⽆环图）表示⼀个⼯程。顶点表示活动，有向边<Vi, Vj>表示活动Vi必须先于活动Vj进⾏
例如：做饭的顺序不能变，按照图来
拓扑排序
- 拓扑排序︰在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序:
①每个顶点出现且只出现一次。
②若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径。
或定义为:拓扑排序是对有向无环图的顶点的一种排序，它使得若存在一条从顶点A到顶点B的路径，则在排序中顶点B出现在顶点A的后面。每个AOV网都有一个或多个拓扑排序序列。
上图的一个拓扑排序为：
- 拓扑排序的实现:
从AOV网中选择一个没有前驱(入度为0)的顶点并输出。
②从网中删除该顶点和所有以它为起点的有向边。
③重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。
汇聚原天河团队并行计算工程师、中科院计算所专家以及头部AI名企HPC专家，助力解决“卡脖子”问题
更多推荐
1
0- 0
已为社区贡献1条内容
所有评论(0)