6.1 图的定义和基本术语

图：G=(V, E) Graph = (Vertex, Edge)

V：顶点(数据元素)的有穷非空集合

E：边的有穷集合

无向图：每条边都是无方向的

有向图：每条边都是有方向的 <>

完全图：任意两个点都有一条边相连

稀疏图：有很少边或弧的图（e<nlogn）

稠密图：有较多边或弧的图

网：边/弧带权的图

邻接：有边/弧相连的两个顶点之间的关系

存在（Vi，Vj），则称Vi和Vj互为邻接点
存在<Vi，Vj>，则称Vi邻接到Vj，Vj邻接于Vi

关联(依附)：边/弧与顶点之间的关系

存在(Vi，Vj)/<Vi，Vj>，则称该边/弧关于于Vi和Vj

顶点的度：与该顶点相关联的边的数目，记为TD(v)；

在有向图中，顶点的度等于该顶点的入度与出度之和

顶点v的入度是以v为终点的有向边的条数，记作ID(v)
顶点v的出度是以v为始点的有向边的条数，记作OD(v)

路径：接续的边构成的顶点序列

路径长度：路径上边或弧的数目/权值之和

回路(环)：第一个顶点和最后一个顶点相同的路径

简单路径：除路径起点和终点可以相同外，其余顶点均不相同的路径

简单回路(简单环)：除路径起点和终点相同外，其余顶点均不相同的路径

连通图(强连通图)：在无（有）向图G=（V，{E}），若对任何两个顶点v、u都存在从v到u的路径，则称G是连通图（强连通图）

权与网：图中边或弧所具有的相关数称为权。表明从一个顶点到另一个顶点的距离或耗费；带权的图称为网

子图

连通分量（强连通分量）

无向图G的极大连通子图称为G的连通分量
有向图G的极大连通子图称为G的强连通分量

极大连通子图的意思是：该子图是G连通子图，将G的任何不在该子图中的顶点加入，子图不再连通

极小连通子图：该子图是G的连通子图，在该子图中删除任何一条边，子图不再连通

生成树：包含无向图G所有顶点的极小连通子图

生成森林：对非连通图，由各个连通分量的生成树的集合

6.2 案例引入

六度空间理论（小世界理论）

把六度空间理论中的人际关系网络抽象成一个无向图G。用图G中的一个顶点表示一个人，两个人认识与否用代表这两个人的顶点之间是否有一条边来表示。从任一顶点出发用广度优先方法对图进行遍历，统计所有路径长度不超过7的顶点

6.3 图的类型定义

重要操作：

CreatGraph(&G, V, VR)

初始条件：V是图的顶点集，VR是图中弧的集合
操作结果：按V和VR的定义构造图G

DFSTraverse(G)

初始条件：图G存在
操作结果：对图进行深度优先遍历

BFSTraverse(G)

初始条件：图G存在
操作结果：对图进行广度优先遍历

6.4 图的存储结构

图的逻辑结构：多对多

图没有顺序存储结构，但可以借助二维数组来表示元素间的关系；这种表示法叫做：数组表示法（邻接矩阵）

链式存储结构：多重链表

邻接表
邻接多重表
十字链表

6.4.1 邻接矩阵

无向图

无向图的邻接矩阵是对称的
顶点 i 的度 = 第 i 行(列)中 1 的个数
特别地：完全图的邻接矩阵中，对角元素为0，其余为1

// 图的邻接矩阵存储表示
#define MAX_VERTEX_NUM 20	// 最大顶点数
#define maxInt 65535		// 无穷大
typedef char vertexType;	// 顶点类型
typedef int arcType;		// 边上的权值类型

typedef struct {
	vertexType vexs[MAX_VERTEX_NUM];	// 顶点集合
	arcType arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];	// 邻接矩阵
	int vexNum, arcNum;	// 图的当前顶点数和弧数
}adjacencyMatrix;

有向图

注：在有向图的邻接矩阵中，

第 i 行含义：以结点Vi为尾的弧（即出度边）
第 i 列含义：以结点Vi为头的弧（即入度边）

分析：

有向图的邻接矩阵可能是不对称的
顶点的出度 = 第 i 行元素之和
顶点的入度 = 第 i 列元素之和
顶点的度 = 第 i 行元素之和 + 第 i 列元素之和

网

即（有权图）的邻接矩阵表示

实现

算法思想：

输入总顶点数和总边数
依次输入点的信息存入顶点表中
初始化邻接矩阵，使每个权值初始化为极大值
构造邻接矩阵

/*******************************************************************************************************************************
 * @description：返回顶点u在图G中的位置
 * @param：G
 * @param：u
 * @return：
 */
int locateVex(adjacencyMatrixGraph* G, vertexType u)
{
	int i;
	for (i = 0; i < G->vexNum; i++) {
		if (G->vexs[i] == u) {
			return i;
		}
	}
	return -1;
}





/*******************************************************************************************************************************
 * @description：创建无向网
 * @param：G
 * @return：
 */
status createUDN(adjacencyMatrixGraph* G)
{
	vertexType v1, v2;
	int i, j, k, w;
	printf("请输入顶点数和边数：");
	scanf("%d,%d", &G->vexNum, &G->arcNum);
	printf("请输入顶点信息：");
	for (i = 0; i < G->vexNum; i++) {
		scanf("%c", &G->vexs[i]);
	}
	for (i = 0; i < G->vexNum; i++) {
		for (j = 0; j < G->vexNum; j++) {
			G->arcs[i][j] = maxInt;
		}
	}
	for (k = 0; k < G->arcNum; k++) {
		printf("请输入一条边所依附的顶点和权值w：");
		scanf("%c,%c,%d", &v1, &v2, &w);
		i = locateVex(G, v1);
		j = locateVex(G, v2);
		G->arcs[i][j] = w;
		G->arcs[j][i] = G->arcs[i][j];	// 无向图对称
	}
	return OK;
}

邻接矩阵的好处：

直观、简单、好理解
方便检查任意一对顶点间是否存在边
方便找任一顶点的所有“邻接点”（有边直接相连的顶点）
方便计算任以顶点的“度”（从该点发出的边数为“出度”，指向该点的边数为“入度”）

无向图：对应行（或列）非0元素的个数
有向图：对应行非0元素的个数是“出度”；对应列非0元素的个数是“入度”

坏处：

不便于增加和删除顶点
浪费空间：存稀疏图（点很多而边很少）有大量无效元素

对稠密图（特别是完全图）还是很合算的

浪费时间：统计稀疏图中一共有多少条边

6.4.2 邻接表

无向图

特点：

邻接表不唯一
若无向图中有 n 个顶点、 e 条边，则其邻接表需 n 个头结点和 2e 个表结点。适宜存储稀疏图;存储空间为：O(n+ 2e)

无向图中顶点vi的度为第 i 个单链表中的结点数

有向图

// 图的邻接表存储表示
typedef struct arcNode {
	int adjVex;	// 该弧所指向的顶点的位置
	struct arcNode* nextArc;	// 指向下一条弧的指针
	arcType info;	// 该弧的相关信息
}arcNode;


typedef struct {
	vertexType data;	// 顶点信息
	arcNode* firstArc;	// 指向第一条依附该顶点的弧的指针
}adjacencyListVertexNode;


typedef struct {
	adjacencyListVertexNode vertices[MAX_VERTEX_NUM];	// 顶点向量
	int vexNum, arcNum;	// 图的当前顶点数和弧数
}adjacencyList;

实现

算法思想：

输入总顶点数和总边数
建立顶点表

依次输入点的信息存入顶点表中
使每个表头结点的指针于初始化为NULL

创建邻接表

依次输入每条边依附的两个顶点
确定两个顶点的序号 i 和 j ，建立边结点
将此边结点分别插入到 vi 和 vj 对应的边链表的头部

/*******************************************************************************************************************************
 * @description：返回顶点u在图G中的位置
 * @param：G
 * @param：u
 * @return：
 */
int locateVex_ByAL(adjacencyListGraph* G, vertexType u)
{
	int i;
	for (i = 0; i < G->vexNum; i++) {
		if (G->vertices[i].data == u) {
			return i;
		}
	}
	return -1;
}





/*******************************************************************************************************************************
 * @description：用邻接表创建无向网
 * @param：G
 * @return：
 */
status createUDN_ByAL(adjacencyListGraph* G)
{
	vertexType v1, v2;
	int i, j, k, w;
	arcNode* p;
	printf("请输入顶点数和边数：");
	scanf("%d,%d", &G->vexNum, &G->arcNum);
	printf("请输入顶点信息：");
	for (i = 0; i < G->vexNum; i++) {
		scanf("%c", &G->vertices[i].data);
		G->vertices[i].firstArc = NULL;
	}// 初始化邻接表结束

	for (k = 0; k < G->arcNum; k++) {
		printf("请输入一条边所依附的顶点和权值w：");
		scanf("%c,%c,%d", &v1, &v2, &w);
		i = locateVex_ByAL(G, v1);
		j = locateVex_ByAL(G, v2);
		// 采用头插法插入边结点
		p = (arcNode*)malloc(sizeof(arcNode));
		p->adjVex = j;
		p->info = w;
		p->nextArc = G->vertices[i].firstArc;
		G->vertices[i].firstArc = p;
		// 无向图对称；若为有向网下面可省略
		// 同理：只要下面的不要上面的就可以建立逆邻接表，即入度
		p = (arcNode*)malloc(sizeof(arcNode));
		p->adjVex = i;
		p->info = w;
		p->nextArc = G->vertices[j].firstArc;
		G->vertices[j].firstArc = p;
	}
	return OK;
}

邻接表特点：

方便找任一顶点的所有“邻接点”
节约稀疏图的空间

需要N个头指针+2E个结点（每个结点至少2个域）

方便计算任一顶点的“度”？

对无向图：是的
对有向图：只能计算“出度”；需要构造“逆邻接表”（存指向自己的边）来方便计算“入度”

邻接矩阵和邻接表示法的关系

联系：邻接表中每个链表对应邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数
区别：

对于任一确定的无向图，邻接矩阵是唯一的（行列号与i顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关，和插入方法有关）
邻接矩阵的空间复杂度为O(n^2)，而邻接表的空间复杂度为O(n+e)

用途：邻接矩阵多用于稠密图；而邻接表多用于稀疏图

6.4.3 十字链表

十字链表(Orthogonal List)是有向图的另一种链式存储结构。我们也可以把它看成是将有向图的邻接表和逆邻接表结合起来形成的一种链表

有向图中的每一条弧对应十字链表中的一个弧结点，同时有向图中的每个顶点在十字链表中对应有一个结点，叫做顶点结点

// 图的十字链表存储表示

// 顶点结点
typedef struct vertexNode_CrossLinkedList {
	vertexType data;	// 顶点信息
	arcNode_CrossLinkedList* firstIn;	// 指向第一条入弧的指针
	arcNode_CrossLinkedList* firstOut;	// 指向第一条出弧的指针
}vertexNode_CrossLinkedList;


// 弧结点
typedef struct arcNode_CrossLinkedList {
	int tailVex, headVex;	// 该弧的尾和头顶点的位置
	struct arcNode_CrossLinkedList* headLink;	// 指向弧头相同的下一条弧的指针
	struct arcNode_CrossLinkedList* tailLink;	// 指向弧尾相同的下一条弧的指针
	arcType info;	// 该弧的相关信息
}arcNode_CrossLinkedList;


// 十字链表
typedef struct {
	vertexNode_CrossLinkedList xlist[MAX_VERTEX_NUM];	// 顶点向量
	int vexNum, arcNum;	// 图的当前顶点数和弧数
}crossLinkListGraph;

6.4.4 邻接多重表

// 图的邻接多重表存储表示

// 弧结点
typedef struct arcNode_AdjacencyMultipleList {
	int ivex, jvex;	// 该弧依附的两个顶点的位置
	struct arcNode_AdjacencyMultipleList* ilink;	// 指向依附顶点ivex的下一条弧的指针
	struct arcNode_AdjacencyMultipleList* jlink;	// 指向依附顶点jvex的下一条弧的指针
	arcType info;	// 该弧的相关信息
	int mark;	// 该弧是否已经访问过的标志
}arcNode_AdjacencyMultipleList;



// 顶点结点
typedef struct vertexNode_AdjacencyMultipleList {
	vertexType data;	// 顶点信息
	arcNode_AdjacencyMultipleList* firstArc;	// 指向第一条依附该顶点的弧的指针
}vertexNode_AdjacencyMultipleList;


// 邻接多重表
typedef struct {
	vertexNode_AdjacencyMultipleList vNodes[MAX_VERTEX_NUM];	// 顶点向量
	int vexNum, arcNum;	// 图的当前顶点数和弧数
}adjacencyMultipleList;

6.5 图的遍历

遍历的定义：

从已给的连通图中某以顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算

图的特点：

图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点

怎样避免重复访问？

解决思路：设置辅助数组 visited[n]，用来标记每个被访问过的顶点

初始状态 visited[i] = 0
顶点 i 被访问，改为 visited[i] = 1，防止被多次访问

6.5.1 深度优先遍历

Depth First Search————DFS

方法：

在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接顶点 w1
再从 w1 出发，访问与 w1 邻接但还未被访问过的顶点 w2
然后再从 w2 出发，进行类似的访问，
如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。
接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。
如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；
如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止

实现

/*******************************************************************************************************************************
 * @description：深度优先搜索
 * @param：G
 * @param：v
 */
void DFS(adjacencyMatrixGraph G, int v)
{
	// 访问顶点v
	visited[v] = TRUE;
	printf("%c ", G.vexs[v]);
	// 对v的每个邻接顶点w
	for (int w = 0; w < G.vexNum; w++)
		if (G.arcs[v][w] == 1 && !visited[w])
			DFS(G, w);

}

时间复杂度：

用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，时间复杂度为O(n^2)
用邻接表来表示图，虽然有 2e 个结点，但只需扫描 e 个结点即可完成遍历，加上访问 n 个头结点的时间，时间复杂度为O(n+e)

结论：

稠密图适于在邻接矩阵上进行深度遍历
稀疏图适于在邻接表上进行深度遍历

测试代码

void DFSMain()
{
	adjacencyMatrixGraph G = { 0 };
	// 偷懒直接用邻接矩阵创建无向图
	G.vexs[0] = '1';
	G.vexs[1] = '2';
	G.vexs[2] = '3';
	G.vexs[3] = '4';
	G.vexs[4] = '5';
	G.vexs[5] = '6';

	/* 构建矩阵
	*  0 1 1 1 0 0
	*  1 0 0 0 1 0
	*  1 0 0 0 1 0
	*  1 0 0 0 0 1
	*  0 1 1 0 0 0
	*  0 0 0 1 0 0
	*/

	G.arcs[0][0] = 0; G.arcs[0][1] = 1; G.arcs[0][2] = 1; G.arcs[0][3] = 1; G.arcs[0][4] = 0; G.arcs[0][5] = 0;
	G.arcs[1][0] = 1; G.arcs[1][1] = 0; G.arcs[1][2] = 0; G.arcs[1][3] = 0; G.arcs[1][4] = 1; G.arcs[1][5] = 0;
	G.arcs[2][0] = 1; G.arcs[2][1] = 0; G.arcs[2][2] = 0; G.arcs[2][3] = 0; G.arcs[2][4] = 1; G.arcs[2][5] = 0;
	G.arcs[3][0] = 1; G.arcs[3][1] = 0; G.arcs[3][2] = 0; G.arcs[3][3] = 0; G.arcs[3][4] = 0; G.arcs[3][5] = 1;
	G.arcs[4][0] = 0; G.arcs[4][1] = 1; G.arcs[4][2] = 1; G.arcs[4][3] = 0; G.arcs[4][4] = 0; G.arcs[4][5] = 0;
	G.arcs[5][0] = 0; G.arcs[5][1] = 0; G.arcs[5][2] = 0; G.arcs[5][3] = 1; G.arcs[5][4] = 1; G.arcs[5][5] = 0;

	G.arcNum = 6;
	G.vexNum = 6;


	printf("深度优先搜索：");
	DFS(G, 1);

}

测试截图

6.5.2 广度优先遍历

方法：

从图的某一结点出发，首先依次访问该结点的所有邻接点Vi1，Vi2，Vin，再按这些顶点被访问的先后次序依次访问与它们相邻接的所有未被访问的顶点
重复此过程，直至所有顶点均被访问为止。

实现

类C语言

void BFS(Graph G,int V)
{
    cout<<v;
    visited[v] = true;	// 访问第v个顶点
    initQueue(Q);		// 辅助队列Q初始化，置空
    enQueue(Q, v);		// v进队
    while(!isQueueEmpty(Q)){
        deQueue(Q, u);	// 队头元素出队并置为u
        for(w = FirstAdjVex(G, u);w>=0;w = NextAdjVex(G, u,w)){
            if(!visited[w]){	// w为u的尚为访问的邻接结点
                cout<<w;
                visited[w] = true;	
                enQueue(Q, w);	// w进队
            }// end if
        }// end for
    }// end while
}

时间复杂度：

如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，都要循环检测矩阵中整整一行（n个元素），总的时间代价为O(n^2)
用邻接表来表示图，虽然有 2e 个结点，但只需扫描 e 个结点即可完成遍历，加上访问 n 个头结点的时间，时间复杂度为O(n+e)

C语言实现

/*******************************************************************************************************************************
 * @description：查找第一个邻接点
 * @param：G
 * @param：v
 * @return：
 */
static int firstAdjVex(adjacencyMatrixGraph* G, int v)
{
	for (int i = 0; i < G->vexNum; i++) {
		if (G->arcs[v][i] != 0) {
			return i;
		}
	}
	return -1;
}





/*******************************************************************************************************************************
 * @description：查找下一个邻接点
 * @param：G
 * @param：v
 * @param：w
 * @return：
 */
static int nextAdjVex(adjacencyMatrixGraph* G, int v, int w)
{
	for (int i = w + 1; i < G->vexNum; i++) {
		if (G->arcs[v][i] != 0) {
			return i;
		}
	}
	return -1;
}






/*******************************************************************************************************************************
 * @description：广度优先搜索
 * @param：G
 * @param：v
 */
void BFS(adjacencyMatrixGraph* G, int v)
{
	int w;
	// 初始化辅助数组
	for (int i = 0; i < G->vexNum; i++) {
		visited_BFS[i] = 0;
	}
	// 初始化队列
	queue<int> Q;
	// 访问顶点v
	printf("%c ", G->vexs[v]);
	visited_BFS[v] = 1;
	// 顶点v入队
	Q.push(v);
	// 队列非空
	while (!Q.empty()) {
		// 出队
		v = Q.front();
		Q.pop();
		// 查找v的邻接点
		for (w = firstAdjVex(G, v); w >= 0; w = nextAdjVex(G, v, w)) {
			// 未访问过
			if (!visited_BFS[w]) {
				// 访问顶点w
				printf("%c ", G->vexs[w]);
				visited_BFS[w] = 1;
				// 顶点w入队
				Q.push(w);
			}
		}
	}
}

测试截图

6.5.3 DFS和BFS的比较

空间复杂度相同，都是O(n)借用了栈或队列
时间复杂度只与存储结构有关（邻接矩阵或邻接表）有关，而与搜索路径无关

6.6 图的应用

6.6.1 最小生成树

生成树：所有顶点均由边连接在一起，但不存在回路的图

一个图可以有许多棵不同的生成树

所有生成树具有以下共同特点：

生成树的顶点个数与图的顶点个数相同
生成树是图的极小连通子图，去掉一条边则非连通
一个有n个顶点的连通图的生成树有 n-1 条边
在生成树中再加一条边必然形成回路
生成树中任意啷个顶点间的路径是唯一的

无向图的生成树

MST性质：

在生成树的构造过程中，图中n个顶点分属两个集合：

已落在生成树上的顶点集：U
尚未落在生成树上的顶点集：V-U
接下来则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边

普里姆Prim算法

算法思想：

图解：

以上图G4为例，来对普里姆进行演示(从第一个顶点A开始通过普里姆算法生成最小生成树)。

初始状态：V是所有顶点的集合，即V={A,B,C,D,E,F,G}；U和T都是空！
第1步：将顶点A加入到U中。
此时，U={A}。
第2步：将顶点B加入到U中。
上一步操作之后，U={A}, V-U={B,C,D,E,F,G}；因此，边(A,B)的权值最小。将顶点B添加到U中；此时，U={A,B}。
第3步：将顶点F加入到U中。
上一步操作之后，U={A,B}, V-U={C,D,E,F,G}；因此，边(B,F)的权值最小。将顶点F添加到U中；此时，U={A,B,F}。
第4步：将顶点E加入到U中。
上一步操作之后，U={A,B,F}, V-U={C,D,E,G}；因此，边(F,E)的权值最小。将顶点E添加到U中；此时，U={A,B,F,E}。
第5步：将顶点D加入到U中。
上一步操作之后，U={A,B,F,E}, V-U={C,D,G}；因此，边(E,D)的权值最小。将顶点D添加到U中；此时，U={A,B,F,E,D}。
第6步：将顶点C加入到U中。
上一步操作之后，U={A,B,F,E,D}, V-U={C,G}；因此，边(D,C)的权值最小。将顶点C添加到U中；此时，U={A,B,F,E,D,C}。
第7步：将顶点G加入到U中。
上一步操作之后，U={A,B,F,E,D,C}, V-U={G}；因此，边(F,G)的权值最小。将顶点G添加到U中；此时，U=V。

此时，最小生成树构造完成！它包括的顶点依次是：A B F E D C G。

/*******************************************************************************************************************************
 * @description：Prim算法，生成最小生成树
 * @param：G
 */
void MiniSpanTree_Prim(adjacencyMatrixGraph G) {
	int min, i, j, k;
	int adjvex[MAX_VERTEX_NUM];		// 保存相关顶点下标
	int lowCost[MAX_VERTEX_NUM];	// 保存相关顶点间边的权值
	lowCost[0] = 0;					// 初始化第一个权值为0，即v0加入生成树
	adjvex[0] = 0;					// 初始化第一个顶点下标为0
	for (i = 1; i < G.vexNum; i++) {
		lowCost[i] = G.arcs[0][i];	// 将v0顶点与之有边的权值存入数组
		adjvex[i] = 0;				// 初始化都为v0的下标
	}
	for (i = 1; i < G.vexNum; i++) {
		min = maxInt;				// 初始化最小权值为∞
		j = 1; k = 0;
		while (j < G.vexNum) {
			if (lowCost[j] != 0 && lowCost[j] < min) {
				min = lowCost[j];	// 找出当前最小的
				k = j;				// 将当前最小权值的下标存入k
			}
			j++;
		}
		cout << "(" << adjvex[k] << "," << k << ")" << endl;	// 打印当前顶点边中权值最小的边
		lowCost[k] = 0;	// 将当前顶点的权值设置为0，表示此顶点已经完成任务
		for (j = 1; j < G.vexNum; j++) {
			if (lowCost[j] != 0 && G.arcs[k][j] < lowCost[j]) {
				lowCost[j] = G.arcs[k][j];	// 将v0顶点与之有边的权值存入数组
				adjvex[j] = k;	// 初始化都为v0的下标
			}
		}
	}
}

克鲁斯卡尔Kruskal算法

最小生成树可能不唯一

/*******************************************************************************************************************************
 * @description：sort()所需的比较函数
 * @param：a
 * @param：b
 * @return：
 */
static bool cmp(edge a, edge b) {
	return a.weight < b.weight;
}






/*******************************************************************************************************************************
 * @description：用于查找连线顶点的尾部下标
 * @param：parent
 * @param：f
 * @return：
 */
static int find(int* parent, int f) {
	while (parent[f] > 0) {
		f = parent[f];
	}
	return f;
}






/*******************************************************************************************************************************
 * @description：Kruskal算法，生成最小生成树
 * @param：G
 */
void MiniSpanTree_Kruskal(adjacencyMatrixGraph G) {
	int i, j, n, m;
	int k = 0;	// 用于统计当前生成树边数
	int adjvex[MAX_VERTEX_NUM];	// 保存相关顶点下标
	edge edges[MAX_VERTEX_NUM];	// 定义边集数组，edge的结构为{begin,end,weight}
	for (i = 0; i < G.vexNum; i++) {
		for (j = i; j < G.vexNum; j++) {
			if (G.arcs[i][j] != 0 && G.arcs[i][j] < maxInt) {
				edges[k].begin = i;
				edges[k].end = j;
				edges[k].weight = G.arcs[i][j];
				k++;
			}
		}
	}
	sort(edges, edges + G.arcNum, cmp);	// 按权值大小排序，从小到大
	for (i = 0; i < G.vexNum; i++) {
		adjvex[i] = 0;
	}
	for (i = 0; i < G.arcNum; i++) {
		n = find(adjvex, edges[i].begin);
		m = find(adjvex, edges[i].end);
		if (n != m) {
			adjvex[n] = m;
			cout << "(" << edges[i].begin << "," << edges[i].end << ")" << endl;
		}
	}
}

两种算法比较

6.6.2 最短路径

交通网络用有向网来表示：

顶点：表示地点
弧：表示两个地点有路连通
弧上的权值：表示两地点之间的距离、交通费或途中所花费的时间等

问题抽象：在有向网中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径

最短路径和最小生成树不同，路径上不一定包含 n 个顶点，也不一定包含 n-1 条边

第一类问题：两点间的最短路径

第二类问题：某源点到其它各点最短路径

第一类问题：单源最短路径——用Dijkstra（迪杰斯特拉）算法

第二类问题：所有顶点间的最短路径——用Floyd（弗洛伊德）算法

迪杰斯特拉Dijkstra算法

初始化：先找到从源点V0到各终点Vk的直达路径（V0，Vk），即通过一条弧到达的路径
选择：从这些路径中找出一条长度最短的路径（V0，u）
更新：然后对其余各条路径进行适当调整：

若在途中存在弧（u，Vk），且（V0，u）+（u，Vk）<（V0，Vk），则以路径（V0，u，Vk）代替（V0，Vk）

在调整后的各条路径中，再找长度最短的路径，依此类推

案例分析

/*******************************************************************************************************************************
 * @description：Dijkstra算法
 * @param：G
 * @param：v0
 * @param：P
 * @param：D
 * @return：
 */
status Dijkstra(adjacencyMatrixGraph* G, int v0, int* P, int* D)
{
	int final[MAX_VERTEX_NUM];	// final[i] = 1表示求得顶点vi的最短路径
	int v, w, k, min;
	for (v = 0; v < G->vexNum; v++) {	// 初始化
		final[v] = 0;	// 全部顶点初始化为未知最短路径状态
		D[v] = G->arcs[v0][v];	// 将与v0点有连线的顶点加上权值
		P[v] = 0;	// 初始化路径数组P为0
	}
	D[v0] = 0;	// v0至v0路径为0
	final[v0] = 1;	// v0至v0不需要求路径
	// 开始主循环，每次求得v0到某个v顶点的最短路径
	for (v = 1; v < G->vexNum; v++) {
		min = INFINITY;	// 当前所知离v0顶点的最近距离
		for (w = 0; w < G->vexNum; w++) {	// 寻找离v0最近的顶点
			if (!final[w] && D[w] < min) {
				k = w;
				min = D[w];	// w顶点离v0顶点更近
			}
		}
		final[k] = 1;	// 将目前找到的最近的顶点置为1
		for (w = 0; w < G->vexNum; w++) {	// 修正当前最短路径及距离
			if (!final[w] && (min + G->arcs[k][w] < D[w])) {
				D[w] = min + G->arcs[k][w];	// 修改当前路径长度
				P[w] = k;
			}
		}
	}
	return OK;
}

弗洛伊德Floyd算法

算法思想：

逐个顶点试探
从Vi到Vj的所有可能存在的路径中
选出一条长度最短的路径

//Floyd-Warshall算法核心语句
    for(int k = 0; k < n; k++){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(e[i][k] + e[k][j] < e[i][j]){
                    e[i][j] = e[i][k] + e[k][j];
                }
            }
        }
    }

6.6.3 拓扑排序

有向无环图：无环的有向图，简称DAG图（Directed Acycline Graph）

有向无环图常用来描述一个工程或系统的进行过程。（通常把计划、施工、生产、程序流程等当成是一个工程）

一个工程可以分为若干个子工程，只要完成了这些子工程（活动），就可以导致整个工程的完成

AOV网：拓扑排序

用一个有向图表示一个工程的各个子工程及其相互制约的关系，其中以顶点表示活动，弧表示活动之间的优先制约关系，称这种有向网为顶点表示活动的网，简称AOV网（Activity On Vertex network）

AOE网：关键路径

用一个有向网表示一个工程的各个子工程及其相互制约的关系，以弧表示活动，以顶点表示活动的开始或结束事件，称这种有向图为边表示活动的网，简称为AOE网（Activity On Edge）

拓扑排序例子：排课表

拓扑排序的方法

拓扑排序的一个重要应用：

检测AOV网中是否存在环的方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定存在环

6.6.4 关键路径

把工程计划表示为边表示活动的网络，即AOE网，用顶点表示事件，弧表示活动，弧的权表示活动持续时间

事件表示在它之前的活动已经完成，在它之后的活动可以开始

对于AOE网，我们关心两个问题：

完成整项工程至少需要多少时间
哪些活动是影响工程进度的关键

关键路径：路径长度最长的路径

路径长度：路径上各活动持续时间之和

如何确定关键路径，需要定义4个描述量：

例：

数据结构——第6章-图（数据结构图答案）

6.1 图的定义和基本术语

6.2 案例引入

6.3 图的类型定义

6.4 图的存储结构

6.4.1 邻接矩阵

无向图

有向图

网

实现

6.4.2 邻接表

无向图

有向图

实现

6.4.3 十字链表

6.4.4 邻接多重表

6.5 图的遍历

6.5.1 深度优先遍历

实现

6.5.2 广度优先遍历

实现

6.5.3 DFS和BFS的比较

6.6 图的应用

6.6.1 最小生成树

普里姆Prim算法

克鲁斯卡尔Kruskal算法

两种算法比较

6.6.2 最短路径

迪杰斯特拉Dijkstra算法

弗洛伊德Floyd算法

6.6.3 拓扑排序

6.6.4 关键路径

相关推荐

取消回复欢迎 你 发表评论:

Google 黑客常用搜索语句一览 原力计划

npx简介（npxvip是哪国的）

在 Android 模拟器上运行 ARM 应用（android模拟器原理）

GB28181,B接口协议之SIPRTSPRTPRTMP协议从入门到精通

手机实时提取SIM卡打电话的信令和声音-辅助外设与商用通话方案

安装使用Hoppscotch构建API请求访问与测试

轻松转换!AppleNumbers到Excel的快捷教程

Python自动化办公——后台截图（python 自动截图）

电脑端腾讯文档如何导出excel

网络流媒体经典开源软件宝典webRTC, FFMpeg, SIP_流媒体开发教程

取消回复欢迎你发表评论:

Google 黑客常用搜索语句一览原力计划