866数据结构笔记 - 第六章图

无向图和有向图边和结点关系？
连通图和强连通图是什么意思？
无向完全图和有向完全图边数
邻接矩阵、邻接表与图之间转换
BFS、DFS序列和生成树
BFS和DFS代码（王道+866）
最小生成树构造两种方法（Prim、Kruskal）
Dijkstra计算最短路径
Flyod代码（866）
拓扑排序序列（必考）
关键路径计算

一、基本概念

图：G=（V,E），顶点集V（图的阶），边集E
线性表可以是空表，树可以是空树，图不能是空图，V一定非空，E可以为空。
无向图：若 E 是无向边（也称边）的有限集合时，则图 G 为无向图。边是顶点的无序对，记为 (v,w) 或(w,v)，其中 v、w 是顶点。
有向图：若 E 是有向边（也称弧）的有限集合时，则图 G 为有向图。弧是顶点的有序对，记为 <v,w>，其中 v、w 是顶点，v 称为弧尾，w 称为弧头，称为从顶点 v 到顶点 w 的弧。
简单图：① 不存在重复边； ② 不存在顶点到自身的边
多重图：图 G 某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联，则 G 为多重图。
度、出度、入度：对于无向图，顶点 v 的度是指依附于该顶点的边的条数，记为 TD(v)。对于有向图，入度是以顶点 v 为终点的有向边的数目，记为ID(v)；出度是以顶点 v 为起点的有向边的数目，记为 OD(v)。
无向图的全部顶点度的和等于边数的两倍。
有向图的全部顶点的入度之和等于出度之和，等于边数。
路径：顶点 $V_p$ 到顶点 $V_q$ 之间的一条路径是指顶点序列 $V_p$ , $V_{i1}$ , $V_{i2}$ ,……., $V_q$
回路：第一个顶点和最后一个顶点相同的路径称为回路或环。
简单路径：在路径序列中，顶点不重复出现的路径称为简单路径。
简单回路：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
路径长度：路径上边的数目。
点到点的距离：从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。若从u到v根本不存在路径，则记该距离为无穷(o) 。
连通、强连通：无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的。有向图中，若从顶点v到顶点w和从顶点 w到页点v之间都有路径，则称这两个顶点是强连通的。
连通图：若图G中任意两个顶点都是连通的，则称图G为连通图，否则称为非连通图。
子图、生成子图：设有两个图G=(V,E)和G'=(V',E')，若V'是V的子集,且E是E的子集，则称G'是G的子图。若有满足V(G') =V(G)的子图G'，则称其为G的生成子图。
连通分量：无向图中的极大连通子图称为连通分量。
强连通分量：有向图中的极大强连通子图称为有向图的强连通分量。
生成树：连通图的生成树是包含图中全部顶点的一个极小连通子图。
生成森林：在非连通图中，连通分量的生成树构成了非连通图的生成森林。
边的权：在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。带权图:边上带有权值的图称为带权图，也称网。
带权路径长度：当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度。
无向完全图：无向图中任意两个顶点之间都存在边。若无向图的顶点数|V|=n，则边为[0., n(n-1)/2]。
有向完全图：有向图中任意两个顶点之间都存在方向相反的两条弧。若有向图的顶点数|V|=n，则边为[0, n(n-1)]。
稀疏图、稠密图：边数很少的图称为稀疏图，反之称为稠密图。
有向图和无向图性质：
对于n个顶点无向图G
所有顶点的度之和为2|E|
如果G是连通图，则最少有n-1条边（树）。若|E|>n-1，则一定有回路
若G是非连通图，则最多有(n-1)(n-2)/2
无向完全图共有n(n-1)/2条边
对于n个顶点有向图G
所有顶点的出度之和=所有顶点的入度之和为=|E|
所有顶点的度之和为2|E|
如果G是强连通图，则最少有n条边（形成回路）
有向完全图共有n(n-1)条边

二、图的存储结构

1.邻接矩阵（顺序存储）

定义：

#define MaxVertexNum 100	//顶点数目的最大值

typedef struct{
    char Vex[MaxVertexNum];		//顶点表
    int Edge[MaxVertexNum][MaxVertexNum];	//邻接矩阵，边表
    int vexnum,arcnum;			//图的顶点数和边数
}MGraph;

度：第 i 个结点的度 = 第 i 行（或第 i 列）的非零元素个数
出度：第 i 行的非零元素个数
入度：第 i 列的非零元素个数
求结点度、入度、出度时间复杂度为O(|V|)
空间复杂度： O(|V|^2 ) ，只和顶点数相关，和实际的边数无关。
适合用于存储稠密图。
无向图的邻接矩阵是对称矩阵，可以压缩存储（只存储上三角区或者下三角区）。
设图G的邻接矩阵为A(矩阵元素为0或1)，则 $A^n$ 的元素 $A^n[i][j]$ 等于由顶点i到点j的长度为n的路径的数目。

带权图（网）：

#define MaxVertexNum 100		//顶点数目的最大值
#define INFINITY 2147483647;	//表示“无穷”

typedef char VertexType;	//顶点数据类型
typedef int EdgeType;		//边数据类型

typedef struct{
    VertexType Vex[MaxVertexNum];	//顶点表
    EdgeType Edge[MaxVertexNum][MaxVertexNum];	//边的权值
    int vexnum,arcnum;		//图的当前顶点数和弧数
}MGraph;

2.邻接表（顺序存储+链式存储）

定义：

#define MVNum 100							//最大顶点数

typedef struct ArcNode{                		//边/弧 
    int adjvex;                             //邻接点的位置 
    struct ArcNode *next;	      			//指向下一个表结点的指针 
}ArcNode;

typedef struct VNode{ 
    char data;                    	        //顶点信息 
    ArcNode *first;         				//第一条边/弧 
}VNode, AdjList[MVNum];                 	//AdjList表示邻接表类型 

typedef struct{ 
    AdjList vertices;              			//头结点数组
    int vexnum, arcnum;     				//当前的顶点数和边数 
}ALGraph;

三、图的基本操作

1. 王道定义：

2. 湖大本科定义：(常用n()、first()、next()、weight()、getmark()、setmark() )

四、图的遍历

1. 广度优先遍历（BFS）

算法实现：

找到与⼀个顶点相邻的所有顶点
防止重复访问
处理非连通图
需要⼀个辅助队列

王道代码：

bool visited[MAX_VERTEX_NUM];	//访问标记数组

// 对图G进行广度优先遍历
void BFSTraverse(Graph G){
    for(i=0; i<G.vexnum; ++i)	//访问标记数组初始化
        visited[i]=FALSE;
    InitQueue(Q);				//初始化辅助队列
    for(i=0; i<G.vexnum; ++i)	//从0号结点开始遍历，对每个连通分量进行一次广度优先遍历
        if(!visited[i])
            BFS(G,i);
}

//从顶点v开始广度优先遍历图G
void BFS(Graph G,int v){
    visit(G,v);					//访问图G的结点v
    visited[v]=TREE;			//标记v已被访问
    EnQueue(Q,v);				//顶点v入队列Q
    while(!isEmpty(Q)){
        DeQueue(Q,v);			//队列头节点出队并将头结点的值赋给v
        for(w=FirstNeighbor(G,v); w>=0; w=NextNeighbor(G,v,w)){
            //检测v的所有邻结点
            if(!visited[w]){
                visit(w);
                visited[w]=TREE;
                EnQueue(Q,w);
            }
        }
    }
}

湖大本科代码（建议使用，以前考过根据图的ADT写代码）：其实和王道代码差不多，只是把操作函数名字换了一下。没有使用visit数组存储标记，使用setMark函数设置标记，用getMark函数获取标记。获取下一个邻点的代码换成了这个for (int w=G->first(v); w<G->n();w = G->next(v,w))。

效率分析：

2. 深度优先遍历（DFS）

王道代码：

bool visited[MAX_VERTEX_NUM];	//访问标记数组

// 对图G进行深度优先算法
void DFSTraverse(Graph G){
    for(v=0; v<G.vexnum; v++){	//初始化标记数组
        visited[v]=FALSE;
    }
    for(v=0; v<G.vexnum; v++){
        if(!visited[v])
            DFS(G,v);
    }
}

// 从顶点v出发深度优先遍历图G
void DFS(Graph G,int v){
    visit(G,v);
    visited[v]=TREE;
    for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v)){
        if(!visited[w])
            DFS(G,v);
    }
}

湖大本科代码（建议使用）：

效率分析：

3. 图的遍历及连通性

同⼀个图的邻接矩阵表示⽅式唯⼀，因此深度优先遍历序列唯⼀，深度优先⽣成树也唯⼀
同⼀个图的邻接表表示⽅式不唯⼀，因此深度优先遍历序列不唯⼀，深度优先⽣成树也不唯⼀
对⽆向图进⾏ BFS/DFS 遍历，调⽤ BFS/DFS函数的次数=连通分量数。对于连通图，只需调⽤ 1 次 BFS/DFS函数
对有向图进⾏ BFS/DFS 遍历，调⽤ BFS/DFS函数的次数要具体问题具体分析。若起始顶点到其他各顶点都有路径，则只需调⽤ 1 次 BFS/DFS函数。对于强连通图，从任⼀结点出发都只需调⽤ 1 次 BFS/DFS函数

五、最小生成树

生成树：连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为 n，则它的生成树含有 n-1 条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。
最⼩⽣成树（最⼩代价树）：对于⼀个带权连通⽆向图G=(V,E)，⽣成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同。设 R 为 G 的所有⽣成树的集合，若 T 为 R 中边的权值之和最⼩的⽣成树，则 T 称为 G 的最小⽣成树（MST）。
最小⽣成树可能有多个，但边的权值之和总是唯⼀且最⼩的。、
最小⽣成树的边数 = 顶点数 - 1。砍掉⼀条则不连通，增加⼀条边则会出现回路。
如果⼀个连通图本身就是⼀棵树，则其最小生成树就是它本身。
只有连通图才有⽣成树，⾮连通图只有生成森林。
Prim 算法（普⾥姆）：从某⼀个顶点开始构建⽣成树，每次将代价最⼩的新顶点纳⼊⽣成树，直到所有顶点都纳⼊为⽌。适合边稠密图。
Kruskal 算法（克鲁斯卡尔）：每次选择⼀条权值最⼩的边，使这条边的两头连通（原本已经连通的就不选），直到所有结点都连通。适合边稀疏图。

六、最短路径

1. BFS求解无权图单源最短路径

使用 BFS算法求无权图的最短路径问题，需要使用三个数组：

d[]数组用于记录顶点 u 到其他顶点的最短路径。
path[]数组用于记录最短路径从那个顶点过来。
visited[]数组用于记录是否被访问过。

#define MAX_LENGTH 2147483647			//地图中最大距离，表示正无穷

// 求顶点u到其他顶点的最短路径
void BFS_MIN_Disrance(Graph G,int u){
    for(i=0; i<G.vexnum; i++){
        visited[i]=FALSE;				//初始化访问标记数组
        d[i]=MAX_LENGTH;				//初始化路径长度
        path[i]=-1;						//初始化最短路径记录
    }
    InitQueue(Q);						//初始化辅助队列
    d[u]=0;
    visites[u]=TREE;
    EnQueue(Q,u);
    while(!isEmpty[Q]){					//BFS算法主过程
        DeQueue(Q,u);					//队头元素出队并赋给u
        for(w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w)){
            if(!visited[w]){
                d[w]=d[u]+1;
                path[w]=u;
                visited[w]=TREE;
                EnQueue(Q,w);			//顶点w入队
            }
        }
    }
}

2. Dijkstra算法求解单源最短路径

使用 Dijkstra算法求最短路径问题，需要使用三个数组：
final[]数组用于标记各顶点是否已找到最短路径。
dist[]数组用于记录各顶点到源顶点的最短路径长度。
path[]数组用于记录各顶点现在最短路径上的前驱。

王道代码：

#define MAX_LENGTH = 2147483647;

// 求顶点u到其他顶点的最短路径
void BFS_MIN_Disrance(Graph G,int u){
    for(int i=0; i<G.vexnum; i++){		//初始化数组
        final[i]=FALSE;
        dist[i]=G.edge[u][i];
        if(G.edge[u][i]==MAX_LENGTH || G.edge[u][i] == 0)
            path[i]=-1;
        else
            path[i]=u;
        final[u]=TREE;
    }
 
  	for(int i=0; i<G.vexnum; i++){
        int MIN=MAX_LENGTH;
        int v;
		// 循环遍历所有结点，找到还没确定最短路径，且dist最⼩的顶点v
        for(int j=0; j<G.vexnum; j++){
	        if(final[j]!=TREE && dist[j]<MIN){
 	            MIN = dist[j];
                v = j;
            }
        }
        final[v]=TREE;
        // 检查所有邻接⾃v的顶点路径长度是否最短
        for(int j=0; j<G.vexnum; j++){
	        if(final[j]!=TREE && dist[j]>dist[v]+G.edge[v][j]){
            	dist[j] = dist[v]+G.edge[v][j];
                path[j] = v;
            }
        }
	}
}

湖大本科代码（20年代码题）：

3. Floyd算法求解各顶点间的最短路径

Floyd算法：求出每⼀对顶点之间的最短路径，使⽤动态规划思想，将问题的求解分为多个阶段。

Floyd算法使用到两个矩阵：

dist[][]：目前各顶点间的最短路径。
path[][]：两个顶点之间的中转点。

王道代码：

int dist[MaxVertexNum][MaxVertexNum];
int path[MaxVertexNum][MaxVertexNum];

void Floyd(MGraph G){
	int i,j,k;
    // 初始化部分
	for(i=0;i<G.vexnum;i++){
		for(j=0;j<G.vexnum;j++){
			dist[i][j]=G.Edge[i][j];		
			path[i][j]=-1;
		}
	}
    // 算法核心部分
	for(k=0;k<G.vexnum;k++){
		for(i=0;i<G.vexnum;i++){
			for(j=0;j<G.vexnum;j++){
	   	    	if(dist[i][j]>dist[i][k]+dist[k][j]){
	   		    	dist[i][j]=dist[i][k]+dist[k][j];
	   		    	path[i][j]=k;
                }
			}
        }
    }
}

湖大本科代码（21年和22年代码题）：

4. 比较

七、拓扑排序

拓扑排序：在图论中，由⼀个有向⽆环图的顶点组成的序列，当且仅当满⾜下列条件时，称为该图的⼀个拓扑排序：
每个顶点出现且只出现⼀次；
若顶点 A 在序列中排在顶点 B 的前⾯，则在图中不存在从顶点 B 到顶点 A 的路径。
或定义为：拓扑排序是对有向⽆环图的顶点的⼀种排序，它使得若存在⼀条从顶点 A 到顶点 B 的路径，则在排序中顶点 B 出现在顶点 A 的后⾯。每个 AOV 网都有⼀个或多个拓扑排序序列。
拓扑排序的实现：

从 AOV ⽹中选择⼀个没有前驱（⼊度为0）的顶点并输出。
从⽹中删除该顶点和所有以它为起点的有向边。
重复 ① 和 ② 直到当前的 AOV 网为空或当前⽹中不存在⽆前驱的顶点为⽌。

王道代码：

#define MaxVertexNum 100			//图中顶点数目最大值

typedef struct ArcNode{				//边表结点
    int adjvex;						//该弧所指向的顶点位置
    struct ArcNode *nextarc;		//指向下一条弧的指针
}ArcNode;

typedef struct VNode{				//顶点表结点
    VertexType data;				//顶点信息
    ArcNode *firstarc;				//指向第一条依附该顶点的弧的指针
}VNode,AdjList[MaxVertexNum];

typedef struct{
    AdjList vertices;				//邻接表
    int vexnum,arcnum;				//图的顶点数和弧数
}Graph;								//Graph是以邻接表存储的图类型

// 对图G进行拓扑排序
bool TopologicalSort(Graph G){
    InitStack(S);					//初始化栈，存储入度为0的顶点
    for(int i=0;i<g.vexnum;i++){
        if(indegree[i]==0)
            Push(S,i);				//将所有入度为0的顶点进栈
    }
    int count=0;					//计数，记录当前已经输出的顶点数
    while(!IsEmpty(S)){				//栈不空，则存入
        Pop(S,i);					//栈顶元素出栈
        print[count++]=i;			//输出顶点i
        for(p=G.vertices[i].firstarc;p;p=p=->nextarc){
            //将所有i指向的顶点的入度减1，并将入度为0的顶点压入栈
            v=p->adjvex;
            if(!(--indegree[v]))
                Push(S,v);			//入度为0，则入栈
        }
    }
    if(count<G.vexnum)
        return false;				//排序失败
    else
        return true;				//排序成功
}

湖大本科代码：

八、关键路径

1.AOE 网：在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间），称之为⽤边表示活动的⽹络，简称 AOE ⽹ (Activity On Edge NetWork)。
2.AOE网具有以下两个性质:
只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始
只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。另外，有些活动是可以并行进行的。
3.在AOE网中仅有一个入度为О的顶点，称为开始顶点（源点)，它表示整个工程的开始;也仅有一个出度为0的顶点，称为结束顶点(汇点)，它表示整个工程的结束。
4.从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动完成整个工程的最短时间就是关键路径的长度，若关键活动不能按时完成，则整个工程的完成时间就会延长。
5.术语:
事件vx的最早发生时间ve(k):决定了所有从vlk开始的活动能够开工的最早时间。
事件v:的最迟发生时间vl(k):它是指在不推迟整个工程完成的前提下，该事件最迟必须发生的时间。
活动a;的最早开始时间e(i):指该活动弧的起点所表示的事件的最早发生时间。
活动a;的最迟开始时间l(i):它是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差。
活动 a;的时间余量d(i)= l(i)- e(i)，表示在不增加完成整个工程所需总时间的情况下，活动a;可以拖延的时间若一个活动的时间余量为零，则说明该活动必须要如期完成,d(i)=0即l(i)= e(i)的活动a是关键活动，由关键活动组成的路径就是关键路径。
6.求关键路径的步骤:
求所有事件的最早发生时间ve():按拓扑排序序列，依次求各个顶点的ve(k)， ve(源点)=0， ve(k) = Max{ve(i)W eight(vj， Vk)}，vj为vk的任意前驱。
求所有事件的最迟发生时间vl():按逆拓扑排序序列，依次求各个顶点的vl(k)，vl(汇点)= ve(汇点)，vl(k)=Min{vl(j)-W eight(vk, vj)}，vj为vk的任意后继。
求所有活动的最早发生时间e():若边≤Vk,Vj >表示活动aj，则有e(i)= ve(k)。
求所有活动的最迟发生时间l():若边<Vk,Vj>表示活动aj，则有l(i)= vl(j) - Weight(vw, v).
求所有活动的时间余量d(): d(i)= l(i)- e(i)。
7.关健活动、关键路径的特性:
若关键活动耗时增加，则整个工程的工期将增长。
缩短关键活动的时间，可以宿短整个工程的工期。
当缩短到一定程度时，关键活动可能会变成非关键活动。
可能有多条关键路径，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。

九、代码题

给定n个村庄之间的交通图，现拟在n个村庄之间选择一个村庄建立小学，请设计一个算法求解该小学应该建立在哪个村庄才能使得距离最远的村庄到小学的路程最短。（21和22年考研原题，21年给了ADT，22年没给ADT）

（1）写出算法思想。

（2）写出算法伪代码，关键之处给出注释。

（3）给出算法时间度和空间复杂度分析。

DEFINE maxvalue 99999;
int distance(Graph *G){
    int D[G->n()][G->n()]; // 邻接矩阵
    for (int i = 0; i < G->n(); i++){
        for (int j = 0; j < G->n(); j++){
            D[i][j] = G->weight(i,j);
        }
    }
    
    // Flyod
    for (int k = 0; k < G->n(); k++){
        for (int i = 0; i < G->n(); i++){
            for (int j = 0; j < G->n(); j++){
                if (D[i][j] > D[i][k] + D[k][i]){
                    D[i][j] = D[i][k] + D[k][i];
                }
            }
        }
    }
    
    int min = maxvalue;
    for (int i = 0; i < G->n(); i++){
        int s = 0;
        // 顶点i到其他各个顶点最短路径中最长
        for (int j = 0; j < G->n(); j++){
            if (D[i][j] < maxvalue && D[i][j] > s){
                s = D[i][j];
            }
        // s中最小
        if (s < min){
            k = i;
            min = s;
        }
    }
    return k;
}