第四次DS博客作业
Q0.展示PTA总分
Q1.本章学习总结
1.1 学习内容总结
-
图的简介
- 在前面几章中，我们学习了“一对一”关系的线性表、“一对多”关系的树，而本章学习的图可以说是在树的基础上延申的“多对多关系”
- 图简单分类可以分成如上图的两种，左边的为无向图，右边的为有向图。例如左图中存在有v1->v3和v3->v1的关系，而右图中只有v1->v3的关系
- 在有向图中，指向某个顶点V的所有箭头数量和称为入度，由顶点V发散出的箭头数量和为出度
- 从一个顶点到另一顶点途径的所有顶点组成的序列（包含这两个顶点），称为一条路径。如果路径中第一个顶点和最后一个顶点相同，则此路径称为“环”。另外的，若路径中各顶点都不重复，则此路径被称为“简单路径”；同样，若回路中的顶点互不重复，此回路被称为“简单回路”
- 在前面几章中，我们学习了“一对一”关系的线性表、“一对多”关系的树，而本章学习的图可以说是在树的基础上延申的“多对多关系”
-
图的存储：邻接矩阵
- 对于图的存储，我们需要记录下有关系的两个顶点和这两个顶点连接的边，因此使用二维数组（邻接矩阵）或链表（邻接表）储存是不错的选择
- 在邻接矩阵中，两个顶点有关系则将值置为1，否则为0，无向图我们可以使用上三角矩阵储存（因为是对称的）
- 下图是一个无向图转换为邻接矩阵储存的方式，可以看出这个邻接矩阵关于绿色的线是对称的
/*邻接矩阵的定义与建立*/
typedef struct //邻接矩阵储存图的结构定义
{ int edges[MAXV][MAXV]; //邻接矩阵
int n,e; //记录图的顶点数，边数
} MGraph;
void CreateMGraph(MGraph& g, int n, int e) //建立邻接矩阵，n和e代表顶点数和边数
{
int a, b;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
g.edges[i][j] = 0; //初始化图，首先将所有顶点设为无关系
for (int i = 0; i < e; i++)
{
cin >> a >> b;
g.edges[a][b] = 1;
//g.edges[b][a] = 1; //如果是无向图的情况
}
g.e = e; g.n = n; //记录图的边数和顶点数
}
- 图的储存：邻接表
- 前面我们了解了邻接矩阵储存图的方式，但它的缺陷也很明显：容易造成空间浪费
- 假如我的图只有一条连接，1和999，这个情况下我们使用邻接矩阵的话，2-998完全就浪费了，因此我们需要邻接表来进行储存图
- 下图是邻接表储存同一个无向图的方式，可以与上文邻接矩阵的说明进行对照。邻接表的图的结构会比较多，在下面的图片中也会标注代码里的一些结构体
- 邻接表的建立前要注意初始化，同时使用头插法进行建表
/*邻接表的结构与建立*/
typedef struct ANode //储存每个顶点所拥有的边的结构
{ int adjvex; //该边的终点编号
struct ANode *nextarc; //指向下一条边的指针
int info; //可以用来储存该边的相关信息，如权重
} ArcNode;
typedef struct Vnode //记录顶点
{ int data; //可以储存顶点的一些信息
ArcNode *firstarc; //指向第一条边
} VNode;
typedef VNode AdjList[MAXV];
typedef struct
{ AdjList adjlist; //邻接表
int n,e; //图中顶点数n和边数e
} AdjGraph;
void CreateAdj(AdjGraph*& G, int n, int e)
{
int i, a, b;
ArcNode* p;
G = new AdjGraph;
for (i = 1; i <= n; i++)
G->adjlist[i].firstarc = NULL; //顶点全部初始化
for (i = 0; i < e; i++)
{
cin >> a >> b;
p = new ArcNode;
p->adjvex = b;
p->nextarc = G->adjlist[a].firstarc; //使用头插法建图
G->adjlist[a].firstarc = p;
/*p = new ArcNode; //无向图的情况
p->adjvex = a;
p->nextarc = G->adjlist[b].firstarc;
G->adjlist[b].firstarc = p;*/
}
G->n = n; G->e = e; //建立图的顶点数和边数
}
- 图的遍历：DFS
- DFS即为深度优先搜索，为了方便记忆，我们可以把它类比成树的先序遍历，即先输出根结点，再输出孩子结点（所以这里我们与树一样会用到递归）
- 它的步骤大致如下：
1.从图中v0出发，访问v0
2.找出v0的第一个未被访问的邻接点，访问该顶点。以该顶点为新顶点，重复此步骤，直至刚访问过的顶点没有未被访问的邻接点为止
3.返回前一个访问过的仍有未被访问邻接点的顶点，继续访问该顶点的下一个未被访问领接点
4.重复2、3步，直至所有顶点均被访问 - 以下图为例，分步解析DFS（图上箭头没有画好，所有的箭头应该都是双向的（或者不标方向），总而言之请想象它是个无向图）
1.首先新建并初始化一个visited数组，用于记录顶点是否被访问过（0和1代表未访问和访问过），假设从1开始，将visited[1]置为1
2.发现顶点1有未访问的邻接点2，将顶点2记录为已访问，以2为顶点继续下一次搜索
3.发现顶点2有未访问的邻接点5，将顶点5记录为已访问，以5为顶点继续下一次搜索
4.发现顶点5有未访问的邻接点6，将顶点6记录为已访问，以6为顶点继续下一次搜索
5.在顶点6我们发现6没有连接着未访问的邻接点了，回溯到上一级，寻找顶点5是否还有未访问的顶点，同理5也没有这样的邻接点，再回溯到上一个顶点2……
一直回溯到顶点1，发现1还连接着未访问的顶点3，将顶点3记录为已访问，以3为顶点继续下一次搜索
6.顶点3与顶点5有连接，但是顶点5已被访问过（visited[5]==1），同时顶点3也没有连接到其他未访问的顶点了，回溯到上一级，就是顶点1
顶点1连接着未访问的顶点4，顶点4记录为已访问
7.此时所有顶点都已经访问过了，我们便得到了一种DFS序列：1->2->5->6->3->4 - 需要注意的是，DFS的序列不是唯一的！特别是在无向图中，选取不同的顶点作为起点可以得到完全不同的遍历结果！
（例如下图中2->5->6->3->1->4、3->1->2->5->6->4等等都是合法的DFS序列！）
/*邻接矩阵DFS（连通图的情况！）*/
void DFS(MGraph g, int v) //v代表当前访问的顶点编号
{
cout << v << " "; //输出顶点
visited[v] = 1; //设置顶点v访问过
for (int i = 1; i <= g.n; i++) //遍历寻找下一个邻接顶点
if (visited[i] == 0 && g.edges[v][i] == 1) //如果该邻接点与当前顶点存在边且该邻接点尚未访问过
DFS(g, i); //则进入递归，从该节点继续DFS
}
/*邻接表DFS（也是连通图！）*/
void DFS(AdjGraph* G, int v) //同样的，v代表当前访问顶点的编号
{
ArcNode* p; //用于遍历顶点所接的链的临时变量
cout << v << " "; //输出顶点编号
visited[v] = 1; //设置顶点已被访问
p = G->adjlist[v].firstarc; //初始化p指向顶点v所连接的第一个结点
while (p != NULL) //遍历完顶点v所连接的所有结点
{
if (!visited[p->adjvex]) //如果结点p所带的数据（即为顶点编号）对应顶点尚未被访问
DFS(G, p->adjvex); //那么就进入递归从该节点继续DFS
p = p->nextarc;
}
}
- 图的遍历：BFS
- BFS即为广度优先搜索，同样的我们可以将它类比为树的层序遍历，即它先输出与起点距离为1的点、再输出距离为2的点，接下来是距离为3的顶点……
- 为了方便BFS实现，我们需要引入一个队列，BFS的步骤大致如下：
1.从图的某个起点的v0开始访问，同时将v0入队
2.当队列不为空时，让队首所储存的顶点v出队
3.检查顶点v的所有未访问邻接顶点u，并让顶点u进入队列
4.重复步骤2、3，直到队列为空 - 同样以上图为例，分步解析BFS（改不了图不好意思，请把它当作是个无向图）
1.首先初始化从访问记录的visited数组和队列queue。假设BFS从1开始，将1设置已访问并入队
2.出队队首即为1，发现顶点1与顶点2、3、4都有连接边，且它们都还未被访问，将2、3、4依次入队并将它们都设置为已访问
3.出队队首2，检查发现顶点2与顶点5有连接边且顶点5尚未被访问，将5入队并将其设置为已访问
4.出队队首3，发现顶点3与顶点5有连接边但顶点5已被访问，因此不做处理
出队队首4，其没有连接边，因此也不做处理
出队队首5，发现其与顶点6有连接边且顶点6还未被访问，将6入队并设置为已访问
5.出队队首6，其没有连接边，因此不做任何处理，也没有新元素入队
6.此时发现队列已空，BFS已完成，得到序列1->2->3->4->5->6 - 与DFS一样，BFS序列也不是唯一的，例如下图中2->1->5->3->4->6也是一个合法的BFS序列
/*邻接矩阵实现BFS（连通图）*/
void BFS(MGraph g, int v) //v代表BFS的起点编号
{
int queue[30] = { 0 }, front, rear; //使用数组模拟队列
int i;
queue[0] = v;
visited[v] = 1; //设置已访问标记
front = 0; rear = 1; //队列初始化
while (front != rear) //当队列不空时
{
for (i = 1; i <= g.n; i++) //遍历找与队首有连接的顶点
if (g.edges[queue[front]][i] == 1 && visited[i] == 0) //若该顶点尚未被访问且与队首有边
{
queue[rear] = i; //将其编号入队
visited[i] = 1; //并设置其已被访问
rear++; //队尾后移
}
cout << queue[front] << " ";
front++; //出队队首
}
}
/*邻接表实现BFS（连通图）*/
void BFS(AdjGraph* G, int v) //v为起点编号
{
int queue[30] = { 0 }, front, rear; //使用数组模拟队列
ArcNode* p;
queue[0] = v;
visited[v] = 1; //将起点设置为已访问
front = 0; rear = 1; //队列初始化
while (front != rear) //当队列不空
{
p = G->adjlist[queue[front]].firstarc; //令p指向队首顶点所连接的第一个结点
while (p != NULL) //遍历所有与其连接的结点
{
if (!visited[p->adjvex]) //如果该结点所带的数据（顶点编号）尚未访问过
{
queue[rear] = p->adjvex; //将其入队
visited[p->adjvex] = 1; //并将该顶点为已访问过
rear++; //队尾后移
}
p = p->nextarc;
}
cout << queue[front] << " ";
front++;
}
}
- 判断图是否连通
- 上面两份代码都是针对连通图的情况，对于非连通图的情况，我们的DFS/BFS结果就不完整
- 那如何判断图是否连通呢？最简单的方法就是在DFS和BFS的过程中，增加一个计数器，每次将一个新的顶点visited[v]置为1时，计数器+1，最后判断计数是否与顶点数相同即可
- 另一种方法，就是使用并查集。简单而言就是找所有顶点的祖先
- 如果所有顶点都有相同的一位祖先，那么该图就为连通图
- 这里我们只需要定义一个parents数组就可以模拟并查集，不需要另起结构体
/*并查集部分代码*/
int FindRoot(int parents[]，int x) //查找x的上级
{
if (x != parents[x]) //上级不是自己的情况
return FindRoot(parents，parents[x])); //递归找上级
else
return x; //上级即为自己
}
void GetUnion(int parents[]，int x，int y) //合并数据x和y
{
x = FindRoot(parents，x); //找x的上级
y = FindRoot(parents，y); //找y的上级
if (x != y) //两个顶点的上级不相同
parent[y] = x; //合并
}
- 查询图中某两点之间的路径
- 这部分其实与栈和队列中走迷宫相同，我们可以通过BFS的方式找到两个顶点间的最短路径
- 如果只是需要找是否有路径，那么可以使用DFS
/*BFS找某两点的最短路径*/
void BFS(AdjGraph* G, int v, int e) //v为起点编号，e为终点编号
{
int queue[30] = { 0 }, front, rear; //使用数组模拟队列
int path[30]; //该数组用于储存路径
ArcNode* p;
queue[0] = v;
path[v] = -1; //起点初始化
visited[v] = 1; //将起点设置为已访问
front = 0; rear = 1; //队列初始化
while (front != rear) //当队列不空
{
if (queue[front] == e) //到达终点
break;
p = G->adjlist[queue[front]].firstarc; //令p指向队首顶点所连接的第一个结点
while (p != NULL) //遍历所有与其连接的结点
{
if (!visited[p->adjvex]) //如果该结点所带的数据（顶点编号）尚未访问过
{
queue[rear] = p->adjvex; //将其入队
visited[p->adjvex] = 1; //并将该顶点为已访问过
rear++; //队尾后移
path[p->adjvex] = queue[front]; //储存路径
}
p = p->nextarc;
}
front++;
}
if (queue[front] == e) //到达终点，输出路径
for (int i = e; path[i] != -1; i = path[i])
cout << i << " ";
else
cout << "No path!";
}
- 最小生成树：Prim算法
- 什么是最小生成树？ 包含原图中的所有 n 个结点，并且有保持图连通的最小权值
- Prim算法的大致步骤：
1.首先选出一个点作为初始顶点，计算所有与之相连接的点的距离，将起点放入集合V，剩余顶点放入集合E
2.选取集合V和集合E中权值最小的边（V->E），将其加入最小生成树中，并将集合E中的该顶点放入集合V中
3.重复步骤2直到所有顶点都在集合V中 - Prim算法不适合用于带权有向图？ 这其实和图是有向图还是无向图，这两者之间没有必然的联系。但是带权有向图有这么一种情况：两个顶点来和回的权值不一样！这就导致了问题的产生。无向图就不会产生这种情况
- 该算法的时间复杂度为 O(n^2)，适合邻接矩阵进行操作
- 具体案例分析（主要对lowcost数组说明）：
1.我们以下图为例分析Prim算法，从顶点1开始，首先初始化lowcost数组，值为与顶点1的距离{0,2,1,99999,8}
2.在集合V（此时只有1）中找与集合E（2、3、4、5）相连且权值最小的边，发现顶点3与1的距离最小
将3加入到集合V中（令lowcost[3]=0），同时修改与3有关的顶点的lowcost数组值（与3的距离小于原lowcost数组中的数值时进行修改，修改后lowcost数组为{0,2,0,5,6}）
3.在集合V（此时有1、3）中找与集合E（2、4、5）相连且权值最小的边，发现顶点2与1的距离最小
将2加入到集合V中，同时修改与2有关的顶点的lowcost数组值（修改后lowcost数组为{0,0,0,3,6}）
4.在集合V（此时有1、3、2）中找与集合E（4、5）相连且权值最小的边，发现顶点4与2的距离最小
将4加入到集合V中，同时修改与4有关的顶点的lowcost数组值（修改后lowcost数组为{0,0,0,0,2}）
……以此类推，直到所有顶点都进入集合V中 - 于是下图Prim算法生成的最小生成树为：{（1，3），（1，2），（2，4），（4，5）}，权值=1+2+3+2=8
#define INF 99999
void Prim(MGraph g, int v) //v为输入的起点
{
int lowcost[MAXV], min, closest[MAXV]; //lowcost数组储存权值，0代表对应顶点已走过，closest记录前驱
int i, j, k;
int total = 0; //记录总权值
for (i = 0; i < g.n; i++) //初始化两个数组
{
lowcost[i] = g.edges[v][i]; //没有连接的两个边该值为99999
closest[i] = v;
}
lowcost[v] = 0;
for (i = 1; i < g.n; i++) //起点已经在V中，所以还要找n-1个顶点
{
min = INF;
for (j = 0; j < g.n; j++) //在还未找过的顶点中找出离已找过顶点最近的顶点k
if (lowcost[j] != 0 && lowcost[j] < min)
{
min = lowcost[j];
k = j; //k为当前找到的最近顶点的编号
}
printf("边(%d,%d)加入了最小生成树，权值为:%d
", closest[k], k, lowcost[k]);
total += lowcost[k];
lowcost[k] = 0; //标记顶点k已经加入
for (j = 0; j < g.n; j++) //修改未访问过顶点对应的数组lowcost和closest的值
if (lowcost[j] != 0 && g.edges[k][j] < lowcost[j])
{
lowcost[j] = g.edges[k][j];
closest[j] = k;
}
}
cout << "该最小生成树的权值为：" << total << endl;
}
- 最小生成树：Kruskal算法
- 与Prim算法不同，Prim算法注重于顶点，Kruskal算法更注重于边
- 使用上并查集能够更好的理解该算法
- 该算法可以这样理解：取所有的边集合中取权值最小的边，若该条边的两个顶点拥有不同的祖先（并查集，或者理解为将其加入最小生成树后不会形成环），则将它们加入最小生成树
- 算法的时间复杂度为 O(eloge)，适合邻接表进行操作
- 具体样例分析
1.首先将所有的边进行排序，{1，2，2，3，5，6，8}，并保存每条边对应的两个顶点
2.首先取第一条边1，对两个顶点1、3进行并查集的合并，par[3]=par[1]=1，将该段子树加入最小生成树
3.接着取第二条边2，对两个顶点1、2进行并查集的合并，par[2]=par[1]=1，并将该段子树加入最小生成树
4.第三条边2，两个顶点为4、5，进行合并，par[5]=par[4]=4，加入最小生成树
5.取第四条边3，两个顶点为2、4，进行合并，par[5]=par[4]=par[2]=1，加入最小生成树
6.对于k个顶点，完成一个最小生成树需要k-1条边，于是该棵最小生成树生成完毕
生成结果：{（1，3），（1，2），（4，5），（2，4）}
typedef struct //边的结构体
{
int u; //边的起始顶点
int v; //边的终止顶点
int w; //边的权值
} Edge;
/*并查集代码还请自行向上翻阅*/
void Kruskal(AdjGraph* g)
{
int i，j，k，u1，v1，sn1，sn2;
int par[MAXSize];
ArcNode* p;
Edge E[MAXSize]; //边集
k = 1;
for (i = 0; i < g.n; i++)
{
p = g->adjlist[i].firstarc;
while (p != NULL) //初始化
{
E[k].u = i;
E[k].v = p->adjvex;
E[k].w = p->weight;
k++;
p = p->nextarc;
}
HeapSort(E，g.e); //采用堆排序对E数组按权值递增排序
MakeSet(par，g.n); //初始化并查集
k = 1; //k表示当前构造生成树的第几条边，初值为1
j = 1; //E中边的下标，初值为1
while (k < g.n) //n-1条边
{
u1 = E[j].u;
v1 = E[j].v; //取一条边的头尾顶点编号u1和v2
sn1 = FindRoot(par，u1);
sn2 = FindRoot(par，v1); //分别得到两个顶点所属的集合编号
if (sn1 != sn2) //两顶点属不同集合
{
printf(" (%d，%d):%d
"，u1，v1，E[j].w);
k++; //生成边数增1
GetUnion(par，u1，v1);//将u1和v1两个顶点合并
}
j++; //扫描下一条边
}
}
}
- 最小生成树的应用：PTA7-6 通信网络设计
- 本题代码其实就是普通的对最小生成树的问题，加上了一个找不到合适的最小边的情况（图不连通）
- 我是使用了Prim+BFS
/*伪代码与思路*/
Prim函数：
初始化cost为0，初始化lowcost数组，第i个元素的值为图中顶点i到顶点1的距离（不存在连线则为99999）
令lowcost[1]=0，防止重复访问
For i=2 to 图G的顶点数 do
重置min=99999，用于记录最小边
遍历lowcost数组
If lowcost[j]小于min且顶点j未被搜寻（即lowcost[j]值为0） then
修改min值为lowcost[j]，记录k=j（最小边对应的顶点）
End if
若找不到合适的最小边，函数结束，返回-1
cost值加上lowcost[k]的值，并记录顶点k被搜索过
遍历lowcost数组，将值不为0且值比图G中k到j连线权值大的进行修正
End for
返回cost的值
BFS函数：
初始化访问标记数组全置为0，数组queue模拟队列
初始化cnt值为-1，初始化储存int类型的vector ve[55]
For i=1 to G的顶点数 do
如果顶点i还未被访问，则将i入队，加入到ve[++cnt]中，并记录i访问过
While 队列不空 do
取队首元素，将与队首元素有连接且未访问过的结点入队、加入到ve[cnt]中，同时记录它访问过
End while
出队队首元素
End for
遍历vector ve，将其每部分都从大到小排序，按题目要求输出
/*具体代码实现*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define inf 99999
typedef struct MGraph
{
int n, e;
int edge[55][55];
}Graph;
void CreateGraph(Graph*& g, int n, int e)
{
int i, j;
int a, b, c;
g = new Graph;
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
g->edge[i][j] = inf;
for (i = 0; i < e; i++)
{
cin >> a >> b >> c;
g->edge[a][b] = g->edge[b][a] = c;
}
g->n = n; g->e = e;
}
int Prim(Graph* g)
{
int lowcost[55];
int i, j, k, min;
int cost = 0;
for (i = 1; i <= g->n; i++) //初始化lowcost数组
lowcost[i] = g->edge[1][i];
lowcost[1] = 0;
for (i = 2; i <= g->n; i++)
{
min = inf;
for (j = 1; j <= g->n; j++) //在没搜寻过的部分找最小边
{
if (lowcost[j] && lowcost[j] < min)
{
min = lowcost[j];
k = j;
}
}
if (min == inf) //找不到合适的边，即不互联的情况
return -1;
cost += lowcost[k];
lowcost[k] = 0;
for (j = 1; j <= g->n; j++) //修正lowcost的值
{
if (lowcost[j] && lowcost[j] > g->edge[k][j])
lowcost[j] = g->edge[k][j];
}
}
return cost;
}
void BFS(Graph* g)
{
int visited[55] = { 0 }, queue[55];
int front, rear;
int i, j, k;
int cnt = -1;
vector<int>ve[55]; //记录每个部分包含的顶点
front = rear = 0;
for (i = 1; i <= g->n; i++) //因为图被分成多个部分，加上一个外层循环保证所有点都能遍历
{
if (!visited[i])
{
visited[i] = 1;
queue[rear++] = i;
ve[++cnt].push_back(i);
}
while (front != rear)
{
k = queue[front];
for (j = 1; j <= g->n; j++)
{
if (!visited[j] && g->edge[k][j] != inf)
{
visited[j] = 1;
queue[rear++] = j;
ve[cnt].push_back(j);
}
}
front++;
}
}
for (i = 0; i <= cnt; i++)
{
sort(ve[i].begin(), ve[i].end()); //将每部分从大到小排序
cout << i + 1 << " part:" << ve[i][0];
for (j = 1; j < ve[i].size(); j++)
cout << " " << ve[i][j];
cout << endl;
}
}
int main()
{
Graph* g;
int n, e;
int a;
cin >> n >> e;
CreateGraph(g, n, e);
a = Prim(g);
if (a == -1)
{
cout << "NO!" << endl;
BFS(g);
}
else
{
cout << "YES!" << endl;
cout << "Total cost:" << a << endl;
}
return 0;
}
- 最短路径：Dijkstra算法
- 什么是最短路径？ 从图中某一顶点（源点）到达另一顶点（终点）的路径可能不止一条，找到一条路径使得沿此路径上各边的权值总和（称为路径长度）达到最小，该条路径就叫做最短路径
- 该算法的步骤大致如下：
1.选择某个起点V0，令集合S={V0}，集合E={其他顶点}，初始化所有距离，若V0到顶点V有边，则其值即为权值，若不存在，则为Inf
2.从还未走过的顶点中选取一个其距离值为最小的顶点V，加入S，对E中顶点的距离值进行修改：若加进V作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值
3.重复上述步骤，直到S中包含所有顶点 - 注意，该算法不适用于图中有负权值的情况
- 需要两个数组，dist储存距离、path数组储存路径（通过回溯）
- 具体样例分析（求下图中从0到其他顶点的最短路径）：
1.首先初始化dist和path数组，对dist数组，若顶点与起点有边，则其值为权值，否则为INF；对path数组，若顶点与起点右边，则值为起点（代表该顶点的前驱为起点），否则为-1
2.从E中选取顶点1，令其加入S，判定其与E中其他顶点间的距离：2在E中，且2原最短距离大于当前路径距离加上从顶点1到顶点2的距离，因此修改顶点2的最短距离，并修改顶点2的前驱为1
对于顶点3，由于1与3之间不存在边，因此不对它进行处理
对于顶点4，原来到顶点4的距离为INF（因为起点与4没有边），通过当前路径从1到4必是最短路径，因此修改顶点4对应的内容
对于顶点5，由于1与5之间不存在边，因此不处理
3.继续从E中选取顶点2，以此类推
关于最终结果，在选取了起点v的情况下，设顶点为e，dist[e]即为从v到e的最短距离，从e->path[e]->path[path[e]]->……->-1（起点的前驱设为-1），通过path数组的回溯即可得到路径上各点
void Dijkstra(MGraph g, int v) //求从起点v到其他顶点的最短路径
{
int path[MAXV], dist[MAXV], s[MAXV];
int i, j, k;
int min;
for (i = 0; i < g.n; i++)
{
dist[i] = g.edges[v][i]; //初始化数组
s[i] = 0; //s置空
if (g.edges[v][i] == INF)
path[i] = -1; //无边时前驱为-1
else
path[i] = v; //有边时前驱即为起点
}
s[v] = 1; //起点加入S
for (i = 0; i < g.n; i++)
{
min = INF;
for (j = 0; j < g.n; j++) //找最短距离的顶点
{
if (!s[j] && dist[j] < min)
{
k = j;
min = dist[j];
}
}
s[k] = 1; //该顶点加入S
for (j = 0; j < g.n; j++)
{
if (!s[j]) //修改不在S的中顶点的距离
{
if (dist[j] > dist[k] + g.edges[k][j] && g.edges[k][j] != INF)
{
dist[j] = dist[k] + g.edges[k][j];
path[j] = k;
}
}
}
}
/*输出路径，此处略*/
}
- 最短路径：Floyd算法
- 与前一个算法类似，不过它不需要输入起点，直接可以求任意两点间的最短路径（上一种算法再加上外部循环也可以做到，且时间复杂度相同）
- 这个算法代码看起来很简单，但是实际理解起来我又说不清楚，此处只好引用该篇文章对floyd算法的解释
-
从任意节点A到任意节点B的最短路径不外乎2种可能，1是直接从A到B，2是从A经过若干个节点到B，所以，我们假设dist(AB)为节点A到节点B的最短路径的距离，对于每一个节点K，我们检查dist(AK) + dist(KB) < dist(AB)是否成立，如果成立，证明从A到K再到B的路径比A直接到B的路径短，我们便设置 dist(AB) = dist(AK) + dist(KB)，这样一来，当我们遍历完所有节点K，dist(AB)中记录的便是A到B的最短路径的距离
- 该算法的缺点也相当明显：空间复杂度过高，空间浪费明显
由于对该算法的理解不足，在这里就无法举例分析了，还请另寻高明
void Floyd(MGraph g) //求每对顶点之间的最短路径
{
int A[MAXV][MAXV];
int path[MAXV][MAXV]; //建立path数组
int i, j, k;
for (i = 0; i < g.n; i++)
for (j = 0; j < g.n; j++)
{
A[i][j] = g.edges[i][j];
if (i != j && g.edges[i][j] < INF)
path[i][j] = i; //表示从i到j，前驱为i
else
path[i][j] = -1; //i与j没有边
}
for (k = 0; k < g.n; k++) //注意i、j、k的顺序！！！！！
for (i = 0; i < g.n; i++)
for (j = 0; j < g.n; j++)
if (A[i][j] > A[i][k] + A[k][j]) //找到更短路径，特别注意i、j、k选取哪两个！！
{
A[i][j] = A[i][k] + A[k][j]; //修改路径长度
path[i][j] = k; //修改经过顶点k
}
}
- 最短路径的应用：PTA7-6 旅游规划
- 本题也是相当基础的对最短路径的考察，在这里我们不需要考虑前驱，只要考虑一个额外的花费
- 对这个花费的处理也相当简单，当路径修改时，花费像举例一样修改即可，当路径修改前后距离一致时，对比保留更低花费的即可
- 还有一点要注意的是！该题建图的时候要建无向图！
/*伪代码和思路*/
Dijkstra函数：
初始化dist数组、money数组、s数组
遍历图中所有节点
循环找不在S中的最短dist，其对应顶点为k
顶点已选，让其加入S
循环修正不在S中的顶点i对应的dist与money数组
若顶点i的最短距离大于k的最短路径加上k到i的距离时
dist与money数组进行修正
若两者相等时
dist数组不进行修正，money数组取值更小的哪一个
结束循环
/*具体代码*/
#include<iostream>
using namespace std;
#define inf 99999
typedef struct MGraph
{
int n, e;
int edge[505][505];
int cost[505][505];
}Graph;
void CreateGraph(Graph*& G, int n, int e)
{
int i, j;
int a, b, c, d;
G = new Graph;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
{
G->edge[i][j] = inf;
G->cost[i][j] = inf;
}
for (i = 0; i < e; i++)
{
cin >> a >> b >> c >> d;
G->edge[a][b] = c;
G->cost[a][b] = d;
G->edge[b][a] = c;
G->cost[b][a] = d;
}
G->n = n; G->e = e;
}
void Dijkstra(Graph* G, int v, int e)
{
int dist[505], s[505], money[505];
int min, i, j, k;
for (i = 0; i < G->n; i++) //初始化
{
dist[i] = G->edge[v][i];
money[i] = G->cost[v][i];
s[i] = 0;
}
s[v] = 1; //起点进入S
dist[v] = money[v] = 0; //初始化S对应的数组
for (i = 1; i < G->n; i++)
{
min = inf;
for (j = 0; j < G->n; j++)
if (dist[j] < min && !s[j]) //找最短dist及其对应顶点k
{
min = dist[j];
k = j;
}
s[k] = 1; //k加入S
for (j = 0; j < G->n; j++)
{
if (!s[j]) //修改不在S中的顶点的dist和money数组
{
if (dist[j] > dist[k] + G->edge[k][j] && G->edge[k][j] != inf)
{
dist[j] = dist[k] + G->edge[k][j];
money[j] = money[k] + G->cost[k][j];
}
else if (dist[j] == dist[k] + G->edge[k][j] && G->edge[k][j] != inf) //两者相同时保留花费更少的
{
if (money[j] > money[k] + G->cost[k][j])
money[j] = money[k] + G->cost[k][j];
}
}
}
}
cout << dist[e] << " " << money[e];
}
int main()
{
int n, e, start, end;
Graph* G;
cin >> n >> e >> start >> end;
CreateGraph(G, n, e);
Dijkstra(G, start, end);
return 0;
}
- 拓扑排序
- 拓扑排序是什么？ 简单来说，就是每个顶点只能出现1次，且若有A->B的关系，那么A必须出现在B前面的一种序列
- 简单来说它的步骤如下：
1.从有向图中选取一个没有前驱的顶点，并输出
2.从有向图中删去此顶点以及所有从该顶点出发的边（以它为尾的弧）
3.重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止 - 只有有向无环图才可以进行拓扑排序！因此我们可以通过拓扑排序来检查图中是否有回路
- 对于函数实现拓扑排序，我们常使用邻接表结构，因为我们可以在头结点结构中加入一个变量，用于记录该顶点的入度；还需要一个栈辅助排序
- 而对于拓扑排序判断图中是否有回路，我们常在拓扑排序的函数中新增计数器，每次出栈让其值加一，最后判断值是否与顶点数相同来判定图是否有回路
- 举例说明（对应上图）
1.在该有向图中，我们发现只有顶点a入度为0，将其入栈，出栈栈顶元素a，计数器+1，将与其对应的边删除，因此我们将a->b、a->c、a->e三条边删除（即为对b、c、e三个点入度减一）
发现b、e顶点入度减1后已为0，将其入栈，顶点c入度减1后为1，因此不处理
2.出栈顶点e，计数器+1，他与顶点d有边，将d顶点入度减1后发现其入度为1，因此不处理
3.出栈顶点b，计数器+1，它与顶点c有边，且c顶点入度减一后为零，因此将c入栈
4.出栈顶点c，计数器+1，它与顶点d有边，d顶点入度减一后为零，将d入栈
5.将d出栈，计数器+1，它没有任何邻接边，不做处理
6.发现栈空，且计数器的值与顶点数相同，图中没有回路，拓扑排序完成
/*邻接表中顶点的结构体定义中新增了一个count，用于记录顶点的入度*/
void TopSort(AdjGraph* G)
{
int i, j;
int stack[105]; //数组模拟栈
int show[105]; //输出拓扑排序
int top = -1;
int cnt; //统计拓扑排序中的顶点数
ArcNode* p;
for (i = 0; i < G->n; i++)
G->adjlist[i].count = 0; //首先初始化，让所有顶点入度都为0
for (i = 0; i < G->n; i++)
{
p = G->adjlist[i].firstarc;
while (p)
{
G->adjlist[p->adjvex].count++; //有边存在时让入度+1
p = p->nextarc;
}
}
cnt = 0; //初始化
for (i = 0; i < G->n; i++)
if (!G->adjlist[i].count) //首先遍历一边将所有入度为0的结点入栈
stack[++top] = i;
while (top != -1) //栈不空
{
i = stack[top--]; //出栈并取栈顶元素
show[cnt++] = i; //将栈顶元素加入到输出的序列中，并将已排序顶点数+1
p = G->adjlist[i].firstarc;
while (p)
{
G->adjlist[p->adjvex].count--; //所有与该顶点有连接的顶点对应入度-1
if (!G->adjlist[p->adjvex].count) //当入度为零时，让该顶点进栈
stack[++top] = p->adjvex;
p = p->nextarc;
}
}
if (cnt < G->n) //当拓扑排序顶点数与图的顶点数不相同时，代表图中有回路，拓扑排序失败
cout << "error!";
else //否则正常输出
{
cout << show[0];
for (i = 1; i < G->n; i++)
cout << " " << show[i];
}
}
- 关键路径
- 什么是关键路径？ 从有向图的源点到汇点的最长路径，又叫关键路径
- 什么是关键活动？ 关键路径中的边
- 我该怎么求关键路径？
1.对有向图拓扑排序
2.根据拓扑序列计算事件（顶点）的ve（最早开始时间），vl（最晚开始时间）数组
ve(i)= 所有 前驱顶点的ve值 + 前驱顶点到当前顶点的权值 取最大值（起点的ve[i]=0，从起点向终点算）
vl(i)= 所有 后继顶点的ve值 - 当前结点到后继顶点的权值 取最小值（终点的vl[i]=ve[i]，从终点向起点算）
3.计算关键活动的e[], l[]。即边的最早、最迟时间
例如对应边jk：
e(i) = ve(j)
l(i) = vl(k) - jk边的权值
4.找e = l边即为关键活动
5.关键活动连接起来就是关键路径 - 举个栗子
1.2 学习体会
- 进入了“图”章节的学习，虽然使用的代码又回到了上学期所学的二维数组和稍微复杂了一点的链表，但可以明显感觉到与前及章的不同
- 首先在课程中，似乎从更多的讲理论、讲代码变成了讲算法，也许这会是将来上课的趋势？
- 其次，图与本学期学习的其他章节也尤其紧密相关，我们常常要借助栈（如拓扑排序）、队列（如BFS）、树（kruskal算法）来实现一个功能，可以说综合性提高了很多
- 最后，我认为图是与实际生活中联系最大的部分，图的“多对多”的关系更符合我们日常生活中的种种关系，可能也是需要最花心思的一个部分了
- 再说回到算法，感觉算法还是本章学习中最困难的一个部分，手在键盘上却敲不出个所以然的情况偶尔会出现，这可能会是接下来的学习中要加强的一部分
Q2.阅读代码
2.1 冗余连接 II
2.1.1 设计思路
- 本题要求删除冗余连接，实现一条“单行路”形式的有向图
- 这就意味着，图上的所有顶点都只会有一个共同的根节点，除了起点外其他顶点的入度均为1，我们很容易可以想到使用并查集来解决问题
- 而本题似乎没有不删除的情况（并不确定，但是看代码是这样），且本题只要求删除一条边
- 时间复杂度为O(n)，空间复杂度为O(n)
- 因此题解代码分为两种情况：
1.若所有结点的入度均为1，这就意味着图里存在环，那么我们需要删除形成环的最后一条边
对于这个情况，题解代码使用的是 当两个顶点找祖先合并时 若两个顶点拥有相同的祖先 ，那么要删除的就是这两个顶点形成的边
可能光看文字会有点没看懂，但看下图很容易就能理解了
2.若有一个顶点的入度为2，那么要删除的边肯定为该顶点连接的两条边选一（因为本题只删一条边），保留能保持图符合要求的那条边
对于这个状况，题解代码首先 保存了后出现的那条边的两个顶点 ，然后判断先前出现的那条边能否与其他边构成符合条件的图（同样是检查两个顶点是否有同样的祖先）
若前出现的边符合，那就删保存的边；如果先出现的边不符合，那么就删先出现的边，保留之前保存的边
2.1.2 伪代码
/*这里就不写并查集部分的伪代码了
就说明一下合并的函数为bool类型，若两个顶点祖先相同（不合并）返回false代表合并失败，否则合并祖先并返回true*/
vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
初始化数组degree用于保存每个顶点的入度，初值为0
初始化变量find作为记录图中是否有入度为2的顶点
for 遍历所有边 do
对应顶点入度+1
if 该顶点入度为2
保存最后出现的这条边的两个顶点，设置find值为1，退出循环
end if
end for
初始化并查集数组
if 所有点入度为1 then
遍历所有边，并将每个边的两个顶点进行并查集合并，若合并失败即这两个顶点合成的边为删除的边
返回这条边，函数结束
end if
for 遍历所有边 do
如果是先前保存的边就跳过
对边的两个顶点进行合并，若合并失败则返回入度为2的顶点的另一条边，结束函数
end for
返回保存的边
}
2.1.3 运行结果
2.1.4 分析
- 本题其实就是对并查集应用的升级，题解作者将合并函数设置为bool类型，通过返回的true和false判断图是否符合要求，是很聪明的选择
- 题解的代码可能比较难理解的只有 for (auto i : edges) 这一部分
- 他其实起到的作用就是遍历edges这个vector，auto让编译器通过初始值来推算变量的类型
- 那么循环里面的i[0]，i[1]又是什么呢？我们可以知道edges是vector<vector
>类型的 （其实就是二维数组） - 于是我判断，这里的i[0]就代表的是edges[j][0]，i[1]代表的是edges[j][1]（其中j为当前循环次数）
- 所以如果输入[0,1],[1,2]，在第一次循环时的i[0]=0，在第二次循环时i[1]=2
- 上面的部分其实是通过它后半部分的代码我推导出来的结论，因为一开始我也看不懂
- 题解代码（我个人认为）可能存在的问题就是对变量i的类型定义，在最后的循环里它既是auto类型，又有int类型，对于代码阅读来讲不是很舒服
2.2 颜色交替的最短路径
2.2.1 设计思路
- 本题看题目要求看似求最短路径，但实际上因为它不是带权值的图，所以并不需要用到最短路径相关的两个算法
- 本题不同的地方在于：它的路径被分为两种颜色，我们走的最短路径必须得是两种颜色不断交替的路径
- 例如上图中，0->2->3就不是一个合法的路径，0->1->2->3和0->1->3都是合法路径
- 由于是红蓝交替，所以这意味着上一步的路径颜色与下一步的路径颜色一定不相同
- 两份代码中BFS是根据每次队首的边的颜色决定下一次的颜色，而DFS代码则是通过不断的 !color （取0、1为红色和蓝色）来实现红蓝交换的效果
- 又因为本题中可能有环，并且可能存在平行边（例如上图中0->1同时存在红色和蓝色两条边），我们的数组不能再局限于顶点的问题，而是要变成边的问题！
- BFS的代码在这里都使用了三维数组来保存visited[i][j][k]，两个代表顶点，一个代表颜色，并记录该条边是否访问过；而DFS代码的三维数组只用于存顶点和颜色，不保存是否访问过
- 看到最短我们通常会想到BFS，但实际上DFS也是OK的
- 为什么同时展示两份代码，是希望不要看到题目就产生思维定势，带权最短路径就一定是dijkstra算法，走迷宫什么的最短步数一定是bfs，这样很容易被限制住思维；可以看到两份代码的对比，首先简洁程度就截然不同，一个使用了三重循环，另一个则是循环递归。我认为这里的两份代码DFS是优于BFS的（实际上这份DFS代码用时击败了98.76%的人，内存占用击败了100%的人，确实是份精妙的代码）
2.2.2 伪代码
/*这里就只展示DFS那份了*/
void dfs(vector<vector<vector<int> > >& g, int col, int i, vector<vector<int> >& res) {
for (auto j : g[col][i]) { //遍历当前颜色i->j顶点所拥有的边
if (res[i][col] + 1 < res[j][!col]) { //与另一种颜色的路径长度判断
res[j][!col] = res[i][col] + 1; //这里通过不断的!col来实现不同颜色的交替，保存更短的路径
dfs(g, !col, j, res); //切换另一种颜色进入下一次递归
}
}
}
vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& red_edges, vector<vector<int>>& blue_edges) {
初始化二维动态数组rg、bg用于保存对应颜色的边（从red_edges和blue_edges中读值，如rg[i][0]=j表示顶点i第一条红色的边指向j）
初始化三维动态数组(?)g，第一个下标代表颜色，随后跟着rg和bg数组
初始化记录长度的数组res，第一个下标代表顶点号，第二个下标代表红蓝色，初始化为INF
res[0] = {0, 0};
由红色边为起点进行dfs
由蓝色边为起点进行dfs
vector<int> out(n);
for i=0 to n do
i顶点对应的最小长度为res[i][0]/res[i][1]两种取小值
若最小值为INF代表该顶点没有合适的路径，对应修改长度为-1
end for
}
2.2.3 运行结果
2.2.4 分析
对于DFS代码中的那个数组g，我也不知道叫他三维数组是否合适- 本题可能说难也不算太难，我认为BFS那份代码是比较好写且好想到的，DFS这份代码优秀在对时间和空间的优化上做到了最佳
- 其中我认为它在DFS中的!col实现两种颜色之间的不断交替向下寻找是最优秀的部分
- 还有就是两份代码都共同将BFS和DFS的着重点从顶点转移到了边上，这是一种全新的DFS/BFS思路，有了这个思路就不会被DFS/BFS会有边访问不到的状况所卡住了
- 例如本次PTA7-1 图着色问题，我一开始是使用BFS进行判断，最终被一个测试点“卡不重复访问顶点”给卡住了，原因就是这两种搜索当某个顶点访问过以后，就不会再进行访问了（例如我同时有边1->2和3->2，顶点2先前已经通过顶点1访问了，在顶点3就不会再对顶点2进行判断，也就是3->2这条边访问不到了）
- 另外BFS的代码中运用到了pair<int,int>，相当于把两个数据组合成一个数据（这两个数据可以是不同类型的，例如pair<int,string>），可以通过first和second来访问两个数据的值
2.3 项目管理
2.3.1 设计思路
- 本题看题意就可以明白是要使用拓扑排序对项目排序
- 难点在于题目中有多个小组，且还存在一些不属于任何小组的孤立点，甚至孤立点也有需要先置完成的任务
- 同时，由于本题的结构甚至没有给我们任何一个图的结构（邻接矩阵或邻接表），我们很难找到拓扑排序的起始点和终点
- 因此题解代码作者使用了这样一个思路：对于每个在同一组的项目，添加一个源点和汇点
该组中项目对不在该组中的项目的依赖关系可以表示为该组的源点依赖于其他组的汇点，最后删掉源点和汇点即可 - 看晕了吗？看张图理下思路
- 该图中有0~7号项目，它用的什么作为源点和汇点？ 使用了大于7的数字作为源点和汇点，对于最后的删除也很方便
- 由图得知项目1需要项目6前置完成，且1是不属于任何一个小组的项目（孤立点），它的依赖关系怎么表示？ 项目1自成一组，它的源点依赖于其他组的汇点，所以它的源点就是项目6所在小组的汇点10
- 所以上图的拓扑排序为[0, 7, 8, 6, 3, 4, 10, 9, 2, 5, 11, 1]，在删除源点和汇点后得到答案[0, 7, 6, 3, 4, 2, 5, 1]
2.3.2 伪代码
/*这里拓扑排序的伪代码我真的写不来。。这里写注释吧*/
bool topSort(vector<unordered_set<int>>& al, int i, vector<int>& res, vector<int>& stat) {
if (stat[i] != 0) return stat[i] == 2; //用于判断图是不是形成了环
stat[i] = 1; //第一次标记
for (auto n : al[i]) //利用DFS进行拓扑排序
if (!topSort(al, n, res, stat)) return false; //若无环则继续递归，否则返回false
stat[i] = 2; //第二次标记，代表该点已排序完成
res.push_back(i); //加入到res数组中
return true; //拓扑排序成功
}
vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
vector<int> res_tmp, res(n), stat(n + 2 * m);
vector<unordered_set<int>> al(n + 2 * m);
for I=0 to n do
if I不等于-1（i属于某个小组）
向al[n + group[i]]插入数据i （建源点）
向al[i]插入数据(n + m + group[i]) （建立该点指向的汇点）
end for
for遍历顶点i的前置点j
if i不是孤立点且i与j属于同一组 向al[j]插入数据i
else
若i是孤立点，则ig=i，否则ig=n+group[i]
若i是孤立点，则jg=j，否则ig=n+m+group[i]
向al[jg]插入数据ig
end if
end for
end for
for n = al.size() - 1 to 0
若拓扑排序不形成环，则继续排序，函数中传入的参数i为这里的n，拓扑排序结果存入res_tmp；若拓扑排序有环代表没有合适的解决方案，返回空列表
翻转res_tmp
将res_tmp中的数据去除源点和汇点后复制到res中（其实就是不复制大于项目编号的数字）
return res;
}
2.3.3 运行结果
虽然和预期结果不一样，但是题目中说明：如果存在多个解决方案，只需要返回其中任意一个即可，所以该结果也是OK的（可以根据设计思路中那张图进行一次排序~）
2.3.4 分析
- 其实本题的最难点基本已经在设计思路部分讲完了，还有的可能就是它递归进行拓扑排序的方法与我们目前接触的完全不同，可能会有点懵
- 题解代码中最巧妙的还是利用了大于项目编号的数字去作为源点和汇点，明白了这部分题解代码也就明白了
- 同时由于vector<unordered_set
> al它中间的set类型，也避免了重复点的问题 - 非常多题解代码本题是运用了双层拓扑排序（可以点进去看本题题解，基本都是双层的），但是这段代码只使用了一层，是它对比其他代码的优势点
但是题解代码一点注释也没有看着真的是很难过了