数据结构与算法-图
图
图的基本概念
图(Graph)是一种较线性表和树更为复杂的数据结构。
在线性结构中，数据元素之间仅存在线性关系。
在树型结构中，数据元素之间存在明显的一对多的层次关系。
而在图型结构中，结点之间是多对多的任意关系。
图的结构定义：
图：由顶点的有穷非空集合和顶点之间边的集合组成
G(Graph) = (V,R)
其中：V={lv∈Data0bject}, R=[VR}, VR={<v,w>|P(v,w)且(v,w∈V)}
<v,w>表示从v到w的一条弧，并称v为弧尾，w为弧头。
谓词P(v,w)定义了弧<v,w>的意义或信息，表示从v到w的一条单向通道。
- 在图中，若顶点v和w之间的边没有方向，则称这条边为无向边，用无序偶对 (v,w) 表示；
- 若从顶点v到w的边有方向，则称这条边为有向边（也称为弧，以区别于无向边），用有序偶对 <v，w> 表示，v称为弧尾，w称为弧头。
- 如果图的任意两个顶点之间的边都是无向边，则称该图为无向图(undirected graph),否则称该图为有向图(directedgraph)。
- 权(weight)通常是对边赋予的有意义的数值量
- 边上带权的图称为带权图或网图(network graph)。
- 树结构中，权通常赋予在结点
- 有向图或无向图中的弧或边带权后的图分别称作有向网或无向网。
- 图的逻辑关系
线性结构中，数据元素之间具有线性关系，逻辑关系表现为前驱-后继；
树结构中，结点之间具有层次关系，逻辑关系表现为双亲-孩子
图结构中，任意两个顶点之间都可能有关系，逻辑关系表现为邻接
图的基本术语
- 子图：
设图G=(V,VR})和图G’=(V’,VR),且V’∈V,VR’∈VR,则称G’为G的子图。 - 无向完全图、有向完全图
在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图(undirectedcomplete graph)。含有n个顶点的无向完全图有n*(n-1)/2条边。
在有向图中，如果任意两顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图(directed complete graph)。含有n个顶点的有向完全图有n*(n-1)条边。 - 稠密图、稀疏图
称边数很少(个数e<nlogn)的图为稀疏图(sparse graph),反之，称为稠密图(dense graph)。 - 邻接、依附
若无向图顶点v和w之间存在一条边(v,w),则称顶点v和w互为邻接点，称边(v,w) 依附于顶点v和w或边(v,w)与顶点v和w 相关联。
与顶点v 关联的边的数目定义为v的度(TD)
对于有向图，若顶点v和w之间存在一条弧<v,w> 则称顶点v 邻接到顶点w,顶点w 邻接自顶点v,称弧<v,w>与顶点v和w相关联。 - 顶点的度、入度、出度
在无向图中，顶点v的度(degree)是指依附于该顶点的边的个数，通常记为TD (v)
在有向图中，
以v为尾的弧的数目定义为v的出度(OD)
以v为头的弧的数目定义为v的入度(ID)。
出度+入度=该顶点的度(TD) - 路径、路径长度、回路
设无向图 / 有向图G=(V,{VR})中的{u=vi,0Vi,1,Vi,m=w}顶点序列中，有(vi,i-1,vi,i) / <vi,i-1,vi,i>∈VR 1≤j≤m,则称从顶点u到顶点w之间存在一条路径。非带权图路径上边的数目 / 带权图路径上边的权值之和称作路径长度，有向图的路径也是有向的。第一个顶点和最后一个顶点相同的路径称为回路(circuit).。在图中路径可能不唯一，回路也可能不唯一。 - 简单路径、简单回路
在路径序列中，顶点不重复出现的路径称为简单路径(simple path)。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路称为简单回路(simple circuit)。通常情况下，路径指的都是简单路径，回路指的都是简单回路。 - 连通图、连通分量
若无向图 G中任意两个顶点之间都有路径相通，则称此图为连通图。非连通无向图中各个极大连通子图称作此图的连通分量
连通顶点：在无向图中，如果顶点vi和顶点vj(i≠j)之间有路径，则称顶点vi和vj是连通的
连通图只有一个极大连通子图,就是它本身 - 强连通图、强连通分量
对有向图，若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图。非强连通图的极大强连通子图称为强连通分量
强连通顶点：在有向图中，如果从顶点vi到顶点vj和从顶点vj到顶点vi均有路径，则称顶点vi和vj是强连通的 - 生成树
假设一个连通图有n个顶点和e条边，其中n-1条边和n个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。 - 生成森林
对非连通图，则称由各个连通分量的生成树的集合为此非连通图的生成森林。
图的抽象数据类型定义
图是一种与具体应用密切相关的数据结构，基本操作有很大差别
ADT Graph
DataModel
顶点的有穷非空集合和顶点之间边的集合
Operation
CreatGraph：图的建立
DestroyGraph：图的销毁
DFTraverse：深度优先遍历图
BFTraverse：广度优先遍历图
endADT
图的遍历
从图中某一顶点出发访问图中所有顶，并且每个结点仅被访问一次抽象操作，可以是对顶点的各种处理，这里简化为输出顶点的数据
- 在图中，如何选取遍历的起始顶点？
解决方案：将图中的顶点按任意顺序排列起来， 从编号最小的顶点开始 - 如何避免遍历不会因回路而陷入死循环？
解决方案：附设访问标志数组visited[n] - 采用什么次序依次访问图中所有顶点？
解决方案：深度优先遍历和广度优先遍历
图的深度优先遍历
类似于树的前序遍历
- 从顶点 v 出发进行深度优先遍历的基本思想是：
（1）访问顶点 v
（2）从 v 的未被访问的邻接点中选取一个顶点 w，从 w 出发进行深度优先遍历
（3）重复上述两步，直至访问所有和 v 有路径相通的顶点
若是非连通图，则图中一定还有顶点未被访问，要从图中另选一个未被访问的顶点作为起始点，重复上述过程。
深度优先遍历是一个递归的过程 - 用伪代码描述深度优先遍历的操作定义
算法：DFTraverse
输入：顶点的编号 v
输出：无
1. 访问顶点 v ; 修改标志visited[v] = 1;
2. w =顶点 v 的第一个邻接点；
3. while (w 存在)
3.1 if (w 未被访问) 从顶点 w 出发递归执行该算法;
3.2 w = 顶点 v 的下一个邻接点;
图的广度优先遍历
类似于树的层序遍历。
- 从顶点 v 出发进行广度优先遍历的基本思想是：
⑴ 访问顶点 v
⑵ 依次访问 v 的各个未被访问的邻接点 v1 , v2 , …, vk
⑶ 分别从 v1 , v2 , …, vk 出发依次访问它们未被访问的邻接点，直至访问所有与顶点 v 有路径相通的顶点
“先被访问顶点的邻接点”先于“后被访问顶点的邻接点” - 用伪代码描述广度优先遍历的操作定义
算法：BFTraverse
输入：顶点的编号 v
输出：无
1. 队列 Q 初始化;
2. 访问顶点 v ; 修改标志visited [v] = 1; 顶点 v 入队列 Q;
3. while (队列 Q 非空)
3.1 v = 队列 Q 的队头元素出队;
3.2 w = 顶点 v 的第一个邻接点;
3.3 while (w 存在)
3.3.1 如果 w 未被访问，则
访问顶点 w ; 修改标志visited[w] = 1; 顶点 w 入队列 Q；
3.3.2 w = 顶点 v 的下一个邻接点；
图的存储结构
在图中，任何两个顶点之间都可能存在关系（边）->无法通过存储位置表示这种任意的逻辑关系->图无法采用顺序存储结构
1.邻接矩阵的存储结构
- 图的邻接矩阵(adjacency matrix)存储也称数组表示法，其基本思想是：
一维数组：存储图中顶点的信息
二维数组（邻接矩阵）：存储图中各顶点之间的邻接关系
存储顶点之间邻接关系的二维数组称为邻接矩阵。- 设图G=(V,E)有n个顶点，则邻接矩阵是一个n×n的方阵，定义为：
- 网图的邻接矩阵可定义为：
其中，wi,j，表示边(vi,vj)或弧<vi,vj>上的权值；∞表示一个计算机允许的、大于所有边上权值的数。
- 设图G=(V,E)有n个顶点，则邻接矩阵是一个n×n的方阵，定义为：
图的邻接矩阵存储结构不是顺序存储结构
-
无向图存储示意图
- 无向图的邻接矩阵有什么特点？
对称矩阵 - 如何求顶点 v 的度？
第 v 行（或第 v 列）非零元素的个数 - 如何判断顶点 i 和 j 之间是否存在边？
if (edge[i][j] == 1) - 如何求顶点 i 的所有邻接点？
for (j = 0; j < n; j++) if (edge[i][j] == 1) 顶点 j 是顶点 i 的邻接点 - 无向图的邻接矩阵有什么特点？
-
有向图
- 有向图的邻接矩阵一定不对称吗？
顶点间存在方向相反的弧 - 如何求顶点 v 的出度？
第 v 行非零元素的个数 - 如何求顶点 v 的入度？
第 v 列非零元素的个数
- 有向图的邻接矩阵一定不对称吗？
邻接矩阵的实现
const int MaxSize = 10;
template <typename DataType>
class MGraph
{
public:
MGraph(DataType a[ ], int n, int e);
~MGraph( );
void DFTraverse(int v);
void BFTraverse(int v);
private:
DataType vertex[MaxSize];
int edge[MaxSize][MaxSize];
int vertexNum, edgeNum;
};
邻接表基本操作的实现
-
图的建立
- 伪代码
算法：CreatGraph(a[n], n, e) 输入：顶点的数据a[n]，顶点个数n，边的个数e 输出：图的邻接矩阵 1. 存储图的顶点个数vertexNum和边的个数edgeNum ； 2. 将顶点信息存储在一维数组vertex中； 3. 初始化邻接矩阵edge； 4. 依次输入每条边并存储在邻接矩阵edge中： 4.1 输入边依附的两个顶点的编号i和j； 4.2 将edge[i][j]和edge[j][i]的值置为1；template <typename DataType> MGraph<DataType> :: MGraph(DataType a[ ], int n, int e) { int i, j, k; vertexNum = n; edgeNum = e; for (i = 0; i < vertexNum; i++) //存储顶点 vertex[i] = a[i]; for (i = 0; i < vertexNum; i++) //初始化邻接矩阵 for (j = 0; j < vertexNum; j++) edge[i][j] = 0; for (k = 0; k < edgeNum; k++) //依次输入每一条边 { cin >> i >> j; //输入边依附的两个顶点的编号 edge[i][j] = 1; edge[j][i] = 1; //置有边标志 } }- 深度优先遍历
算法：DFTraverse 输入：顶点的编号 v 输出：图的深度优先遍历序列 1. 访问顶点 v; 修改标志visited[v] = 1; 2. j =顶点 v 的第一个邻接点； 3. while (j 存在) 3.1 if (j 未被访问) 从顶点 j 出发递归执行该算法; 3.2 j = 顶点 v 的下一个邻接点;template <typename DataType> void MGraph<DataType> :: DFTraverse(int v) { cout << vertex[v]; visited[v] = 1; for (int j = 0; j < vertexNum; j++) if (edge[v][j] == 1 && visited[j] == 0) DFTraverse( j ); }- 广度优先遍历
算法：BFTraverse 输入：顶点的编号 v 输出：图的广度优先遍历序列 1. 队列 Q 初始化; 2. 访问顶点 v ; 修改标志visited [v] = 1; 顶点 v 入队列 Q; 3. while (队列 Q 非空) 3.1 i = 队列 Q 的队头元素出队; 3.2 j = 顶点 v 的第一个邻接点; 3.3 while (j 存在) 3.3.1 如果 j 未被访问，则 访问顶点 j ; 修改标志visited[j] = 1; 顶点 j 入队列 Q； 3.3.2 j = 顶点 i 的下一个邻接点；template <typename DataType> void MGraph<DataType> :: BFTraverse(int v) { int w, j, Q[MaxSize]; //采用顺序队列 int front = -1, rear = -1; //初始化队列 cout << vertex[v]; visited[v] = 1; Q[++rear] = v; //被访问顶点入队 while (front != rear) //当队列非空时 { w = Q[++front]; //将队头元素出队并送到v中 for (j = 0; j < vertexNum; j++) if (edge[w][j] == 1 && visited[j] == 0 ) { cout << vertex[j]; visited[j] = 1; Q[++rear] = j; } } }
图采用邻接矩阵存储，查找每个顶点的邻接点所需时间为O(n),所以，深度优先和广度优先遍历图的时间复杂度均为O(n2),其中n为图中顶点个数。
邻接矩阵存储结构的空间复杂度是O(n2)
如果采用邻接矩阵存储稀疏图，会生成稀疏矩阵
2.图的邻接表存储结构（链式存储法）
类似于树的孩子表示法
-
邻接表存储的基本思想是：
边表（邻接表）：顶点 v 的所有邻接点链成的单链表
顶点表：所有边表的头指针和存储顶点信息的一维数组
其中，vertex为数据域，存放顶点信息；firstEdge为指针域，指向边表的第一个结点；adivex为邻接点域，存放该顶点的邻接点在顶点表中的下标①；nxt为指针域，指向边表的下一个结点。对于网图，边表结点还需增设info域存储边上信息（如权值）。
-
存储结构定义
struct EdgeNode //定义边表结点
{
int adjvex; //邻接点域
EdgeNode *next;
} ;
template <typename DataType>
struct VertexNode //定义顶点表结点
{
DataType vertex;
EdgeNode *firstEdge;
};
- 基本操作
- 边表中的结点对应图中的一条边
- 对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边。
- 设图有n个顶点e条边，邻接表的空间复杂度是O(n+e)
- ①对于无向图，顶点i的度等于顶点i的边表中的结点个数。
对于有向图，顶点 i 的出度等于顶点 i 的出边表中的结点个数；顶点 i 的入度等于所有出边表中以顶点 i 为邻接点的结点个数。p = adjlist[v].firstEdge; count = 0; while (p != nullptr) { count++; p = p->next; }- ②判断从顶点 i 到顶点 j 是否存在边，只需测试顶点的边表中是否存在邻接点域为 j 的结点。
- ③查找顶点 i 的所有邻接点，只需遍历顶点的边表，该边表中的所有结点都是顶点 i 的邻接点。
p = adjlist[v].firstEdge; while (p != nullptr) { j = p->adjvex; //j是v的邻接点 p = p->next; }- 无向图存储空间：n+2e
2.邻接表的实现
const int Maxsize 10; //图的最多顶点数
template <typename DataType>
class ALGraph{
public:
ALGraph(DataType a[l,int n,int e); //构造函数
~ALGraph () //析构函数
void DETraverse(int v); //深度优先遍历图
void BFTraverse(int v) //广度优先遍历图
private:
VertexNode<DataType>adjlist [Maxsize]; //存放顶点表的数组
int vertexNum,edgeNum; //图的顶点数和边数
};
- 逆邻接表（有向图）
边表（邻接表）：顶点 v 的所有入度顶点链成的单链表
邻接表基本操作的实现
- 构造函数一图的建立
- 伪代码
算法：构造函数ALGraph
输人：顶点的数据信息a[n],顶点个数n,边的个数e
输出：图的邻接表
1.存储图的顶点个数和边的个数：
2,将顶点信息存储在顶点表中，将该顶点边表的头指针初始化为NULL:
3.依次输人边的信息并存储在边表中：
3.1输入边所依附的两个顶点的编号1和：
3.2生成边表结点s,其邻接点的编号为j:
3.3将结点s插人到第1个边表的表头：
template <typename DataType>
ALGraph<DataType>::ALGraph(DataType a[],int n,int e){
int i,j,k;
EdgeNode *s=nullptr;
vertexNum = n;edgeNum = e;
for(i=0;i<vertexNum;1++) //输人顶点信息，初始化顶点表
{
adjlist[i].vertex = a[i]; //adjlist[]顶点表数组
adjlist[i].firstEdge = nullptr;
for (k=0;k edgeNum;k++) //依次输人每一条边
{
cin>>i>>j; //输入边所依附的两个顶点的编号
s = new EdgeNode;s->adjvex =j; //生成一个边表结点s
s->next = adjlist[i].firstEdge; //将结点s插入表头
adjlist[i].firstEdge=s;
}
}
- 析构函数—图的销毁
template <typename DataType>
ALGraph<DataType>::~ALGraph()
{
EdgeNode *p=nullptr,*q=nullptr;
for (int i=0;i<vertexNum;i++)
{
p=q=adjlist[i].firstEdge;
while (p !=nullptr)
{
p-p->next
delete q;q=p;
}
}
}
- 深度优先遍历
算法：DFTraverse
输入：顶点的编号 v
输出：无
1. 访问顶点 v; 修改标志visited[v] = 1;
2. j =顶点 v 的第一个邻接点；
3. while (j 存在)
3.1 if (j 未被访问) 从顶点 j 出发递归执行该算法;
3.2 j = 顶点 v 的下一个邻接点;
template <typename DataType>
void ALGraph<DataType>::DFTraverse(int v)
{
int j;
EdgeNode p=nullptr;
cout <<adjlist[v].vertex;visited[v]=1;
p=adjlist[v].firstEdge; //工作指针P指向顶点v的边表
while(p !nullptr) //依次搜索顶点ⅴ的邻接点
{
j=p->adjvex;
if(visited[j]==0)DFTraverse(j)
p=p->next;
}
}
- 广度优先遍历算法
算法：BFTraverse
输入：顶点的编号 v
输出：无
1. 队列 Q 初始化;
2. 访问顶点 v ; 修改标志visited [v] = 1; 顶点 v 入队列 Q;
3. while (队列 Q 非空)
3.1 i = 队列 Q 的队头元素出队;
3.2 j = 顶点 v 的第一个邻接点;
3.3 while (j 存在)
3.3.1 如果 j 未被访问，则
访问顶点 j ; 修改标志visited[j] = 1; 顶点 j 入队列 Q；
3.3.2 j = 顶点 i 的下一个邻接点；
template <typename DataType>
void ALGraph<DataType>::BFTraverse(int v)
int w,j,Q[Maxsize]; //采用顺序队列
int front =-1,rear =-1; //初始化队列
EdgeNode *p=nullptr;
cout <<adjlist[v].vertex;visited[v]=1;
Q[++rear]=v: //被访问顶点入队
while (front!=rear) //当队列非空时
{
w=Q[++front];
p=adjlist[w].firstEdge; //工作指针p指向顶点ⅴ的边表
while (p!=nullptr)
{
j=p->adjvex;
if (visited[j]==0){
cout<<adjlist[j].vertex; visited[j]=1;
Q[++rear]=j;
{
p=p->next;
}
}
}
邻接矩阵和邻接表的比较
1.空间性能比较
图的邻接矩阵是一个n×n的矩阵，所以其空间代价是O(n2)。
邻接表的空间代价是O(n+e)。
2.时间性能比较
在图的算法中访问某个顶点的所有邻接点是较常见的操作。如果使用邻接表，只需要检查此顶点的边表，即只检查与它相关联的边，平均需要查找O(e/n)次：如果使用邻接矩阵，则必须检查所有可能的边，需要查找O(n)次。
3.唯一性比较
当图中每个顶点的编号确定后，图的邻接矩阵表示是唯一的；但图的邻接表表示不是唯一的，边表中结点的次序取决于边的输入次序以及结点在边表的插入算法。
4.对应关系
图的邻接矩阵和邻接表虽然存储方法不同，但存在着对应关系。邻接表中顶点i的边表对应邻接矩阵的第行，整个邻接表可看作是邻接矩阵的带行指针的链接存储。
最小生成树
- 完全图：任意两个顶点之间都有直达的边相连的无向图。
- 连通图：任意两个顶点之间都有路径相通的无向图。
- 生成树：一个连通图的生成树是指一个极小连通子图，含有图中的全部n个顶点，但只有足以构成一棵树的n-1条边。多——构成回路，少——不连通。生成树可能不唯一。
- 极大连通子图如果加入任何一个不在图的点集中的点都会导致它不再连通。
- 极小连通子图如果删除一条边，就无法构成生成树，也就是说给极小连通子图的每个边都是不可少的。
- 无向连通网的生成树上各边的权值之和称为该生成树的代价，在图的所有生成树中，代价最小的生成树称为最小生成树(minimal spanning tree)。
- 最小生成树要解决的两个问题：
1尽可能选取权值小的边，但不能构成回路
2选取n-1条恰当的边以连接网的n个顶点。
算法一：普里姆算法(Prim)
算法二：克鲁斯卡尔算法(Kruskal)
Prim算法（普里姆算法）
- 基本思想：
取图中任意一个顶点V作为生成树的根，之后往生成树上添加新的顶点W。在添加的顶点W和已经在生成树上的顶点V之间必定存在一条边，该边的权值在所有连通顶点V和W之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有个顶点为止。 - 在生成树的构造过程中，图中n个顶点分属两个集合：己落在生成树上的顶点集U和尚未落在生成树上的点集V-U；则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。
- 伪代码
算法：Prim
输入：无向连通网G=(V，E)
输出：最小生成树T=(U，TE)
1. 初始化：U = {v}； TE={ }；
2. 重复下述操作直到U = V：
2.1 在E中寻找最短边(i，j)，且满足i∈U，j∈V-U；
2.2 U = U + {j}；
2.3 TE = TE + {(i，j)}；
- Prim算法的存储结构。
①图的存储结构：由于在算法执行过程中，需要不断读取任意两个顶点之间边的权值，所以，图采用邻接矩阵存储。
②候选最短边集：设数组adjvex[n]和lowcost[n]分别表示候选最短边的邻接点和权值，数组元素adjvex[i]和lowcost[i]的值如下所示，其含义是候选最短边(i,j)的权值为w，其中i∈V-U,j∈U。
adjvex[i]=j
lowcost[i]=w
由于顶点j从集合V一U进入集合U后，候选最短边集发生了变化，依据下式对数组adjvex[n]和lowcost[n]进行更新，然后将lowcost[j]置为0，表示将顶点j加人集合U中。
lowcost[i]=min{lowcost[i]，边(i,j)的权值} / 0,v∈U,
adjvex[i]=j(如果边(i,j)的权值<lowcost[i])
void Prim(int v) /*假设从顶点v出发*/
{
int i, j, k, adjvex[MaxSize], lowcost[MaxSize];
for (i = 0; i < vertexNum; i++) /*初始化辅助数组shortEdge*/
{
lowcost[i] = edge[v][i]; adjvex[i] = v;
}
lowcost[v] = 0; /*将顶点v加入集合U*/
for (k = 1; k < vertexNum; i++) /*迭代n-1次*/
{
j = MinEdge(lowcost, vertexNum) /*寻找最短边的邻接点j*/
cout << j << adjvex[j] << lowcost[j];
lowcost[j] = 0; //顶点)加入集合0
for (i = 0; i < vertexNum; i++) /*调整数组shortEdge[n]*/
if (edge[i][j] < lowcost[i]) {
lowcost[i] = edge[i][j]; adjvex[i] = j;
}
}
}
}
MinEdge函数实现在数组lowcost中查找最小权值并返回其下标
Prim算法的时间复杂度为O(n^2^)
Kruskal（克鲁斯卡尔算法）
- Prim算法的关键是什么？
找到顶点分别位于U 和 V-U 中的连接 U 和 V-U 的最短边
Prim算法：先构造满足条件的候选最短边集lowcost，再查找最短边 lowcost[i]
Kruskal算法：先查找最短边，再判断是否满足条件
算法：Kruskal算法
输入：无向连通网G=(V，E)
输出：最小生成树T=(U，TE)
1. 初始化：U=V；TE={ }；
2. 重复下述操作直到所有顶点位于一个连通分量：
2.1 在E中选取最短边(u，v);
2.2 如果顶点 u、v 位于两个连通分量，则
2.2.1 将边 (u，v) 并入TE；
2.2.2 将这两个连通分量合成一个连通分量；
2.3 在 E 中标记边 (u，v)，使得 (u，v) 不参加后续最短边的选取；
Kruskal算法——存储结构
- ①图的存储结构：因为Kruskal算法依次对图中的边进行操作，因此考虑采用边集
数组(edge set array)存储。为了提高查找最短边的速度，可以先对边集数组按边上的权
值排序。
边集数组元素的结构体定义
struct//定义边集数组的元素类型
{
int from,to,weight;//假设权值为整数
}EdgeType;
- ②连通分量的顶点所在的集合：由于涉及集合的查找和合并等操作，考虑采用并查集来实现。并查集是将集合中的元素组织成树的形式，合并两个集合，即将一个集合的根结点作为另一个集合根结点的孩子，图6-19给出了并查集的合并过程示例。
- 为了便于在并查集中进行查找和合并操作，树采用双亲表示法存储。设数组parent[n],
- 如何判断两个顶点是否位于同一个连通分量呢？
vex1 = FindRoot(parent, i);
vex2 = FindRoot(parent, j);
if (vex1 != vex2) {
}
int FindRoot(int parent[ ], int v)
{
int t = v;
while (parent[t] > -1)
t = parent[t];
return t;
}
- 如何合并两个连通分量呢？
vex1 = FindRoot(parent, i);
vex2 = FindRoot(parent, j);
if (vex1 != vex2) {
parent[vex2] = vex1;
}
Kruskal算法——C++实现
void Kruskal( )
{
int i, num = 0, vex1, vex2;
for (i = 0; i < vertexNum; i++)
parent[i] = -1;
for (num = 0, i = 0; num < vertexNum; i++)
{
vex1 = FindRoot(parent, edge[i].from);
vex2 = FindRoot(parent, edge[i].to);
if (vex1 != vex2) {
cout << edge[i].from << edge[i].to << edge[i].weight;
parent[vex2] = vex1;
num++;
}
}
}
const int MaxVertex = 10;
const int MaxEdge = 100;
template <typename DataType>
class EdgeGraph
{
public:
EdgeGraph(DataType a[ ], int n, int e);
~EdgeGraph( );
void Kruskal( );
private:
int FindRoot(int parent[ ], int v)
DataType vertex[MaxVertex];
EdgeType edge[MaxEdge];
int vertexNum, edgeNum;
} ;
- Prim算法时间复杂度为0(n2)，适用于稠密图
Kruskal算法的时间复杂度为O(elog2e)，适用于求稀疏网的最小生成树。
最短路径
最短路径(shortest path)：在非网图中，是指两顶点之间经历的边数最少的路径。路径上的第一个顶点称为源点(source),最后一个顶点称为终点(destination)。在网图中，最短路径是指两顶点之间经历的边上权值之和最少的路径。
- 从单源点到其余各点的最短路径，迪杰斯特拉算法(Dijkstra)
- 每一对顶点之间的最短路径，弗洛伊德算法(Floyd)
Dijkstra算法（迪杰斯特拉）
w<v, vi>：从顶点 v 到顶点 vi 的权值
dist(v, vi)：表示从顶点 v 到顶点 vi 的最短路径长度
- 基本思想
-
Dijkstra算法按路径长度递增的次序产生最短路径
-
只可能经过已经产生终点的顶点
-
将顶点集合V分成两个集合，一类是生长点的集合S,包括源点和已经确定最短路径的顶点；另一类是非生长点的集合V一S,包括所有尚未确定最短路径的顶点，并使用一个待定路径表，存储当前从源点到每个非生长点v的最短路径。
-
(1)初始时，集合S中仅包含源点v0,集合V-S中包含除源点v0以外的所有顶点，V0到V-S中各顶点的路径长度或着为某个权值（如果它们之间有弧相连），或者为∞（没有弧相连）。
-
(2)按照最短路径长度递增的次序，从集合V-S中选出到顶点V0路径长度最短的顶点VK加入到S集合中。
-
(3)加入VK之后，为了寻找下一个最短路径，必须修改从V0到集合V-S中剩余所有顶点V的最短路径。若在路径上加入VK之后，使得V0到V1的路径长度比原来没有加入VK时的路径长度短，则修正V0到v1的路径长度为其中较短的。
-
(4)重复以上步骤，直至集合V-S中的顶点全部被加入到集合S中为止。
-
- 路径特点
- 路径长度最短的最短路径的特点：
在这条路径上，必定只含一条弧，并且这条弧的权值最小。（设为V0→VK) - 下一条路径长度次短的最短路径的特点：
它只可能有两种情况：或者是直接从源点到该点Vi(只含一条弧)；或者是从源点经过顶点VK,再到达Vi(由两条弧组成)。 - 再下一条路径长度次短的最短路径特点：
它可能有两种情况：或者是直接从源点到该点（只含一条弧）；或者是从源点经过顶点VK、Vi再到达该顶点（由多条弧组成）。 - 其余最短路径的特点：
它或者是直接从源点到该点（只含一条弧）；或者是从源点经过已求得最短路径的顶点，再到达该顶点。
- 路径长度最短的最短路径的特点：
Dijkstra算法的存储结构。
邻接矩阵
-
如何存储dist(v, vi)呢？
整型数组dist[n]：存储当前最短路径的长度
字符串数组path[n]：存储当前的最短路径，即顶点序列 -
①图的存储结构：因为在算法执行过程中，需要快速求得任意两个顶点之间边上的权值，所以，图采用邻接矩阵存储。
-
②辅助数组dist[n]：元素dist[i]表示当前所找到的从源点v到终点vi的最短路径长度。初态为：若从v到vi有弧，则dist[i]为弧上的权值：否则置dist[i]为∞。若当前求得的终点为vk，则根据下式进行迭代：
dist[i]=min {dist[i],dist[k]+edge[k][i]} 0 <= i <= n-1
若vi∈S,dist[i]表示源点到vi的最短路径长度
若vi∈V-S,dist[i]表示源点到vi的只包括S中的顶点为中间顶点的最短路径。 -
③辅助数组path[n]：元素path[i]是一个字符串，表示当前从源点v到终点vi的最短路径。初态为：若从v到u:有弧，则path[i]为"vvi",否则置path[]为空串。
-
伪代码
算法：Dijkstra算法
输入：有向网图 G=(V，E)，源点 v
输出：从 v 到其他所有顶点的最短路径
1. 初始化：集合S = {v}；dist(v, vi) = w<v, vi>, (i=1...n)；
2. 重复下述操作直到 S == V
2.1 dist(v, vk) = min{dist(v, vj), (j=1..n)}；
2.2 S = S + {vk}；
2.3 dist(v, vj)=min{dist(v, vj), dist(v, vk) + w<vk, vj>}；
void Dijkstra(int v) /*从源点v出发*/
{
int i, k, num, dist[MaxSize]; string path[MaxSize];
for (i = 0; i < vertexNum; i++)
{
dist[i] = edge[v][i]; path[i] = vertex[v] + vertex[i];
}
for (num = 1; num < vertexNum; num++)
{
for (k = 0, i = 0; i < vertexNum; i++)
if ((dist[i] != 0) && (dist[i] < dist[k])) k = i;
cout << path[k] << dist[k];
for (i = 0; i < vertexNum; i++)
if (dist[i] > dist[k] + edge[k][i]) {
dist[i] = dist[k] + edge[k][i]; path[i] = path[k] + vertex[i];
}
dist[k] = 0;
}
}
时间复杂度是O(n2)。
Floyd算法
求每一对顶点的最短路径问题
【想法 1】每次以一个顶点为源点调用Dijkstra算法。显然，时间复杂度为O(n3)
基本思想
w<vi, vj>：从顶点 vi 到顶点 vj 的权值
distk(vi, vj)：从顶点 vi 到顶点 vj 经过的顶点编号不大于 k 的最短路径长度
dist-1(vi, vj) = w<vi, vj>
distk(vi, vj) = min{distk-1(vi, vj), distk-1(vi, vk)+distk-1(vk, vj)}
算法：Floyd算法
输入：带权有向图 G=(V，E)
输出：每一对顶点的最短路径
1. 初始化：假设从 vi 到 vj 的弧是最短路径，即dist-1(vi, vj)=w<vi, vj>；
2. 循环变量 k 从 0~n-1 进行 n 次迭代：
distk(vi, vj)=min{distk-1(vi, vj), distk-1(vi, vk)+distk-1(vk, vj)}
void Floyd( )
{
int i, j, k, dist[MaxSize][MaxSize];
for (i = 0; i < vertexNum; i++)
for (j = 0; j < vertexNum; j++)
dist[i][j] = edge[i][j];
}
for (k = 0; k < vertexNum; k++)
for (i = 0; i < vertexNum; i++)
for (j = 0; j < vertexNum; j++)
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
#C++实现
void Floyd( )
{
int i, j, k, dist[MaxSize][MaxSize];
for (i = 0; i < vertexNum; i++)
for (j = 0; j < vertexNum; j++)
dist[i][j] = edge[i][j];
for (k = 0; k < vertexNum; k++)
for (i = 0; i < vertexNum; i++)
for (j = 0; j < vertexNum; j++)
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
最小生成树有且仅有n-1条边，最短路径每条路径最多有n-1条边。
拓扑排序
- 几乎所有的工程都可以分为若干个称作活动的子工程，某些活动之间通常存在一定的约束条件
AOV网
- AOV网（顶点表示活动的网）（activity on vertex network）：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系
- AOV网中出现回路意味活动之间的优先关系是矛盾的
- 而测试AOV网是否存在回路的方法，就是对AOV网进行拓扑排序
拓扑序列的定义
- 拓扑序列：设有向图G=(V，E)具有 n 个顶点，则顶点序列 v0, v1, …, vn-1 称为一个拓扑序列，当且仅当满足下列条件：若从顶点 vi到 vj 有一条路径，则在顶点序列中顶点 vi 必在顶点 vj 之前
- 拓扑排序(topological sort)：对一个有向图构造拓扑序列的过程
- 一个AOV网的拓扑序列可能不唯一
基本思想
(1)从AOV网中选择一个没有前驱的顶点并输出；
(2)从AOV网中删去该顶点以及所有以该顶点为尾的弧；
(3)重复上述两步，直到全部顶点都被输出，或AOV网中不存在没有前驱的顶点。
存储结构
- (1)图的存储结构：因为在拓扑排序的过程中，需要查找所有以某顶点为尾的弧，即需要找到该顶点的所有出边，所以，图应该采用邻接表存储。另外，在拓扑排序过程中，需要对某顶点的入度进行操作，例如，查找入度等于零的顶点，将某顶点的入度减1等，而在图的邻接表中对顶点入度的操作不方便，所以，在顶点表中增加一个入度域，以方便对入度的操作。图6-27给出了一个AOV网及其邻接表存储示意图。
- (2)查找没有前驱的顶点：为了避免每次查找时都去遍历顶点表，设置一个栈，凡是AOV网中入度为0的顶点都将其压栈。
- 伪代码
算法：TopSort
输入：有向图G=(V，E)
输出：拓扑序列
1. 栈 S 初始化；累加器 count 初始化；
2. 扫描顶点表，将入度为 0 的顶点压栈；
3. 当栈 S 非空时循环
3.1 j = 栈顶元素出栈；输出顶点 j；count++；
3.2 对顶点 j 的每一个邻接点 k 执行下述操作：
3.2.1 将顶点 k 的入度减 1；
3.2.2 如果顶点 k 的入度为 0，则将顶点 k 入栈；
4. if (count<vertexNum) 输出有回路信息；
- C++实现
void TopSort( )
{
int i, j, k, count = 0, S[MaxSize], top = -1;
EdgeNode *p = nullptr;
for (i = 0; i < vertexNum; i++) /*扫描顶点表*/
if (adjlist[i].in == 0) S[++top] = i;
while (top != -1 ) /*当栈中还有入度为0的顶点时*/
{
j = S[top--]; cout << adjlist[j].vertex; count++;
p = adjlist[j].first;
while (p != nullptr) /*描顶点表，找出顶点j的所有出边*/
{
k = p->adjvex; adjlist[k].in--;
if (adjlist[k].in == 0) S[++top] = k; /*将入度为0的顶点入栈*/
p = p->next;
}
}
if (count < vertexNum ) cout << "有回路”;
}
时间复杂度为O(n+e)。
AOE 网的定义
- 几乎所有的工程都可以分为若干个称作活动的子工程，活动之间存在某些制约关系，每个活动通常需要一个持续的时间
- 源点：整个工程的开始点，没有入边的顶点。其入度为0
终点：整个工程的结束点，没有出边的顶点，其出度为0 - AOE网（边表示活动的网）（activity on edge network）：在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，边上的权值表示活动的持续时间
- AOV网由顶点表示活动，AOE网由边表示活动；
*AOE网的性质：
（1）只有在进入某顶点的各活动都已经结束，该顶点所代表的事件才能发生
（2）只有在某顶点所代表的事件发生后，从该顶点出发的各活动才能开始
- AOE网能够解决什么问题？
（1） 完成整个工程至少需要多少时间?
（2）为缩短完成工程所需的时间， 应当加快哪些活动?
这个AOE网的最短工期是多少？ - 关键路径：AOE网中从源点到终点的最长路径，具有最大路径长度的路径
- 关键活动：关键路径上的活动
不按期完成关键活动就会影响整个工程的进度
换言之，要缩短整个工期，必须加快关键活动的进度
关键路径
基本思想
- 如何求关键路径呢？
求关键活动 - 关键活动为什么是关键的？
关键活动的开始时间不能推迟 - 如何求关键活动呢？
关键活动的最早开始时间和最晚开始时间相等
算法：关键路径算法
输入：带权有向图 G=(V，E)
输出：关键活动
1. 计算各个活动的最早开始时间和最晚开始时间
2. 计算各个活动的时间余量，时间余量为 0 即为关键活动
- 为了找出关键活动及关键路径，需要定义如下数组
设带权有向图 G=(V，E)含有 n 个顶点 e 条边，设置 4 个一维数组：
（1）事件的最早发生时间 ve[n]
ve[0] = 0
ve[k] = max{ve[j] + len<vj, vk>} (<vj, vk>∈p[k]) p[k]：所有到达 vk 的有向边
事件 v2 的最早发生时间是多少？
ve[2] = max{ve[0] + a1, ve[1] + a2} = {0 + 3, 4 + 2} = 6
AOE网的性质：只有进入 vk 的所有活动<vj，vk>都结束，vk 代表的事件才能发生
（2）事件的最迟发生时间 vl[n]
vl[n-1] = ve[n-1]
vl[k] = min{vl[j]-len<vk , vj}（<vk, vj>∈s[k]）s[k] ：所有从 vk 发出的有向边
事件 v3 的最迟发生时间是多少？
vl[3] = ve[3] = 10
事件 v2 的最迟发生时间是多少？
vl[2] = vl[3] – a3 = 6
事件 v0 的最迟发生时间是多少？
ve[0] = min{ve[1] – a0, ve[2] – a1} = {4 – 4, 6 – 3} = 0
（3）活动的最早开始时间 ae[e]
（4）活动的最晚开始时间 al[e]
若活动 ai 由有向边<vk, vj>表示，则
ae[i] = ve[k]
al[i] = vl[j] - len<vk, vj>
活动 a2 的最早开始时间是多少？
ae[2] = ve[1] = 4
活动 a2 的最晚开始时间是多少？
al[2] = vl[2] - 2 = 4
a0,a2,a3,a4是关键路径