计算机软件基础课件：图

图BasicsofComputerSoftware答辩人：XXX

目录图的基本概念1图的存储结构2图的遍历3图的应用4图的基本概念PART1基本概念连通性问题拓扑排序图的存储结构图的遍历最小生成树最短路径关键路径图的基本概念图的定义：图是由顶点集合及顶点间的关系集合组成的一种数据结构：

Graph＝(V,E)其中：V={x|x

某个数据对象}是顶点的有穷非空集合；E={(x,y)|x,y

V}是顶点之间关系的有穷集合，也叫做边或弧的集合，此时的图称为无向图（边）或有向图（弧）。无向图：在无向图中，顶点对(x,y)是无序的。有向图：在有向图中，顶点对<x,y>是有序的。无向完全图：若有n个顶点的无向图有n(n-1)/2条边,则此图为无向完全图。即任何2顶点间均有一条边存在。有向完全图：有n个顶点的有向图有n(n-1)条弧,则此图为有向完全图。即任何2顶点间均有一对方向相反的弧存在。12033456120012无向完全图有向完全图012图的基本概念

邻接顶点：如果(u,v)是E(G)中的一条边，则称u与v互为邻接顶点。子图：设有两个图G＝(V,E)和G’＝(V’,E’)。若V’

V且E’

E,则称图G’是图G的子图。1203子图1030321320图的基本概念权：某些图的顶点或边具有与它相关的数,称之为权。这种带权图叫做网络。如：交通网的公里数、工程造价图中的造价顶点的度TD(v)：一个顶点v的度是与它相关联的边的条数。在有向图中,顶点的度等于该顶点的入度与出度之和。入度ID(v):是以v为终点（弧头）的弧的条数

出度OD(v):是以v为始点（弧尾）的弧的条数图的基本概念ABECF有向图顶点的度(TD)=出度(OD)+入度(ID)TD(B)=OD(B)+ID(B)=3图的基本概念路径：在图G＝(V,E)中,若从顶点vi出发,沿一些边经过一些顶点vp1,vp2,…,vpm，到达顶点vj。则称顶点序列(vivp1vp2...vpmvj)为从顶点vi

到顶点vj

的路径。它经过的边(vi,vp1)、(vp1,vp2)、...、(vpm,vj)应是属于E的边。1203路径：0,1,2,3ABECF路径：A,E,C,F图的基本概念路径长度：非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和。简单路径：若路径上各顶点v1,v2,...,vm均不互相重复,则称这样的路径为简单路径。回路：若路径上第一个顶点v1与最后一个顶点vm重合,则称这样的路径为回路或环。120312031203图的基本概念ABECF路径：A,B,C,F路径长度：3同时它也是简单路径回路：A,E,C,F,A同时它也是简单回路图的基本概念图的存储结构PART2图的存储结构

A.Edge[i][j]=1，若<i,j>∈E或(i,j)∈E0，否则01邻接矩阵（顺序存储）在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表，还有一个表示各个顶点之间关系的邻接矩阵。设图A=(V,E)是一个有n个顶点的图,图的邻接矩阵是一个二维数组A.edge[n][n]，定义：无向图的邻接矩阵是对称的;有向图的邻接矩阵可能是不对称的。0123

邻接矩阵120顶点表0123A.vexs=012B.vexs=图的顺序存储图的存储结构在无向图的邻接表中,

统计第i行(列)1的个数可得顶点I的度。在有向图的邻接表中,

统计第i行1的个数可得顶点i的出度，统计第j列1的个数可得顶点j的入度。

无向图的邻接矩阵有向图的邻接矩阵图的存储结构182301632954网络的邻接矩阵

A.Edge[i][j]=W(i,j)，若i≠j且<i,j>∈E∞或0，若i≠j且<i,j>∉E0，若i=j图的存储结构#defineMaxVerNum100//最大结点数typedefintVertType;//结点类型typedefintEdgeType;

//边的类型typedefstruct{intn;//顶点数VertTypevexs[MaxVerNum];//顶点结构inte;//边的个数EdgeTypeedges[MaxVerNum][MaxVerNum];//边结构}Mgraph;

邻接矩阵表示法的存储结构定义建立有向图G的邻接矩阵存储voidCreatGraph(MGraph*G)//建立有向图G的邻接矩阵存储{inti，j，k，w；charch；

scanf(“%d，%d”，&(G->n)，&(G->e))；//输入顶点数和边数for(i=0；i<G->n；i++)scanf(“%d”，&(G->vexs[i]))；//输入顶点信息，建立顶点表for(i=0；i<G->n；i++) for(j=0；j<G->n；j++)G->edges[i][j]=0；//初始化邻接矩阵for(k=0；k<G->e；k++) {scanf(“%d，%d”，&i，&j)；//输入e条边，建立邻接矩阵 G->edges[i][j]=1；//若加入G->edges[j][i]=1，则为无向图的邻接矩阵}}邻接矩阵的特点无向图的邻接矩阵一定是一对称矩阵无向图的邻接矩阵的第i行(或第i列)非零元素(或非∞元素)个数为第i个顶点的度D(vi)。有向图的邻接矩阵的第i行非零元素(或非∞元素)个数为第i个顶点的出度OD(vi)，第i列非零元素(或非∞元素)个数就是第i个顶点的入度ID(vi)。邻接矩阵表示图，很容易确定图中任意两个顶点之间是否有边相连。由顺序存储的顶点表及n个链式存储的边链表两部分组成邻接表（图的链式存储）ABCDABCD0123边链表顶点表

13021002图的存储结构顶点表：存放顶点本身的数据信息，表中每个表目对应于图的一个顶点，包括两个字段：VerTex：顶点信息Firstedge：指向边链表的第一个结点vertexFirstedge边链表：存放边的信息，链表中每个结点包括三个字段：Adjvex:存放与顶点vi相邻接的顶点vj在顶点表中的位置Info:存放边结点所代表的边的权值（可选项）Next:指向边链表的下一个边结点adjvexinfonexttypedefstructnode//边结点{intadjvex;//邻接点域intinfo;//权值（可选）

structnode*next;//边链表指针}EdgeNode;#defineMaxVertexNum100//最大顶点数typedefstructtnode{intvertex;

//顶点域

structnode*firstedge;//边链表指针}VertexNode;//表结点typedefstruct{AdjListadjlist;//邻接表intn,e;//顶点数和边数}ALGraph;//邻接表vertexFirstedge顶点表结点边链表结点adjvexinfonextTypedefVertexNodeadjlist[MaxVertexNum];//顶点表无向图的邻接表的建立过程：BCADVertexfirstedgeABCD0123adjvexnext1

30

2

01.建立顶点信息（建顶点表）2.输入边信息，插入到边链表中（建立边链表）1

voidCreateALGraph(ALGraph*G)//建立有向图的邻接表存储{inti，j，k；EdgeNode*p；

scanf(“%d，%d”，&(G->n)，&(G->e)；//读入顶点数和边数for(i=0；i<G->n；i++)//建立有n个顶点的顶点表{scanf(“%c”，&(G->adjlist[i].vertex))；//读入顶点信息 G->adjlist[i].firstedge=nil；//顶点的边表头指针设为空}for(k=0；k<G->e；k++)/建立边表 {scanf(“%d，%d”，&i，&j);//读入边<Vi，Vj>的顶点对应序号 p=(EdgeNode*)malloc(sizeof(EdgeNode))；//生成新边表结点p p->adjvex=j；//邻接点序号为j p->next=G->adjlist[i].firstedge；//将边结点插入到顶点Vi的链表头部 G->adjlist[i].firstedge=p；

}}

建立有向图的邻接表算法：有向图的邻接表和逆邻接表邻接表(出边表)ABCABC

1

02

逆邻接表(入边表)ABC1

0

1

邻接表：对每个顶点vi将所有以顶点vi为弧尾（起始结点）的弧链接起来，形成出边表，可以建立有向图的邻接表逆邻接表：对每个顶点vi将所有以顶点vi为弧头（终止结点）的弧链接起来，形成入边表，可以建立有向图的逆邻接表网络(带权图)的邻接表BACD69528(出边链表)(顶点表)ABCD15012336

28

32

19

adjvexinfonext图的遍历PART3图的遍历02广度优先搜索BFS(BreadthFirstSearch)01深度优先搜索DFS(DepthFirstSearch)两种图的遍历方法深度优先搜索DFS(DepthFirstSearch)1.从图中某个顶点v出发，访问v。2.找到刚访问过的顶点的第一个未被访问的邻接点，访问该顶点。以该顶点为新顶点，重复此步骤，直至刚访问的顶点没有未被访问的邻接点为止。3.返回前一个访问过得且仍有未被访问的邻接点的顶点，找到该顶点的下一个未被访问的邻接点，访问该顶点。4.重复步骤2，3，直至图中所有顶点都被访问过。深度优先搜索可以用堆栈来实现深度优先搜索过程可用堆栈来实现69AEDFCBGIH123457878前进回退深度优先访问顺序：69AEDFCBGIH12345A栈底DEGCFBHI图的遍历广度优先搜索BFS(BreadthFirstSearch)1.从图中某个顶点v出发，访问v。2.依次访问v的各个未被访问过得邻接点。3.分别从这些邻接点出发依次访问他们的邻接点4.重复步骤3，直至图中所有的顶点都被访问到。广度优先搜索可以用队列来实现广度优先搜索BFS——类似于树的按层遍历AEDFCBGIH123456789AEDFCBGIH123456789ABCDEFGHIABCDEFGHI访问顺序：队尾广度优先生成树图的应用PART401020403拓扑排序解决工程实践中的活动步骤问题最小生成树解决工程实践中的最小代价问题最短路径解决2点之间的最短距离问题关键路径解决工程实践中的最短工期问题图的应用最小生成树的相关概念最小生成树拓扑排序关键路径最短路径生成树连通图的生成树是一个极小连通子图，它包含图中所有顶点，但只有足以构成一棵树的n-1条边最小生成树问题该问题是构造连通图的最小代价生成树问题连通图无向图中，如果任意两个顶点之间都能够连通，则称此无向图为连通图代价一棵生成树的代价就是树上各边（弧）的代价（权值）之和）最小生成树是带权图例如，若要在n个城市间建立通信联络网，则只需n-1条线路。但在n个城市间，最多可能架设n（n-1）/2条线路，选择哪n-1条线路，使费用最少。123456872135689最小生成树12345687214357681110912连通图普里姆算法克鲁斯卡尔算法最小生成树拓扑排序关键路径最短路径普里姆（Prim）算法假设N=（V，E）是连通图，TE是N上最小生成树中边的集合。从U={u0}（u0

V），TE=空开始；重复执行：在所有uU，vV-U的边(u,v)

E中找一条代价最小的边(u0，v0)并入TE，同时u0并入U，直到U=V为止；此时TE中必有n-1条边，则T=（V，TE）为N的最小生成树。最小生成树拓扑排序关键路径最短路径普里姆（Prim）算法12345687214357681110912123456872135689(1)U={1,2},V-U={3,4,5,6,7,8}初始状态：U={1},V-U={2,3,4,5,6,7,8}(4)U={1,2,4,7,5},V-U={3,6,8}(2)U={1,2,4},V-U={3,5,6,7,8}(3)U={1,2,4,7},V-U={3,5,6,8}(5)U={1,2,4,7,5,6},V-U={3,8}(6)U={1,2,4,7,5,6,3},V-U={8}(7)U={1,2,4,7,5,6,3,8},V-U={}最小生成树拓扑排序关键路径最短路径克鲁斯卡尔（Kruskal）算法假设N=（V，E）是连通图取图中每个顶点自成一个连通分量在{E}中选择代价最小的边，若该边所依附的顶点落在T中不同的连通分量上，则将此边加入生成树T中；否则，舍去此边，再选择下一条代价最小的边。重复上述步，直到T中所有顶点都在同一连通分量上为止。最小生成树拓扑排序关键路径最短路径克鲁斯卡尔（Kruskal）算法12345687214357681110912123456872135689(1){1},{2,4},{3},{5},{6},{7},{8}初始状态：{1},{2},{3},{4},{5},{6},{7},{8}(4){1,2,4,5,7},{3},{6},{8}(2){1,2,4},{3},{5},{6},{7},{8}(3){1,2,4,7},{3},{5},{6},{8}(5){1,2,4,5,6,7},{3},{8}(6){1,2,3,4,5,6,7},{8}(7){1,2,3,4,5,6,7,8}最小生成树拓扑排序关键路径最短路径AOV网与拓扑排序AOV网：用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网。计划、施工过程、生产流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分为若干个叫做“活动”的子工程。完成了这些活动，这个工程就可以完成了。在AOV网络中不能出现有向回路,即有向环。因此，对给定的AOV网络，必须先判断它是否存在有向环。最小生成树拓扑排序关键路径最短路径最小生成树拓扑排序关键路径最短路径课程代码课程名称先修课程C1高等数学C2程序设计基础C3离散数学C1，C2C4数据结构C3，C2C5高级语言程序设计C2C6编译方法C5，C4C7操作系统C4，C9C8普通物理C1C9计算机原理C8学生课程学习工程图

检测有向环的一种方法是对该AOV网络的各个结点(活动)进行拓扑排序。

拓扑排序：将各个顶点(代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。如果通过拓扑排序能将AOV网络的所有顶点都排入一个拓扑有序的序列中,则该网络中必定不会出现有向环。如果AOV网络中存在有向环，此AOV网络所代表的工程是不可行的。最小生成树拓扑排序关键路径最短路径拓扑排序算法①在AOV网络中选一个没有直接前驱的顶点,并输出之;②

从图中删去该顶点,同时删去它发出的所有有向边;③重复以上①、②步,直到全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或:图中还有未输出的顶点,但已跳出处理循环。说明图中还剩下一些顶点,它们都有直接前驱。这时网络中必存在有向环。最小生成树拓扑排序关键路径最短路径例如,对上述学生选课工程图C8C3C5C4C9C6C7C1C2对其进行拓扑排序,还可得其它拓扑序列如：

C2,C5,C1,C8,C9,C3,C4,C7,C6拓扑排序：C8C3C5C4C9C6C7C1C2最小生成树拓扑排序关键路径最短路径C0C1C2C3C4C5拓扑排序的过程(a)有向无环图C0C2C5C1C3(b)输出顶点C4后C1C2C5C3(c)输出顶点C0后C4C0C2C5C1C3(d)输出顶点C3后拓扑序列：C2最小生成树拓扑排序关键路径最短路径C1C5(e)输出顶点C2后C5C1(f)输出顶点C1后C5(g)输出顶点C5后本拓扑序列除了它满足图中给出的所有前驱和后继关系，对于本来没有这种关系的顶点，如C4和C2，也排出了先后次序关系。C4C0C3拓扑序列：C2拓扑排序的过程最小生成树拓扑排序关键路径最短路径AOE网络：用边表示活动的网络如果在带权有向无环图中,用有向边表示一个工程中的活动，用边上权值表示活动持续时间，用顶点表示事件，则这样的有向图叫做用边表示活动的网络,简称AOE网络。最小生成树拓扑排序关键路径最短路径问：完成整个工程至少需要多少时间？为缩短完成工程所需的时间,应当加快哪些活动?<1,3><3,4>那些活动不能耽误，必须按时完成？

<1,3><3,4>

AOE网络在某些工程估算方面非常有用。例如：132481291022天源点→←汇点←关键路径最小生成树拓扑排序关键路径最短路径从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同,但只有各条路径上所有活动都完成了,整个工程才算完成。因此,完成整个工程所需的时间取决于从源点到汇点的最长路径长度,这条路径长度最长的路径就叫做关键路径(CriticalPath)。要找出关键路径，必须找出关键活动,即不按期完成就会影响整个工程进度的活动。最小生成树拓扑排序关键路径最短路径求关键路径步骤求Ve(i):事件Vi的最早发生时间：从始点到vi的最长（加权）路径长度求Vl(i):事件Vi的最迟发生时间：在不拖延整个工期的条件下，vi的可能的最晚发生时间。求e(i):活动ai的最早开始时间：活动的起点的最早发生时间求l(i):活动ai的最迟开始时间：在不拖延整个工期的条件下，活动起点的可能的最晚发生时间。l(i)-e(i):完成活动ai的时间余量最小生成树拓扑排序关键路径最短路径12346791058a1=8a3=7a4=3a6=9a8=13a9=4a11=8a7=9a12=6a13=14a2=6a5=10a10=19a14=1012345678910VeVl086167201620ai12345678910111213