null第7章 图第7章 图 本章主
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
：图的基本概念、图的存储结构和图的常用算法
教学目的：
教学重点：图的各种存储方式及其运算
教学难点：图结构存储方式的选择，几种经典图算法的实现
本章
内容
财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容
：图的基本概念 图的存储结构
图的遍历 最小生成树 最短路径
拓扑排序 关键路径null 本章主要介绍图的基本概念、图的存储结构和有关图的一些常用算法。通过本章学习，读者应该：
1) 了解图的定义和术语
2) 掌握图的各种存储结构
3) 掌握图的深度优先搜索和广度优先搜索遍历算法
4) 理解最小生成树、最短路径、拓扑排序、关键路径等图的常用算法 本章学习导读 null
图（Graph）是一种较线性表和树更为复杂的非线性结构。是对结点的前趋和后继个数不加限制的数据结构，用来描述元素之间“多对多”的关系。
在线性结构中，结点之间的关系是线性关系，除开始结点和 终端结点外，每个结点只有一个直接前趋和直接后继。
在树形结构中，结点之间的关系实质上是层次关系，同层上的每个结点可以和下一层的零个或多个结点（即孩子）相关，但只能和上一层的一个结点（即双亲）相关（根结点除外）。
在图结构中，对结点（图中常称为顶点）的前趋和后继个数不加限制的，即结点之间的关系是任意的。
由此，图的应用极为广泛，特别是近年来的迅速发展，已渗透到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及
数学
数学高考答题卡模板高考数学答题卡模板三年级数学混合运算测试卷数学作业设计案例新人教版八年级上数学教学计划
的其它分支中。null 7. 1 .1 图的定义
图是由一个顶点集 V 和一个弧集 R构成的数据结构。
Graph = (V, R )
V = { x | x 某个数据对象} ， 是顶点的有穷非空集合；
R——边的有限集合
R = {(x, y) | x, y V } 无向图 或
R = {
| x, y V && Path (x, y)}有向图
是顶点之间关系的有穷集合，也叫做边(edge)集合。Path (x, y)表示从 x 到 y 的一条单向通路, 它是有方向的。x弧尾，y弧头。7.1 图及其基本运算 有向图与无向图
有向图中：边用表示，且x与y是有序的。
a. 有向图中的边称为“弧”
b. x——弧尾或初始点 y——弧头或终端点
无向图：边用(x, y) 表示，且顶x与 y是无序的。
完全图
在具有n 个顶点的有向图中，最大弧数为 n(n-1)
在具有n 个顶点的无向图中，最大边数为 n(n-1)/2
顶点的度
无向图：与该顶点相关的边的数目
有向图：
入度ID(v) ：以该顶点为头的弧的数目
出度OD(v) ：以该顶点为尾头的弧的数目
在有向图中, 顶点的度等于该顶点的入度与出度之和。null
图7-1 无向图和有向图 null 在图7-1中，图(a)为无向图，其中G1的顶点集合和边集合分别为：
V(G1)={1，2，3，4，5，6，7}，
E(G1)={(1，2)，(l，3)，(2，3)，(3，4)，(3，5)，(5，6)，(5，7)}。
图(c)为有向图，其中G3的顶点集合和弧集合分别为
V(G3)={1，2，3，4，5，6}，
E(G3)={<1，2>，<1，3>，<1，4>，<3，1>，<4，5>，<5，6>，<6，4>} null
7.1.2 图的基本术语
1． 顶点的度
与顶点v相关的边或弧的数目称作顶点v的度。在有向图中，一个顶点依附的弧头数目，称为该顶点的入度。一个顶点依附的弧尾数目，称为该顶点的出度，某个顶点的入度和出度之和称为该顶点的度。
例如图7-1中，无向图G1中顶点3的度为4，顶点5的度为3。
例如在图7-1中，有向图G3中顶点1的出度OD (1)=3，入度ID (1)=1，其度TD (1)=4。 null
2．路径和回路
在无向图G中，若存在一个顶点序列Vp ,Vi1，Vi2，…，Vin，Vq, 使得（Vp,Vi1）,(Vi1,Vi2),…..，(Vin,Vq)均属于E（G），则称顶点Vp到Vq存在一条路径。
若一条路径上除起点和终点可以相同外，其余顶点均不相同，则称此路径为简单路径。
起点和终点相同的路径称为回路；
简单路径组成的回路称为简单回路。
路径长度
路径上经过的边的数目称为该路径的路径长度。
非带权图的路径长度是指此路径上边/弧的条数。
带权图的路径长度是指路径上各边/弧的权之和。null简单路径 若路径上各顶点 v1,v2,...,vm 均不互相重复, 则称这样的路径为简单路径。
回路 若路径上第一个顶点 v1 与最后一个顶点vm 重合, 则称这样的路径为回路或环。
null3.边和弧
边: 无向图中顶点的偶对，写成（Vx，Vy）或（Vy，Vx）。
弧: 有向图中顶点的偶对,〈Vx,Vy〉表示从Vx到Vy。
弧头: 弧的终点
弧尾: 弧的起点弧 〈Vx，Vy〉
弧尾Vx 弧头Vynull4．子图
设有两个图 G＝(V, E) 和 G‘＝(V’, E‘)。若 V’ V 且 E‘E, 则称 图G’ 是 图G 的子图。null
图7-3 连通分量和强连通分量 5．连通性
在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的。如果图中任意一对顶点vi和vj（vi，vj∈V）都是连通的, 则称此图是连通图。非连通图的极大连通子图叫做连通分量。
图7-1中G1是连通图，G2是非连通图。
G2中有3个连通分量，如图7-3（a）所示。
6 ．强连通图与强连通分量
在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径, 则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。 null
7．网络
权 某些图的边或弧具有与它相关的数, 称之为权。权可以代表一个顶点到另一个顶点的距离，耗费等。
网络 这种带权连通图图一般称为网络。如图7-4所示。 null
8．生成树、生成森林
生成树 一个连通图的生成树是它的极小连通子图，在n个顶点的情形下，有n-1条边。
生成树是对连通图而言的
是连同图的极小连同子图
包含图中的所有顶点
有且仅有n-1条边
非连通图的生成树则组成一个生成森林。若图中有n个顶点，m个连通分量，则生成森林中有n-m条边。null
9．邻接点
顶点: 图中的结点
邻接点:
无向图中，若边(Ｖx,Ｖy)E，
两顶点之间有条边，则两顶点互 为邻接点。
x —— y ( x ,y )
有向图中，若弧(Ｖx,Ｖy)E，
从x到y有一条弧，则y是x的邻接点， 但x不是y的邻接点。
x y null
7.1.3 图的基本运算
图的基本运算也包括查找、插入和删除。
（1）顶点定位运算 确定顶点v在图中的位置；
（2）取顶点运算 求取图中第i个顶点；
（3）求第一个邻接点运算 求图中顶点v的第一个邻接点；
（4）求下一个邻接点运算 已知w为图中顶点v的某个邻接点，求顶点w的下一个邻接点；
（5）插入顶点运算 在图中增添一个顶点v作为图的第n+1个顶点，其中n为插入该顶点前图的顶点个数；
（6）插入弧运算 在图中增添一条从顶点v到顶点w的弧。
（7）删除顶点运算 从图中删除顶点v以及所有与顶点v相关联的弧。
（8）删除弧运算 从图中删除一条从顶点v到顶点w的弧。null 无向图的邻接矩阵是以主对角线对称的，有向图的邻接矩阵可能是不对称的。
在有向图中：
第 i 行 1 的个数就是顶点 i 的出度，
第 j 列 1 的个数就是顶点 j 的入度。
在无向图中, 第 i 行 (列) 1 的个数就是顶点i 的度。7.2.1 邻接矩阵
邻接矩阵(Adjacency Matrix)是表示顶点之间相邻关系的矩阵。设G＝(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵。7.2 图的存储结构 null图7-6 有向图及其邻接矩阵 图7-5 无向图及其邻接矩阵 null 对于无向图，（vi，vj）和（vj，vi）表示同一条边，因此，在邻接矩阵中Aij=Aji。
无向图的邻接矩阵是（关于主对角线）对称矩阵，可用主对角线以上（或以下）的部分表示。
对有向图，弧和< vj，vi >表示方向不同的两条弧，Aij和Aji表示不同的弧，所以有向图的邻接矩阵一般不具有对称性。
邻接矩阵表示法适合于以顶点为主的运算。 null 对于有向图，顶点vi的出度OD (vi)等于邻接矩阵第i行元素之和；顶点vi的入度ID (vi)等于邻接矩阵第i列元素之和，即 ： 对于无向图，顶点vi的度等于邻接矩阵第i行的元素之和，即： OD (vi)= ID (vi)= TD（vi）= 对于带权图的邻接矩阵，定义为：null 顶点表: 一个记录各个顶点信息的一维数组，
邻接矩阵：一个表示各个顶点之间的关系（边或弧）的二维数组。
使用邻接矩阵存储结构，可用一维数组表示图的顶点集合，用二维数组表示图的顶点之间关系（边或弧）的集合，数据类型定义如下：
#define MAX_VERTEX_NUM 20 //最大顶点数
typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
//邻接矩阵类型
typedef struct {
VertexType vexs[MAX_VERTEX_NUM]; //顶点表
AdjMatrix arcs; //邻接矩阵
int vexnum,arcnum; //图的顶点数和弧数
} MGraph;
由于一般图的边或弧较少，其邻接矩阵的非零元素较少，属稀疏矩阵，因此会造成一定存储空间的浪费。 null建立邻接矩阵算法:
void CreateMGraph(MGraph &G)
{ int i,j,k,w;
char v1,v2;
printf("Input vexnum & arcnum:");
scanf("%d,%d",&G.vexnum,&G.arcnum);
printf("Input Vertices:");
scanf("% s",G.vexs);
for (i=0;iadjvex=j;
p->info = w;
p->nextarc=G.vertices[i].firstarc;
G.vertices[i].firstarc=p;
} return;7.2.3 十字链表
十字链表 (Orthogonal List)是有向图的另一种链式存储结构。
可看作是将有向图的邻接表和逆邻接表结合的一种链表。
在十字链表中，为每个顶点vi设置一个结点，它包含数据域data和两个链域firstout、firstin，称为顶点结点。数据域data用于存放顶点vi的有关信息；链域firstin指向以顶点vi为弧头的第一个弧结点；链域firstout指向以顶点vi为弧尾的第一个弧结点。
弧结点包括四个域：尾域tailvex、头域headvex，链域hlink和tlink。 hlink指向弧头相同的下一条弧，tlink指向弧尾相同的下一条弧；data顶点信息，firstin以该顶点为头的第一个弧结点，firstout以该结点为尾的第一个弧结点7.2.3 十字链表
十字链表 (Orthogonal List)是有向图的另一种链式存储结构。
可看作是将有向图的邻接表和逆邻接表结合的一种链表。
在十字链表中，为每个顶点vi设置一个结点，它包含数据域data和两个链域firstout、firstin，称为顶点结点。数据域data用于存放顶点vi的有关信息；链域firstin指向以顶点vi为弧头的第一个弧结点；链域firstout指向以顶点vi为弧尾的第一个弧结点。
弧结点包括四个域：尾域tailvex、头域headvex，链域hlink和tlink。 hlink指向弧头相同的下一条弧，tlink指向弧尾相同的下一条弧；data顶点信息，firstin以该顶点为头的第一个弧结点，firstout以该结点为尾的第一个弧结点顶点结点弧结点null图7-8 十字链表 图7-8为图7-6 (a)有向图的十字链表。 采用十字链表表示有向图，很容易找到以顶点vi为弧尾的弧和以顶点vi为弧头的弧，因此顶点的出度、入度都很容易求得。 null十字链表的数据类型定义如下：
#define MAXV <最大顶点个数>
typedef struct //弧结点
{ int tailvex,headvex; //弧尾和弧头顶点位置
struct ArcNode *hlink,*tlink;
//弧头相同和弧尾相同的弧的链域
}ArcNode;
typedef struct //顶点结点
{ VertexType data; //顶点信息
ArcNode *firstin,*firstout;
//分别指向该顶点的第一条入弧和出弧
}VexNode;null7.2.4 邻接多重表
邻接多重表是无向图的另一种链式存储结构。在邻接多重表中设置一个边结点表示图中的一条边。边结点包含五个域，结构如下所示： 其中：mark 域 标志域，用于对该边进行标记；
ivex 域 存放该边依附的一个顶点vi的位置信息；
ilink 域 该链域指向依附于顶点vi的另一条边的边结点；
jvex 域 存放该边依附的另一个顶点vj的位置信息；
jlink 域 该链域指向依附于顶点vj的另一条边的边结点。
邻接多重表为每个顶点设置一个结点，其结构如下： null图7-9 邻接多重表 图7-9为图7-5 (a)无向图的邻接多重表。 由邻接多重表可以看出，表示边（vi，vj）的边结点通过链域ilink和jlink链入了顶点vi和顶点vj的两个链表中，实现了用一个边结点表示一个边的目的，克服了在邻接表中用两个边结点表示一个边的缺点。因此邻接多重表是无向图的一种很有效的存储结构。 null邻接多重表的结点数据类型定义如下：
#define MAXV <最大顶点个数>
typedef struct //边结点类型
{ int mark; //访问标识
int ivex,jvex; //该边的两个顶点位置信息
struct Enode *ilink,*jlink;
//分别指向依附这两个顶点的下一条边
}Enode;
typedef struct //顶点结点类型
{ VertexType data; //顶点数据域
ENode *firstedge; //指向第一条依附该顶点的边
}Vnode; 7.3 图的遍历 7.3 图的遍历 和树的遍历相似，若从图中某顶点出发访遍图中每个顶点，且每个顶点仅访问一次，此过程称为图的遍历。 (Traversing Graph)。
但是，在图中有回路，从图中某一顶点出发访问图中其它顶点时，可能又会回到出发点，而图中或许还有顶点没有访问到，因此，图的遍历较树的遍历更复杂。
图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。
图的遍历顺序有两种：深度优先搜索（DFS）和广度优先搜索（BFS）。对每种搜索顺序，访问各顶点的顺序也不是唯一的。 null
7.3.1 深度优先搜索（DFS）
1． 深度优先搜索思想
深度优先搜索遍历类似于树的先序遍历。假定给定图G的初态是所有顶点均未被访问过，在G中任选一个顶点i作为遍历的初始点，则深度优先搜索递归调用包含以下操作：
（1）访问搜索到的未被访问的邻接点；
（2）将此顶点的visited数组元素值置1；
（3）搜索该顶点的未被访问的邻接点，若该邻接点存在，则从此邻接点开始进行同样的访问和搜索。
深度优先搜索DFS可描述为：
（1）访问v0顶点；
（2）置 visited[v0]=1；
（3）搜索v0未被访问的邻接点w，若存在邻接点w，则DFS(w)。 null 遍历过程：
DFS 在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接顶点 w1；再从 w1 出发，访问与 w1邻 接但还没有访问过的顶点 w2；然后再从 w2 出发，进行类似的访问，… 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。
接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。null 深度优先搜索的示例 图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。
为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组 visited [ ]，它的初始状态为 0，在图的遍历过程中，一旦某一个顶点 i 被访问，就立即让 visited [i] 为 1，防止它被多次访问。null 对上图，深度优先搜索遍历的顺序（之一）为：
v1 →v2→v4→ v8→ v5→v6→v3→v7。 图7-10 深度优先搜索 null深度优先搜索算法：
int visited[MAX_VERTEX_NUM];
void DFS(ALGraph G, int v)
{ ArcNode *p;
printf("%c",G.vertices[v].data);
visited[v]=1;
p=G.vertices[v].firstarc;
while (p)
{ if (!visited[p->adjvex]) DFS(G,p->adjvex);
p=p->nextarc;
}
} //从第v个顶点出发DFS null整个图的DFS遍历
void DFSTraverse(ALGraph G)
{
for (int v=0;v0 do
(i)delete(Queue,f,r,x); //队首元素出队并赋于x
(ii)对所有x的邻接点w
if visited[w]=0 then
（a）访问w;
（b）visited[w]=1;
（c）insert(Queue,f,r,w); //w进队列 null以邻接表为存储结构，广度优先搜索遍历算法如下：
#define MAXV <最大顶点数>
void bfs(ALGraph *g,int v)
{ ArcNode *p;
int queue[MAXV]; //定义存放队列的数组
int visited[MAXV]； //定义存放结点的访问标志的数组
int f=0,r=0,x,i; //队列头尾指针初始化，把队列置空
for(i=0,in;i++) //访问标志数组初始化
visited[i]=0;
printf(“％d”,v); //访问初始顶点v
visited[v]=1; //置已访问标记
r=(r+1)％MAXV;
queue[r]=v; //v进队
while(f!=r){ //若队列不空时循环
f=(f+1)％MAXV;
x=queuet[f]; //出队并赋给x
p=g->adjlist[x].firstarc;
//找与顶点x邻接的第一个顶点 nullp=g->adjlist[x].firstarc;
//找与顶点x邻接的第一个顶点
while(p!=NULL)
{ if (visited[p->adjvex]==0)
//若当前邻接点未被访问
{ visited[p->adjvex]=l;
//置该顶点已被访问的标志
printf(“％d”，p->adjvex); //访问该顶点
r=(r+1)％MAXV;
queue[r]=p->adjvex; //该顶点进队
}
p=p->nextarc; //找下一个邻接点
}
}
}
// w进队列 null算法
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
： 如果使用邻接表表示图，则循环的总时间代价为 d0 + d1 + … + dn-1 = O(e)，其中的 di 是顶点 i 的度。
如果使用邻接矩阵，则对于每一个被访问过的顶点，循环要检测矩阵中的 n 个元素，总的时间代价为O(n2)。null7.4 最小生成树 1. 生成树
在一个无向连通图G中，其所有顶点和遍历该图经过的所有边所构成的子图G′ 称做图G的生成树。一个图可以有多个生成树，从不同的顶点出发，采用不同的遍历顺序，遍历时所经过的边也就不同，例如图7-12的(b) 和(c) 为图7-12 (a) 的两棵生成树。其中 (b) 是通过DFS得到的，称为深度优先生成树；(c) 是通过BFS得到的，称为广度优先生成树。 图7-12 生成树 null 按照生成树的定义，n 个顶点的连通网络的生成树有 n 个顶点、n-1 条边。而所有包含n-1 条边及n个顶点的连通图都是无回路的树，所以生成树是连通图中的极小连通子图.
由于使用不同的遍历图的
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。如深度优先生成树、广度优先生成树
在图论中，常常将树定义为一个无回路连通图。
对于一个带权的无向连通图，其每个生成树所有边上的权值之和可能不同，我们把所有边上权值之和最小的生成树称为图的最小生成树。求图的最小生成树有很多实际应用。例如，通讯线路铺设造价最优问题就是一个最小生成树问题。null 假设把n个城市看作图的n个顶点，边表示两个城市之间的线路，每条边上的权值表示铺设该线路所需造价。铺设线路连接n个城市，但不形成回路，这实际上就是图的生成树，而以最少的线路铺设造价连接各个城市，即求线路铺设造价最优问题，实际上就是在图的生成树中选择权值之和最小的生成树。构造最小生成树的算法有很多，下面分别介绍克鲁斯卡尔(Kruskal)算法和普里姆(Prim)算法。 7.4.1 克鲁斯卡尔(Kruskal)算法
克鲁斯卡尔算法是一种按权值递增的次序选择合适的边来构造最小生成树的方法。null算法的基本思想： 在图中任取一个顶点K作为开始点，令U={k}，W=V-U，其中V为图中所有顶点集，然后找一个顶点在U中，另一个顶点在W中的边中最短的一条，找到后，将该边作为最小生成树的树边保存起来，并将该边顶点全部加入U集合中，并从W中删去这些顶点，然后重新调整U中顶点到W中顶点的距离, 使之保持最小，再重复此过程，直到W为空集止。
假设G=（V，E）是一个具有n个顶点的带权无向连通图，T= (U，TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，则构造最小生成树的过程如下：
(1) 置U的初值等于V，TE的初值为空集；
(2) 按权值从小到大的顺序依次选取图G中的边，若选取的边未使生成树T形成回路，则加入TE；若选取的边使生成树T形成回路，则将其舍弃。循环执行(2)，直到TE中包含(n-1)条边为止。 null应用克鲁斯卡尔算法构造最小生成树的过程:null为实现克鲁斯卡尔算法需要设置一维辅助数组E，按权值从小到大的顺序存放图的边，数组的下标取值从0到e-1（e为图G边的数目）。
假设数组E存放图G中的所有边，且边已按权值从小到大的顺序排列。n为图G的顶点个数，e为图G的边数。克鲁斯卡尔算法如下：
#define MAXE <最大边数>
#define MAXV <最大顶点数>
typedef struct
{ int vex1; //边的起始顶点
int vex2; //边的终止顶点
int weight; //边的权值
}Edge;
null Void kruskal(Edge E[],int n,int e)
{ int i,j,m1,m2,sn1,sn2,k;
int vset[MAXV];
for(i=0;i则Vj顶点的距离为此弧权值，否则为∞(一个很大的数)，然后每次从W中的顶点中选一个其距离值为最小的顶点Vm加入到S中，每往S中加入一个顶点Vm，就要对W中的各个顶点的距离值进行一次修改。若加进Vm做中间顶点，使+的值小于值，则用+代替原来Vj的距离，修改后再在W中选距离值最小的顶点加入到S中，如此进行下去，直到S中包含了图中所有顶点为止。null图7-16 带权有向图 设G=(V，E)是一个带权有向图，指定的顶点v0为源点，求v0到图的其余各顶点的最短路径。如图7-16所示，若以顶点0为v0，它到其余各顶点的最短路径分别为：
顶点0 顶点1：无路径
顶点0 顶点2：最短路径为（0，2），最短路径长度为10
顶点0 顶点4：最短路径为（0，4），最短路径长度为30
顶点0 顶点3：最短路径为（0，4，3），最短路径长度为50
顶点0 顶点5：最短路径为（0，4，3，5），最短路径长度为60 null从以上图7-16的最短路径可以看出：
(1) 最短路径并不一定是经过边或弧数最少的路径。如从顶点0到顶点5的路径（0，5）长度为100，路径（0，4，5）长度为90，路径（0，2，3，5）长度为70，路径（0，4，3，5）长度为60，其中最短路径为（0，4，3，5），最短路径长度为60。
(2) 这些最短路径中，长度最短的路径上只有一条弧，且它的权值在从源点出发的所有弧的权值中最小。如从源点0出发有3条弧，其中以弧<0，2>的权值为最小。此时（0，2）不仅是顶点 0到顶点2 的一条最短
浙公网安备 33021202002483