【数据结构】ds笔记8-图

本篇笔记总结DSPv2b_6(图) for student内的相关内容。配图太多不是因为不抽象，而是因为太抽象。最后，本人学艺不精，只是一边看着ppt一边敲敲改改，如有疏漏，欢迎提出喵~o( =∩ω∩= )m

where is my tutu

1 图的基本概念

1.1 图的定义

1. 图是由顶点的非空有穷集合与顶点之间关系(边或弧)的集合构成的结构, 通常表示为G=(V,E)。其中,V为顶点集合,E为关系(边或弧)的集合。

2. 一条边或弧的表示

   1. 图形

      

   2. 符号

      (v_i, v_j)或<v_i, v_j>

   3. 语言

      顶点v_i与v_j是这条边的两个邻接点。

      这条边依附于顶点v_i和顶点v_j。

3. 例：

   

1.2 图的分类

1. 无向图：对于(v_i, v_j)∈E，必有(v_i, v_j)∈E，并且偶对中顶点的前后顺序无关。
2. 有向图：<v_i, v_j>∈E是顶点的有序偶对。
3. 网（络）：与边有关的数据称为权，边上带权的图称为网络。

1.3 名词术语

1. 顶点的度：依附于顶点v_i的边的数目，记为TD(v_i)

   对于有向图来说，有：

   • 顶点的出度：以顶点v_i为出发点的边的数目，记为OD(v_i)。
   • 顶点的入度：以顶点v_i为终止点的边的数目，记为ID(v_i)。
   • TD(v_i) = OD(v_i) + ID(v_i)

   结论：

   • 对于具有n个顶点，e条边的图，有：

     \[ \frac{1}{2}e = \sum_{i=1}^{n}TD(v_{i}) \]

   • 具有n个顶点的无向图最多有n(n-1)/2条边。

   • 具有n个顶点的有向图最多有n(n-1)条边。

   边的数目达到最大的图称为完全图。边的数目达到或接近最大的图称为稠密图，否则，称为稀疏图。

2. 路径和路径长度

   顶点v_x到v_y之间有路径P(v_x, v_y)的充分必要条件为：存在顶点序列v_x, v_i1, v_i2, …, v_im, v_y，并且序列中相邻两个顶点构成的顶点偶对分别为图中的一条边。

   出发点与终止点相同的路径称为回路或环；顶点序列中顶点不重复出现的路径称为简单路径。不带权的图的路径长度是指路径上所经过的边的数目，带权图的路径长度是指路径上经过的边上的权值之和。

3. 子图

   对于图G=(V,E)与G'=(V',E'),若有V'⊆V, E'⊆E,则称G'为G的一个子图。

   

   如图，G₁'和G₂'是G的子树

4. 图的联通(Connected)

   1. 无向图(Digraph)的联通

      无向图中顶点v_i到v_j有路径,则称顶点v_i与v_j是连通的。若无向图中任意两个顶点都连通, 则称该无向图是连通的（称为连通图）。

      连通分量：无向图中的极大连通子图。

      

   2. 有向图(Directed Graph)的连通

      若有向图中顶点v_i到v_j有路径,并且顶点v_j到v_i也有路径，则称顶点v_i与v_j是连通的。若有向图中任意两个顶点都连通，则称该有向图是强连通的。

      强连通分量：有向图的极大强连通子图。

      

5. 生成树

   包含具有n个顶点的连通图G的全部n个顶点,仅包含其n-1条边的极小连通子图称为G的一个生成树。

   

   性质：

   1. 包含n个顶点的图：连通且仅有n-1条边

      <=>无回路且仅有n-1条边

      <=>无回路且连通

      <=>是一棵树

   2. n个顶点的图中只要少于n-1条边，就不连通

   3. 如果n个顶点的图中有多于n-1条边，图将有环（回路）

   4. 一般情况下，生成树不唯一

2 图的存储方法

2.0 图需要存储的信息

1. 所有顶点的数据信息
2. 顶点之间关系（边或弧）的信息
3. 权的信息（对于网络）

2.1 邻接矩阵存储方法

2.1.1 核心思想

采用两个数组存储一个图

1. 定义一个一维数组VERTEX[0...n-1]存放图中所有顶点的数据信息(若顶点信息为0,1,2,3,...,此数组可略)。（称为顶点数组）

2. 定义一个二维数组A[0...n-1, 0...n-1]存放图中所有顶点之间关系的信息（该数组成为邻接矩阵），有 \[ A[i][j]= \begin{cases} 1, & \text当顶点v_{i}到顶点v_{j}有边时\\ 0,& \text当顶点v_{i}到顶点v_j无边时 \end{cases} \] 对于带权的图，有 \[ A[i][j]= \begin{cases} W_{ij}, & \text当顶点v_{i}到顶点v_{j}有边时，且边的权为W_{ij}\\ ∞,& \text当顶点v_{i}到顶点v_j无边时 \end{cases} \]

2.1.2 特点

• 无向图的邻接矩阵一定是一个对称矩阵。
• 不带权的有向图的邻接矩阵一般是稀疏矩阵。
• 无向图的邻接矩阵的第i行(或第i列)非0或非∞元素的个数为第i个顶点的度数。
• 有向图的邻接矩阵的第i行非0或非∞元素的个数为第i个顶点的出度；第i列非0或非∞元素的个数为第i个顶点的入度。
• 空间复杂度：O(n²)

2.1.3 代码实现

#define MaxV <最大顶点个数>
typedef struct edge{		// 定义边类型
	int weight;
}Edge;
Vertype Vertex[MaxV];		// 顶点信息数组
Edge G[MaxV][MaxV];			// 邻接矩阵

2.2 邻接表存储方法

2.2.1 核心思想

建立n个线性链表存储该图

1. 每一个链表前面设置一个头结点,用来存放一个顶点的数据信息,称之为顶点结点。其构造为

   其中，vertex域存放某个顶点的数据信息；link域存放某个链表中第一个节点的地址。n个头结点构成一个数组。

2. 第i个链表中的每一个链结点（称之为边结点）表示以第i个顶点为出发点的一条边；边结点的构造为

   其中，next域为指针域；weight域为权值域（若图不带权，则无此域）；adjvex域存放以第i个顶点为出发点的一条边的另一端在头结点数组中的位置。

   

2.2.2 特点

• 无向图的第i个链表中边结点个数是第i个顶点度数。
• 有向图的第i个链表中边结点个数是第i个顶点的出度。
• 无向图的边结点个数一定为偶数；边结点个数为奇数的图一定是有向图。

2.2.3 代码实现

#define MaxV <最大顶点个数>
typedef struct edge{		// 定义边结点类型
    int adjvex;
    int weight;
    struct edge *next;
}ELink;
typedef struct ver{			// 定义顶点结点类型
    vertype vertex;
    ELink *link;
}VLink;
VLink G[MaxV];

2.2.4 逆邻接表

第i个链表中的每一个链结点（称之为边结点）表示以第i个顶点为终止点的一条边。

2.3 *（稀疏矩阵）三元组存储方法

1. 三元组(i, j, value)
2. 三元组表示适合存储稀疏矩阵（稀疏图），针对图来说，是一种按边存储的方式，又称为边集数组，特别适合于图的按边访问应用。当然，若按顶点来访问图将不是很方便。

#define MaxV <最大顶点个数>
#define MaxE <最大边数>
typedef struct edge{		// 定义边类型
    int v1, v2;
    int weight;
}Edge;
Vertype Vertex[MaxV];		// 顶点信息数组
Edge G[MaxE];			// 边集数组（三元组）

2.4 图的基本操作

createGraph();		// 创建一个图
destoryGraph();		// 删除一个图
insertVex(v);		// 在图中插入一个顶点v
deleteVex(v);		// 在图中删除一个顶点v
insertEdge(v,w);	// 在图中插入一条边<v,w>
deleteEdge(v,w);	// 在图中删除一条边<v,w>
traverseGraph();	// 遍历一个图

例：

若有如下输入： 8 0 2 4 … -1 1 3 6 8 … -1 …

第一行为图的顶点个数，从第二行开始第一个数为顶点序号，第二个数字开始为该顶点的邻接顶点，每行以-1结束，则创建一个邻接表存储的图算法如下：

#define MaxV 256
typedef struct edge{ 
    int adj;
    int wei;
	struct edge *next;
}Elink;
typedef struct ver{
	ELink *link;
}Vlink;
VLink G[MaxV];

void createGraph(VLink graph[]){
	int i, n, v1, v2;
	scanf("%d",&n);
    for(i=0; i<n; i++){
        scanf("%d %d", &v1, &v2);
        while(v2 != -1){
            graph[v1].link = insertEdge(graph[v1].link, v2);
            graph[v2].link = insertEdge(graph[v2].link, v1);
            scanf("%d", &v2);
        }
    }
} 
//在链表尾插入一个节点
Elink *insertEdge(ELink *head, int avex){
    ELink *e,*p;
    e = (ELink *) malloc (sizeof(ELink));
    e->adj = avex;
    e->wei = 1;
    e->next = NULL;
    if(head == NULL){
        head = e;
        return head;
    }
    for(p=head; p->next != NULL; p=p->next)
        ;
    p->next = e;  
    return head;
}

2.4 *有向图的十字链表存储方法

有向图的十字链表存储方法1-CSDN博客

有向图的十字链表存储方法2；深度优先、广度优先遍历-CSDN博客

2.5 *无向图的多重邻接表存储方法

无向图的多重邻接表存储方法1-CSDN博客

无向图的多重邻接表存储方法2-CSDN博客

3 图的遍历

从图中某个指定的顶点出发, 按照某一原则对图中所有顶点都访问一次, 得到一个由图中所有顶点组成的序列, 这一过程称为图的遍历。

3.1 深度优先遍历(Depth First Search, DFS)

1. 原则：从图中某个指定的顶点v出发，先访问顶点v，然后从顶点v未被访问过的一个邻接点出发，继续进行深度优先遍历，直到图中与v相通的所有顶点都被访问；若此时图中还有未被访问过的顶点，则从另一个未被访问过的顶点出发重复上述过程，直到遍历全图。
2. 算法：

int Visited[N] = {}; //标识顶点是否被访问过，N为顶点数
void travelDFS(VLink G[ ], int n){
	int i;
    for(i=0; i<n; i++)
        Visited[i] = 0 ;
    for(i=0; i<n; i++)
        if( !Visited[i] )
            DFS(G, i);
}
void DFS(VLink G[ ], int v){
    ELink *p;
    Visited[v] = 1; //标识某顶点被访问过
    VISIT(G, v); //访问某顶点
    for(p=G[v].link; p !=NULL;  p=p->next)
         if( !Visited[p->adjvex] )
             DFS(G, p->adjvex);
}

3. 算法分析：如果图中具有n个顶点、e条边，则
   • 若采用邻接表存储该图,由于邻接表中有2e个或e个边结点，因而扫描边结点的时间为O(e)；而所有顶点都递归访问一次，所以，算法的时间复杂度为O(n+e)。
   • 若采用邻接矩阵存储该图，则查找每一个顶点所依附的所有边的时间复杂度为O(n)，因而算法的时间复杂度为O(n^２)。

3.2 广度优先遍历(Breadth First Search, BFS)

1. 原则：从图中某个指定的顶点v出发，先访问顶点v，然后依次访问顶点v的各个未被访问过的邻接点，然后又从这些邻接点出发，按照同样的规则访问它们的那些未被访问过的邻接点，如此下去，直到图中与v相通的所有顶点都被访问（完成一个连通分量的遍历）; 若此时图中还有未被访问过的顶点, 则从另一个未被访问过的顶点出发重复上述过程，直到遍历全图（完成所有连通分量的遍历）。
2. 算法

int Visited[N] = {}; //标识顶点是否被访问守，N为顶点数
void travelBFS(VLink G[ ], int n){
	int i;
    for(i=0; i<n; i++)
        Visited[i] = 0 ;
    for(i=0; i<n; i++)
        if( !Visited[i] )
            BFS(G, i);
}
void BFS(VLink G[ ], int v){
    ELink *p;
    Visited[v] = 1; //标识某顶点已入队
    enQueue(Q, v);
    while( !emptyQ(Q) ){
         v = deQueue(Q);  //取出队头元素
         VISIT(G, v); //访问当前顶点
         for(p=G[v].link; p!=NULL; p=p->next ) //访问该顶点的每个邻接顶点
				if( !Visited[p->adjvex] ){
                    Visited[p->adjvex] = 1; //标识某顶点入队
                    enQueue(G, p->adjvex);
				}
     }
}

3. 算法分析：
   • 邻接表：O(n+e)
   • 邻接矩阵：O(n²)

3.3 DFS与BFS

对比这两个图的遍历算法，其实它们在时间复杂度上是一样的，不同之处仅仅在于对顶点的访问的顺序不同。具体用哪个取决于具体问题。通常DFS更适合目标比较明确，以找目标为主要目的的情况，而BFS更适合在不断扩大遍历范围时找到相对最优解的情况。

3.4 例：独立路径计算

1. 题目

   

2. 分析

   本问题的实质：给定起点，对图进行遍历，并在遍历图的过程中找到到达终点的所有情况。前面介绍的DFS和BFS算法都是从源点出发对邻接顶点的遍历。而问题是本文中两个点间可能有多个边（如图所示）。

   算法策略是对DFS算法（或BFS）进行改进，在原来按邻接顶点进行遍历，改为按邻接顶点的边进行遍历（即从一个顶点出发遍历其邻接顶点时，按邻接顶点的边进行深度遍历，即只有当某顶点的所有邻接顶点的所有边都遍历完才结束该结点的遍历）。

3. 代码实现

#define MAXSIZE 512
struct edge{	//边结点结构
	int eno;	//边序号
	int adjvex;	//邻接顶点
	int weight;	//边的权重（可为距离或时间），本文中为1
	struct edge *next;
 };
struct ver{		//顶点结构，邻接表下标即为顶点序号
	struct edge *link;
}; 
struct ver G[MAXSIZE];		//由邻接表构成的图
char Visted[MAXSIZE] = {};		//标识相应顶点是否被访问 
int paths[MAXSIZE]; 		//独立路径

4 最小生成树

4.1 什么是最小生成树

1. 最小生成树：包含着连通图的全部n个顶点，仅包含其n-1条边的极小连通子图。
2. 生成树性质：
   1. 包含n个顶点的图：连通且有n-1条边 <=>无回路且有n-1条边 <=>无回路且连通 <=>是一棵树
   2. 如果n个顶点的图中只有少于n-1条边，图将不连通
   3. 如果n个顶点的图中有多于n-1条边，图将有环（回路）
   4. 一般情况下，生成树不唯一
3. 带权连通图中，总的权值之和最小的带权生成树为最小生成树。最小生成树也称最小代价生成树,或最小花费生成树。
4. 构造最小生成树的基本原则
   1. 只能利用图中的边来构造最小生成树；
   2. 只能使用、且仅能使用图中的n-1条边来连接图中的n个顶点；
   3. 不能使用图中产生回路的边。

4.2 求最小生成树

4.2.1 普利姆(Prim)算法

1. 基本思想：设G=(V, GE)为具有n个顶点的带权连通图；T=(U, TE)为生成的最小生成树，初始时，TE=空，U={v}，v∈V。

   依次在G中选择一条一个顶点仅在V中，另一个顶点在U中，并且权值最小的边加入集合TE，同时将该边仅在V中的那个顶点加入集合U。重复上述过程n–1次，使得U=V，此时T为G的最小生成树。

2. Prim算法数据结构说明

int weights[MAXVER][MAXVER];
// 当图G中存在边(i,j)，则weights[i][j]为其权值，否则为一个INFINITY
int edges[MAXVER];
// 存入生成的最小生成树的边，如 ：(i, edges[i]) 为最小生成树的一条边，应有n-1条边
int minweight[MAXVER];
// 存放未确定为生成树的顶点至已确定的生成树上顶点的边权重，
// minweight[i]表示顶点i至生成树上顶点的边权重， minweight[i] = 0 表示顶点i已确定为最小生成树顶点

3. 代码实现

#define MAXVER 512
#define INFINITY 32767
void Prim(int weights[][MAXVER], int n, int src, int edges[ ]){
    //weights为权重数组、n为顶点个数、src为最小树的第一个顶点、edge为最小生成树边
    int minweight[MAXVER], min;
    int i, j, k;
    for(i=0; i<n; i++){		//初始化相关数组
    	minweight[i] = weights[src][i];		//将src顶点与之有边的权值存入数组
        edges[i] = src;		//初始时所有顶点的前序顶点设为src，(src,i）
    }
    minweight[src] = 0;		//将第一个顶点src顶点加入生成树
    for(i=1; i< n; i++){
    	min = INFINITY;
        for(j=0, k=0; j<n; j++)
        	if(minweight[j] !=0 && minweight[j]<min){	//在数组中找最小值，其下标为k
            	min = minweigth[j];
				k = j;
            }
        minweight[k] = 0;  //找到最小树的一个顶点
        for(j=0; j<n; j++) 
        	if(minweight[j]!=0 && weights[k][j]<minweight[j]){
				minweight[j] = weights[k][j];	//将小于当前权值的边(k,j)权值加入数组中
				edges[j] = k;	//将边(j,k)信息存入边数组中
			}
	}
}

4.2.2 克鲁斯卡尔(Kruskal)方法

1. 基本思想：设G=(V, GE)为具有n个顶点的带权连通图；T=(U, TE)为生成的最小生成树。初始时，TE=空，U={v}，v∈V。

   从G中选择一条当前未选择过的、且边上的权值最小的边加入TE，若加入TE后使得T未产生回路,则本次选择有效，如使得T产生回路，则本次选择无效，放弃本次选择的边。重复上述选择过程直到TE中包含了G的n-1条边，此时的T为G的最小生成树。

2. *算法：

// 参考：https://onlyar.site/2022/01/24/Cpp-template/#kruskal-%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91
#include <stdio.h>
#include <stdlib.h>

#define V_MAX 300005
#define E_MAX 500005

typedef long long ll;

struct Edge {
    int x, y, w;
} e[E_MAX];

int v[V_MAX];		// 并查集(查源数组)    v[x]表示x的无数个前驱中的某一个

int cmp(const void *p1, const void *p2);
int Find(int x);
int isUnion(int x, int y);
void Union(int x, int y);	//合并
void makeSet(int n);		//初始化并查集(查源数组)

int main() {
    int n, m;		// n个结点，m条边
    scanf("%d%d", &n, &m);
    makeSet(n);
    for (int i=0; i<m; i++)
        scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].w);
    qsort(e, n, sizeof(struct Edge), cmp);	// 按照w从小到大排序
    int cnt = 0;
    ll sum = 0;
    for(int i=0; cnt<n-1; i++){
        if(isUnion(e[i].x, e[i].y))		// 形成回路了，看下一条边
            continue;
        cnt++;
        sum += e[i].w;
        Union(e[i].x, e[i].y);		// y的源头=x的源头
    }
    printf("%lld", sum);      // 输出最小生成树的权值
    return 0;
}

int cmp(const void *p1, const void *p2){
    struct Edge *d1 = (struct Edge *)p1;
    struct Edge *d2 = (struct Edge *)p2;
    if(d1->w < d2->w){
        return -1;
    }else{
        return 1;
    }
}

void makeSet(int n) {
    for (int i=1; i<=n; i++)
        v[i] = i;
}

int Find(int x) {
    if (v[x]==x)		// 如果v[x] == x，则x本身就是“源头”
        return x;
    return v[x] = Find(v[x]);	// 否则x的源头就是x的前驱(v[x])的源头
}

int isUnion(int x, int y) {
    if(Find(x) == Find(y)){		// 二者源头相同，相当于x和y在同一条线上，如果连上xy则会形成回路
        return 1;
    }else{
        return 0;
    }
}
void Union(int x, int y) { v[Find(y)] = Find(x); }

4.3 例

4.3.1 判断题们

1. 任意连通图中，假设没有相同权值的边存在，则权值最小的边一定是其最小生成树中的边。 (√)
2. 任意连通图中，假设没有相同权值的边存在，则权值最大的边一定不是其最小生成树中的边。 (╳)
3. 任意连通图中，假设没有相同权值的边存在，则与同一顶点相连的权值最小的边一定是其最小生成树中的边。 (√)
4. 采用克鲁斯卡尔算法求最小生成树的过程中，判断一条待加入的边是否形成回路，只需要判断该边的两个顶点是否都已经加入到集合U中。 (╳)

4.3.2 问题：北航网络中心铺设光缆

设计考虑：

1. 可用邻接矩阵存储网络图数据结构：

struct edge{
	int id;
	int wei;
};
struct edge graph[MAXVER][MAXVER];	//邻接矩阵
int edges[MAXVER]={0};		//生成树数组
// 根据输入值对<id,v1,v2,wei>构造图：
graph[v1][v2].id = id;
graph[v1][v2].weight = wei;
graph[v2][v1].id = id;
graph[v2][v1].weight = wei;

2. 调用Prim算法得到最小生成树，存放在edges数组中
3. 根据生成树数组edges可得到生成树边序号为graph\[i][edges[i]].id的边，其权重为：graph\[i][edges[i]].wei
4. 最小生成树按边序号进行排序输出.

5 最短路径问题(Dijkstra算法)——单原点问题

5.1 路径长度的定义

1. 不带权的图：路径上所经过的边的数目
2. 带权的图：路径上经过的边上的权值之和

5.2 问题的提出

设出发顶点为v(通常称为源点)。

求：单源点最短路径；每对顶点之间的最短路径；求图中第1短、第2短、...的最短路径

5.3 解决问题所需要确定的数据结构

1. 图的存储

   以0~n-1分别代表n个顶点,采用邻接矩阵存储该图,有 \[ A[i][j] = \begin{cases} W_{ij}, & \text当顶点v_{i}到顶点v_{j}有边时，且边的权为W_{ij}\\ ∞,& \text当顶点v_{i}到顶点v_j无边时\\ 0, & \text当v_i=v_j时 \end{cases} \]

5.4 Dijkstra算法

（本质上也是一种贪婪算法(greedy algorithm)）

设v0为源顶点，Weights为顶点间权重数组（邻接矩阵），Sweight为v0到相应顶点最小权重数组，Spath为最短路径数组，wfound表示某顶点是否已确定最短路径(0未确定，1已确定)，有如下定义：

int Weigths[VNUM][VNUM], Spath[VNUM]={0};
int Sweight[VNUM], wfound[VNUM]; 

1. 初始化数组Sweight,使得Sweight[i] = Weigths[v0][i]。

2. 初始化Sweight[v0]=0, Spath[i]=v0, wfound[v0] = 1。

3. 查找与v0间权重最小且没有确定最短路径的顶点v，即在Sweight数组中查找权重最小且没有确定最短路径的顶点。

4. 标记v为已找到最短路径的顶点。

5. 对于图G中每个从顶点v0到其最短路径还未找到，且存在边(v,w)，如果从v0通过v到w的路径权值小于它当前的权值，则更新w的权值为：v的权值+边(v,w)的权值，即：Sweight[w] = Sweight[v]+Weights[v][w]。

6. 重复上述过程的第3至第5步n–1次。

注：最短路径数组Spath含义为Spath[v]表示顶点v在最短路径上的直接前驱顶点。假设某最短路径由顶点v0,v1,v2,v3组成，则有：v2=Spath[v3], v1=Spath[v2], v0=Spath[v1]。

Dijkstra(int v0){
	int i, j, v, minweight;
    char wfound[VNUM] = {};		// 用于标记从v0到相应顶点是否找到最短路径，0未找到，1找到
    for(i=0; i<VNUM; i++){
        Sweight[i] = Weights[v0][i];
        Spath[i] = v0;
    }		// 初始化数组Sweight和Spath
    Sweight[v0] = 0;
    wfound[v0] = 1;
	for(i=0; i< VNUM-1; i++){		// 迭代VNUM-1次
		minweight = INFINITY;
		for(j=0; j<VNUM; j++)		// 找到未标记的最小权重值顶点 
			if( !wfound[j] && ( Sweight[j]<minweight) ){
				v = j; 
				minweight = Sweight[v];
			}
		wfound[v] = 1;		// 标记该顶点为已找到最短路径
		for(j =0; j < VNUM; j++)		// 找到未标记顶点且其权值大于v的权值+(v,j)的权值，更新其权值
			if( !wfound[j]  &&  (minweight + Weights[v][j] < Sweight[j] )) {
				Sweight[j] = minweight + Weights[v][j];
				Spath[j] = v;		// 记录前驱顶点
			}
	}
}

问：对于给定的带权连通无向图，从某源点到图中各顶点的最短路径构成的生成树是否是该图的最小生成树？

答：Dijkstra最短路径算法构造的生成树不一定为最小生成树

*Dijkstra算法的局限性：无法正确处理含负权边的图。（ppt没看懂，待更新）

5.5 北京地铁乘坐线路查询

5.5.1 题目

文件bgstations.txt为数据文件，包含了北京地铁的所有线路及所有车站信息。其格式如下： 12 1 23 苹果园 0 古城 0 … 公主坟 1 … 四惠东 1 2 19 西直门 1 积水潭 0 … 西直门 说明：表明目前北京地铁共开通12条线，其中1号线有23个车站，分别为苹果园，非换乘站；…；公主坟，换乘站…。2线共有19个站，分别为西直门，换乘站，…。

输入： 起始站：西土城 目的站：北京西站

输出： 西土城-10(1)-知春路-13(2)-西直门-4(2)-国家图书馆-9(4)-北京西站

5.5.2 方案一

1. 算法
   1. 初始化地铁线路图(initMap()函数)
      1. 将站信息加入到站信息数组中（注意：站名是唯一的，每个站在该数组中的下标即为图的顶点编号）（即图的顶点数组）
      2. 将每条线路的当前站和其前序站构成的边(v1,v2)加入到图顶点权重数组中（注：在权重数组中权重信息包括两站间的站数（缺省为1）以及所属线路）
   2. 分别读入起始站和目的站
   3. 按照Dijkstra算法在图中查找最短路径(Dijkstra()函数)
   4. 依据最短路径按按照格式要求输出换乘路径(printPath()函数)
2. 代码实现

#define MAXNUM 512		//地铁最大站数
#define MAXLEN 16		//地铁站名的最大长度
#define INFINITY 32767

struct station{ //车站信息
	char sname[MAXLEN];		//车站名
    int ischange;		//是否为换乘站，0-否，1-换乘
};
struct weight{
    int wei;	//两个站间的权重，即相差站数，缺省为1
    int lno;	//两个顶点所在的线号
};
struct station BGvertex[MAXNUM];		//地铁网络图顶点数组
struct weight BGweights[MAXNUM][MAXNUM];	//网络图权重数组，邻接矩阵
int Vnum = 0;	//实际地铁总站数
void initMap(){
    FILE *fp;
    int i, j, snum, lno, lnum, v1, v2;
    struct station st;
    …
    fscanf(fp, "%d", &snum);
    for(i=0; i<snum; i++){
        fscanf(fp, "%d %d", &lno, &lnum);
        v1 = v2 = -1;
        for(j=0; j<lnum; j++){
        fscanf(fp, "%s %d", st.sname, &st.ischange);
        v2 = addVertex(st); //将该站加到站信息数组中，返回其下标
        if(v1 != -1){
            BGweights[v1][v2].wei = BGweights[v2][v1].wei = 1;
            BGweights[v1][v2].lno = BGweights[v2][v1].lno = lno;
        }
        v1 = v2;
        }
    }
    fclose(fp);
    return;
}

5.5.3 方案二

算法

1. 构造一个北京地铁换乘网络图（只由换乘节点组成）
2. 根据用户输入的源和目的车站，将两个顶点加到网络图中
3. 按最短路径算法在图中查找由源到目的车站的最短路径。

5.6 *Dijkstra算法（单源点问题）与Floyd算法（多源点问题）

Dijkstra算法和Floyd算法时间复杂度都为O(n³)，但Floyd更简洁

链接阅读：

1. Floyd算法-c实现-CSDN博客
2. Floyd算法-C C++ matlab 实现-CSDN博客
3. Floyd算法-反正不是c实现-CSDN博客
4. Floyed算法及证明-c++实现-知乎 (zhihu.com)
5. Floyd算法-java实现-知乎 (zhihu.com)
6. 数据结构1800题型-Floyd算法求最短路径_哔哩哔哩_bilibili

6 *AOV网与拓扑排序

6.1 AOV网

以顶点表示活动，以有向边表示活动之间的优先关系的有向图称为顶点表示活动的网(Activity On Vertex Network),简称AOV网。

在AOV网中，若顶点i到顶点j之间有路径,则称顶点i为顶点j的前驱，顶点j为顶点i的后继；若顶点i到顶点j之间为一条有向边，则称顶点i为顶点j的直接前驱，顶点j为顶点i的直接后继。

AOV网通常用于描述工程的进行顺序（如下图）。我们可以通过对AOV网进行操作来判断工程能否正常进行。

检测工程能否正常进行，首先要判断对应的AOV网中是否存在回路，达到该目的最有效的方法之一是对AOV网构造其顶点的拓扑序列，即对AOV网进行拓扑排序（由某个集合上的一个偏序得到该集合上的一个全序的操作称为拓扑排序）。

设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列v1,v2,…,vn，满足若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在顶点vj之前，则称这样的顶点序列为一个拓扑序列。构造拓扑序列的过程就是拓扑排序。

6.2 拓扑排序

构造AOV网的一个顶点序列，使得该顶点序列满足下列条件：

1. 若在AOV网中,顶点i优先于顶点j，则在该序列中顶点i仍然优先于顶点j；
2. 若在AOV网中，顶点i与顶点j之间不存在优先关系,则在该序列中建立它们的优先关系,即顶点i优先于顶点j，或者顶点j优先于顶点i；
3. 若能构造出这样的拓扑序列，则拓扑序列包含AOV网的全部顶点，说明AOV网中没有回路；反之，若构造不出这样的序列，说明AOV网中存在回路。

6.3 拓扑排序方法

1. 从AOV网中任意选择一个没有前驱的顶点；
2. 从AOV网中去掉该顶点以及以该顶点为出发点的所有边；
3. 重复上述过程，直到AOV网中的所有顶点都被去掉（说明AOV网中无回路），或者AOV网中还有顶点，但不存在入度为0的顶点（说明AOV网中有回路）。

6.4 自然语言描述的拓扑排序算法

1. 首先建立一个入度为0的顶点栈，将网中所有入度为0的顶点分别进栈。
2. 当堆栈不空时，反复执行以下动作：
   1. 从顶点栈中退出一个顶点，并输出它；
   2. 从AOV网中删去该顶点以及以它发出的所有边，并分别将这些边的终点的入度减1；
   3. 若此时边的终点的入度为0，则将该终点进栈；
3. 若输出的顶点个数少于AOV网中的顶点个数，则报告网中存在回路，否则，说明该网中不存 在回路。

6.5 拓扑排序算法的c实现

C语言实现拓扑排序与关键路径_c语言 拓扑排序-CSDN博客

7 *AOE网与关键路径

7.1 AOE网

与AOV网相比，AOE网更关心每个活动持续多少时间/完成整个工程至少需要多少时间/哪些活动是关键活动。

AOE(Activity On Edge)网为一个带权的有向无环图，其中，以顶点表示事件，有向边表示活动，边上的权值表示活动持续的时间。正常情况下，AOE网中只有一个入度为0的顶点，称之为源点；有一个出度为0的顶点，称之为终点。

AOE网的特点：

1. 只有在某个顶点所代表的事件发生以后,该顶点引发的活动才能开始。
2. 进入某事件的所有边代表的活动都已完成,该顶点代表的事件才能发生。

7.2 AOE网的存储方法

采用邻接矩阵存储方法

7.3 关键路径

1. 定义：从源点到终点的路径中具有最大长度的路径为关键路径；关键路径上的活动称为关键活动。
2. 特点：
   1. 关键路径的长度(路径上的边的权值之和)为完成整个工程所需要的最短时间。
   2. 关键路径的长度变化(即任意关键活动的权值变化)将影响整个工程的进度，而其他非关键活动在一定范围内的变化不会影响工期。

7.4 求关键路径

思路： e[i] — 活动a_i的最早开始时间； l[i] — 活动a_i的最晚开始时间； 若l[i]–e[i]=0，则说明活动a_i为一个关键活动。 ee[k] — 事件k的最早发生时间； le[k] — 事件k的最晚发生时间； 通过ee[k]和le[k]求出e[i]和l[i]，若e[i] = l[i]则活动a_i为一个关键活动

1. 计算时间k的最早发生时间ee[k]

   事件k的最早发生时间决定了由事件k出发的所有活动的最早开始时间；该时间是指从源点到顶点(事件)k的最大路径长度。

   计算方法： \[ ee[0] = 0\\ ee[k] = \max_{<j, k>∈P(k)}ee[j]+<j, k>的权 \] 例：

2. 计算事件k的最晚发生时间le[k]

   所谓事件k的最晚发生时间是指不影响整个工期的前提下事件k必须发生的最晚时间，它必须保证从事件k发出的所有活动的终点事件（k的后继事件）的最迟发生时间。

   计算方法： \[ le[n-1] = n-1\\ le[k] = \min_{<k, j>∈S(k)}le[j]-<k, j>的权 \]

3. 计算活动i的最早开始时间e[i]

   所谓活动i的最早开始时间实际上是事件k发生的最早时间，即只有事件k发生，活动i才能开始。

   计算方法： \[ e[i] = ee[k] \]

4. 计算活动i的最晚开始时间l[i]

   所谓活动i的最晚开始时间是指不推迟整个工期的前提下活动i开始的最晚时间。

   计算方法： \[ l[i] = le[j]-<k, j>的权 \]

5. 求出关键活动与关键路径

   计算方法： \[ l[i] = e[i] \]

7.5 关键路径计算的c实现

【C语言】关键路径（求解过程及算法实现）_已知关键事件求关键路径-CSDN博客

【C语言】关键路径/最长路径模拟实现_关键路径和最长路径区别-CSDN博客

8 *网络流量问题

8.1 相关概念

设给定边容量为c_v,w的有向图G=(V,E)（容量可以表示通过一个管道的水、电、交通、网络等最大流量）。有两个顶点，一个是s称为源点(source)，一个是t称为汇点(sink)。对于任一条边(v,w)，最多有“流”的c_v,w个单位（容量）可以通过。在既不是源点s又不是汇点t的任一顶点v，总的进入流必须等于总的发出的流。每条边上的流满足下面两个条件：

• 通过边的流不能大于边的容量（容量约束）
• 到达顶点v的流的总和与从v流出的总和相同，其中v不是源点或汇点（流守恒）

最大流问题：确定从s到t可以通过的最大流量。

8.2 最大流算法原理

算法设有3个图（原图G、流图Gf、残余图Gr），在其上分阶段进行。Gf表示在算法的任意阶段已经达到的流，算法终止时其包含最大流；Gr称为残余图（residual graph），它表示每条边还能再添加上多少流（即还残余多少流），对于Gr中每条边（称为残余边，residual edge）可以从其容量中减去当前流来计算其残余流。

1. 初始时Gf所有边都没有流（流为0），Gr与G相同；
2. 每个阶段，先从Gr中找一条从s到t的路径（称为增长路径augmenting path）；
   1. 将该路径上最小边的流量作为整个路径的流（权），并将路径加至流图Gf中；
   2. 将该权值路径从Gr中减去，若某条边权值为0，则从Gr中除去；
   3. 将具有该权的反向路径加到Gr中；
   4. 重新执行步骤2，直到Gr中无从s到t的路径；
3. 将Gf中顶点t的每条入边流值相加得到最大流。