资源描述
.,第七章图,数据结构,.,一、图的定义(Graph),2,图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构： Graph( V, E ) 其中V = x | x数据对象是顶点的有穷非空集合 E是顶点之间关系的有穷集合，包括 E1 = (x, y) | x, y V 边的集合 或 E2 = | x, y V 弧的集合,第一节图的定义与术语,.,第一节图的定义与术语,交通图（公路、铁路） 顶点：地点 边：连接地点的公路交通图中有单行道双行道,分别用有向边、无向边表示；电路图 顶点：元件 边：连接元件之间的线路通讯线路图 顶点：地点 边：地点间的连线,.,二、无向图(Undigraph),4,第一节图的定义与术语,用(x,y)表示两个顶点x,y之间的一条边(edge)N=V,E，V=0,1,2,3,4,5，E=(0,1), (0,4), (0,5), (1,2), (1,3), (1,5), (2,3), (3,4), (3,5), (4,5),.,二、无向图(完全图),5,第一节图的定义与术语,如果无向图有n(n-1)/2条边，称为无向完全图,.,二、无向图,6,第一节图的定义与术语,邻接点：如果(x,y)E,称x,y互为邻接点，即x,y相邻接依附：边(x,y)依附于顶点x,y相关联：边(x,y)与x,y相关联顶点的度：和顶点相关联的 边的数目，记为TD(x),.,三、有向图(Digraph),7,第一节图的定义与术语,用表示从x到y的一条弧(Arc)，且称x为弧尾，y为弧头，N=V,E，V=0,1,2,3,4，E=， ,.,三、有向图(完全图),8,第一节图的定义与术语,如果有向图有n(n-1)条边，则称为有向完全图,.,三、有向图,9,第一节图的定义与术语,邻接：如果E,称x邻接到y,或y邻接自x相关联：弧与x,y相关联入度：以顶点为头的弧的 数目，记为ID(x)出度：以顶点为尾的弧的 数目，记为OD(x)度：TD(x)=ID(x)+OD(x),.,四、路径(Path),10,第一节图的定义与术语,路径：是一个从顶点x到y的顶点序列(x, vi1, vi2, vin, y)其中，(x,vi1),(vij-1,vij),(vin,y)皆属于E,1到3有路径(1,0,4,3),1到4有路径(1,2,4),.,五、回路,11,第一节图的定义与术语,回路或环：路径的开始顶点与最后一个顶点相同，即路径中(x, vi1, vi2, vin, y)，x=y简单路径：路径的顶点序列中，顶点不重复出现,1到1构成环(1,0,4,3,1),1到3是简单路径(1,0,4,3),.,六、连通,12,第一节图的定义与术语,连通：如果顶点x到y有路径，称x和y是连通的连通图：图中所有顶点都连通,连通图,非连通图,.,七、子图,13,第一节图的定义与术语,设有两个图 G(V, E) 和 G(V, E)。若 V V 且 EE, 称图G是图G的子图,.,八、生成树,14,第一节图的定义与术语,一个连通图的生成树是一个极小连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边,.,第二节图的存储结构,图的邻接矩阵存储表示法图的邻接表表示法图的逆邻接表表示法图的十字链表表示法图的邻接多重表表示法,.,一、邻接矩阵(Adjacency Matrix),16,第二节图的存储结构,邻接矩阵：记录图中各顶点之间关系的二维数组。对于不带权的图，以1表示两顶点存在边(或弧)(相邻接)，以0表示两顶点不邻接，即 1 如果(i,j)E 或 EAij = 0 其它,.,一、邻接矩阵,17,第二节图的存储结构,无向图的邻接矩阵为：有向图的邻接矩阵为：,.,一、邻接矩阵(性质),18,第二节图的存储结构,无向图的邻接矩阵是对称的其第i行1的个数或第i列1的个数，等于顶点i的度TD(i)有向图的邻接矩阵可能是不对称的其第i行1的个数等于顶点i的出度OD(i)，第j列1的个数等于顶点j的入度ID(j),.,一、邻接矩阵(网络),19,第二节图的存储结构,有时在图的每条边上附上相关的数值，这种与图的边相关的数值叫权。 权可以表示两个顶点之间的距离、耗费等具有某种意义的数,若将图的每条边都赋上一个权，则称这种带权图为网络。 在网络中，两个顶点如果不邻接，则被视为距离为无穷大； wi,j 如果(i,j)E 或 EAij = 其它,.,一、邻接矩阵(网络),20,第二节图的存储结构,有向网N=V,E，V=0,1,2,3,4，E=, E中每个元组的第三个元素表示权。 1、画出该网, 2、写出该网的邻接矩阵。,.,一、邻接矩阵(定义),21,第二节图的存储结构,#define MAXVERTEXNUM 100 /最大顶点数typedef struct int VertexNum; /顶点数char VertexMAXVERTEXNUM;/顶点数据int AdjMatrixMAXVERTEXNUMMAXVERTEXNUM; / 邻接矩阵 Graph;Graph MGraph;,.,一、邻接矩阵(创建),22,第二节图的存储结构,#define INFINITY100/无穷大void CreateGraph(Graph *G) /生成图int i, j;cin G-VertexNum;/输入图的顶点数for (i=1; iVertexNum; i+)cin G-Vertexi; /输入顶点信息for (i=1; iVertexNum; i+) for (j=1; jVertexNum; j+) cin G-AdjMatrixij; /依次输入邻接矩阵 if (G-AdjMatrixij = -1) G-AdjMatrixij = INFINITY; ,.,二、邻接表(Adjacency List),23,第二节图的存储结构,邻接表是图的一种链式存储结构在邻接表中，每个顶点设置一个单链表，其每个结点都是依附于该顶点的边（或以该顶点为尾的弧）,.,二、邻接表(结点结构),24,第二节图的存储结构,边(弧)的结点结构 adjvex; / 该边(弧)所指向的顶点的位置 nextarc;/ 指向下一条边(弧)指针 info; / 该边(弧)相关信息的指针或权值顶点的结点结构 data; / 顶点信息 firstarc;/指向第一条依附该顶点的边(弧),.,typedef struct VexNode / 定义图的顶点 char Vertex;/ 顶点int Weight;/ 边（弧）的权值struct VexNode *NextArc;/ 指向下一条边(弧)指针 VexNode;,第二节图的存储结构,二、邻接表(结点结构),.,二、邻接表(无向图),26,第二节图的存储结构,.,二、邻接表(有向图),27,第二节图的存储结构,.,二、邻接表(网络),28,第二节图的存储结构,.,二、邻接表(定义),29,第二节图的存储结构,typedef struct / 定义图（采用邻接链表）int VertexNum;/ 顶点数VexNode *AdjList;/ 邻接表头指针 Graph;Graph MGraph;,.,二、邻接表(创建),30,第二节图的存储结构,void CreateGraph(Graph *G)/ 创建图（邻接表）int i, ArcNum;char x, y;cin G-VertexNum;/ 输入顶点数G-AdjList=new VexNodeG-VertexNum+1; / 申请n个头结点for (i=1; iVertexNum; i+) cin G-AdjListi.Vertex;/ 输入顶点信息（字符）G-AdjListi.NextArc=NULL; / 头顶点下一条边指针为空 cin ArcNum; / 输入边（弧）数for (i=1; i x; / 输入顶点1（或弧尾）cin y; / 输入顶点2（或弧头）InsertLinkList(G, x, y); / 在x单链表中，插入y结点InsertLinkList(G, y, x); / 插入x结点（无向图）,.,二、邻接表(创建插入结点),31,第二节图的存储结构,void InsertLinkList(Graph *G, char x, char y)int j;VexNode *p, *q;j = GetVexNodeNo(G, x); / 找到顶点x对应的单链表头结点q = new VexNode;/ 申请一个新结点q-Vertex = y;/ 边的另一个顶点（弧头）为yq-NextArc = NULL;if (G-AdjListj.NextArc=NULL)|(G-AdjListj.NextArc-Vertexy)q-NextArc = G-AdjListj.NextArc; / 插入结点G-AdjListj.NextArc = q;else p = G-AdjListj.NextArc;while(p-NextArc),.,二、邻接表(创建顶点对应的序号),32,第二节图的存储结构,int GetVexNodeNo(Graph *G, char c) / 找到字符对应的单链表序号 int j; for (j=1; jVertexNum; j+) if (G-AdjListj.Vertex = c) break; return(j);,.,二、邻接表(性质),33,第二节图的存储结构,有向图邻接表: 顶点的出度-第i个链表中结点的个数； 顶点的入度-必须遍历整个邻接表也可以建立一个逆邻接表要判定两个顶点i和j是否有边（或弧），必须搜索整个第i个和第j个链表，不及邻接矩阵方便,.,二、邻接表(有向图的逆邻接表),34,第二节图的存储结构,逆邻接表中，弧的箭头向内(入弧),.,三、十字链表(Orthogonal List),35,第二节图的存储结构,十字链表是有向图的另一种存储结构十字链表是将有向图的邻接表和逆邻接表结合起来的一种存储结构,.,三、十字链表(结点结构),36,第二节图的存储结构,弧的结点结构 tailvex;/ 弧尾顶点的位置 headvex;/ 弧头顶点的位置 tlink; / 指向弧尾相同的下一条弧 hlink; / 指向弧头相同的下一条弧 info; / 该弧相关信息的指针或权值,.,三、十字链表(结点结构),37,第二节图的存储结构,顶点的结点结构data; / 与顶点相关的信息firstin; / 指向以顶点为弧头的第一个弧结点firstout;/ 指向以顶点为弧尾的第一个弧结点,.,三、十字链表(举例),38,第二节图的存储结构,.,四、邻接多重表(Adjacency Multilist),39,第二节图的存储结构,邻接多重表是无向图的另一种存储结构在无向图中，一条边要用2个结点表示(分别从2个顶点的角度看)在邻接多重表中，一条边只用一个结点表示将所有具有某顶点的结点，全部用链连结起来，链所在的域为该顶点对应的指针域,.,四、邻接多重表(结点结构),40,第二节图的存储结构,边的结点结构 mark; / 标记域，如指示该边是否被搜索过 ivex,jvex;/ 该边所依附的两个顶点的位置 ilink;/ 指向下一条依附于ivex的边 jlink;/ 指向下一条依附于jvex的边 info; / 该边相关信息的指针或权值,.,四、邻接多重表(举例),41,第二节图的存储结构,.,一、图的遍历,42,第三节图的遍历,从图的某一顶点开始，访遍图中其余顶点，且使每一个顶点仅被访问一次图的遍历主要应用于无向图,.,二、深度优先搜索(DFS),43,第三节图的遍历,图的深度优先搜索是树的先根遍历的推广图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组 visited ,.,二、深度优先搜索(DFS算法),第三节图的遍历,所有顶点访问标志visited设置为FALSE从某顶点v0开始，设v=v01.如果visitedv=FALSE，则访问该顶点，且设visitedv=TRUE2.如果找到当前顶点的一个新的相邻顶点w,设v=w,重复13.否则(说明当前顶点的所有相邻顶点都已被访问过，或者当前顶点没有相邻顶点)，如果当前顶点是v0，退出；否则返回上一级顶点，重复2,.,二、深度优先搜索(举例),45,第三节图的遍历,采用以下链表存储结构时，DFS次序为0,1,2,3,4,5,visit,.,二、深度优先搜索(举例),46,第三节图的遍历,DFS次序1:V1,V2,V4,V8,V5,V3,V6,V7DFS次序2:V1,V2,V5,V8,V4,V3,V6,V7,由于没有规定访问邻接点的顺序，深度优先序列不唯一,.,第三节图的遍历,当采用邻接表存储结构并且存储结构已确定的情况下，遍历的结果是确定的。,c0,c1,c3,c2,c4,c5,DFS序列：c0 c1 c3 c4 c5 c2,.,三、广度优先搜索(BFS),48,第三节图的遍历,广度优先搜索(BFS)是一种分层搜索方法BFS每向前走一步可能访问一批顶点, 不存在往回退的情况BFS不是一个递归的过程。,.,三、广度优先搜索(BFS算法),49,第三节图的遍历,所有顶点访问标志visited设置为FALSE从某顶点v0开始，访问v0，visitedv0=TRUE，将v0插入队列Q1.如果队列Q不空，则从队列Q头上取出一个顶点v,否则结束2.依次找到顶点v的所有相邻顶点v，如果visitedv=FALSE，访问该顶点v，visitedv=TRUE，将v插入队列Q3.重复1,2,.,三、广度优先搜索(BFS函数),50,第三节图的遍历,void BFSTraverse(Graph *G, char FirstVertex)int i, j; char y, VisitedMAXVERTEXNUM;VexNode *p;for (i=1; iVertexNum; i+) Visitedi = F;/ 所有结点对应的访问位 赋初值InitQueue(GQ); / 清空循环队列i = GetVexNodeNo(G, FirstVertex);Visitedi = T;cout AdjListi.Vertex;EnQueue(GQ, G-AdjListi.Vertex); / 新搜索到的结点插入队列while (QueueEmpty(GQ) != ERROR) DeQueue(GQ, ,.,三、广度优先搜索(举例),第三节图的遍历,BFS为0,1,4,5,2,3 BFS为v1,v2,v3,v4, v5,v6,v7,v8,.,算法分析 DFS遍历：实质是对每个顶点查找邻接点的过程，取决于存储结构。当图有e条边，其时间复杂度为O(e)，图的每个顶点至多调用一次DFS函数（递归过程）。 总时间复杂度为O(n+e) 。 BFS遍历： 与DFS遍历唯一区别是邻接点搜索次序不同. 总时间复杂度为O(n+e) 。,第三节图的遍历,.,练 习,例按顺序输入顶点对：(1,2),(1,6),(2,6),(1,4),(6,4),(1,3),(3,4),(6,5),(4,5),(1,5),(3,5)， 根据建立无向图的邻接表算法,画出相应的邻接表。并写出在该邻接表上，从顶点4开始搜索所得的深度优先遍历序列和广度优先遍历序列。,.,一、无向图的连通性,54,第四节图的连通性问题,如果无向图中，存在不连通的顶点，则该图称为非连通图 非连通图 连通图,.,二、无向图的连通分量,55,第四节图的连通性问题,非连通图的极大连通子图叫做连通分量若从无向图的每一个连通分量中的一个顶点出发进行DFS或BFS遍历，可求得无向图的所有连通分量的生成树(DFS或BFS生成树)所有连通分量的生成树组成了非连通图的生成森林,.,二、无向图的生成树,56,第四节图的连通性问题,由DFS遍历，求得连通分量称为DFS生成树由BFS遍历，求得连通分量称为BFS生成树,BFS生成树,DFS生成树,.,三、最小生成树,57,第四节图的连通性问题,如果无向图中，边上有权值，则称该无向图为无向网如果无向网中的每个顶点都相通，称为连通网最小生成树(Minimum Cost Spanning Tree)是代价最小的连通网的生成树，即该生成树上的边的权值和最小,.,三、最小生成树(准则),58,第四节图的连通性问题,必须使用且仅使用连通网中的n-1条边来联结网络中的n个顶点；不能使用产生回路的边；各边上的权值的总和达到最小。,.,四、普里姆(Prim)算法生成最小生成树,59,第四节图的连通性问题,假设N=(V,E)是连通网TE是N上最小生成树中边的集合1.U=u0，(u0V), TE=2.在所有uU,vV-U的边(u,v)E中找一条代价最小的边(u,v0)并入集合TE，同时v0并入U3.重复2，直到U=V,.,四、普里姆(Prim)算法举例,60,第四节图的连通性问题,原图 (a) (b),(c) (d) (e) (f),.,P174页，图7.16,.,算法7.9,void MiniSpanTree_PRIM(MGraph G, VertexType u) / 用普里姆算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边,记录从顶点集U到VU的代价最小的边的辅助数组定义 struct VertexType adjvex; VRType lowcost; closedgeMAX_VERTEX_NUM; int i,j,k; k = LocateVex ( G, u ); for ( j=0; j0, viV-U printf(closedgek.adjvex, G.vexsk); / 输出生成树的边 closedgek.lowcost = 0; / 第k顶点并入U集 for (j=0; jG.vexnum; +j) if (G.arcskj.adj Vertexi = StartVexChar) StartVex = i; break;for (i=1; iVertexNum; i+) Pathi0 = 0; / 顺序表的0位置，存放顺序表(路径)的长度 Desti = INFINITY;/ 所有顶点到开始顶点之间的距离初值设为无穷大 if (G-AdjMatrixStartVexi AdjMatrixStartVexi; Pathi1 = G-VertexStartVex; Pathi2 = G-Vertexi; Pathi0 = 2; Finali = F;,76,.,三、Dijkstra算法代码,第五节最短路径,DestStartVex = 0; / 初始化，开始顶点属于S集（已处理过的结点）FinalStartVex = T;for (i=1; iVertexNum; i+) MinDest = INFINITY; for (j=1; jVertexNum; j+) / 找未处理顶点中到开始顶点最近的顶点 if (Finalj = F) if (Destj VertexNum; j+) / 更新当前最短路径及距离 if(Finalj=F) ,77,.,一、有向无环图(DAG),第六节有向无环图及其应用,有向无环图(DAG:Directed Acycline Graph)是图中无环的有向图,DAG,非DAG,78,.,一、有向无环图(DAG),第六节有向无环图及其应用,有向图中，可以用深度优先搜索(DFS)，找出是否存在环从某个顶点v出发，进行DFS，如果存在一条从顶点u到v的回边，则有向图中存在环DFS: 0,1,2,4,3,非DAG,.,二、拓扑排序,第六节有向无环图及其应用,1.偏序若集合X上的关系R是：.自反的：x R x.反对称的：x R y = y R x.传递的：xRy & yRz = xRz 则称R是集合X上的偏序关系,.,二、拓扑排序,第六节有向无环图及其应用,2.全序设关系R是集合X上的偏序，如果对每个x,yX，必有xRy或者yRx，则称R是X上的全序关系偏序指集合中仅有部分成员之间可比较全序指集合中全体成员之间均可比较,81,.,二、拓扑排序,第六节有向无环图及其应用,3.拓扑有序右图是一个偏序关系，因为1,3没有先后关系如果人为地增加1,3先后关系，如1先于3，则右图变为全序， 称为拓扑有序,.,二、拓扑排序,第六节有向无环图及其应用,4.拓扑排序由偏序定义得到的拓扑有序的操作称拓扑排序算法：.在有向图中选一个没有前驱的顶点且输出之.从图中删除该顶点和所有以它为尾的弧 重复两步，直到所有顶点输出为止,83,.,第六节有向无环图及其应用,算法7.12:Status ToplogicalSort(ALGraph G) /ToplogicalSort() functionFindInDegree(G,indegree); /Find indegree of node0.vexnum-1InitStack(S);for(i=0;inextarc) k=p-adjvex; if(!(-indegreek) Push(S,k);/end of for/end of whileif (countG.vexnum) return (ERROR);else return (OK);/end of ToptlogicalSort() function,.,二、拓扑排序(举例),第六节有向无环图及其应用,原图,输出0之后,输出0,1之后,输出0,1,3之后,4,最后输出拓扑排序结果：0,1,3,2,4,输出0,1,3,2之后,.,三、AOV-网,第六节有向无环图及其应用,如果用有向图的顶点表示活动，用弧表示活动间的优先关系，则称该有向图为顶点表示活动的网AOV(Activity On Vertex Network)AOV一定是DAG，即图中不存在环，因为存在环意味着某项活动应以自己为先决条件,86,.,三、AOV-网(举例),第六节有向无环图及其应用,课程代号 课程名称 先修课程C1 高等数学C2 程序设计基础C3 离散数学 C1, C2 C4 数据结构 C3, C2C5 高级语言程序设计 C2C6 编译方法 C5, C4C7 操作系统 C4, C9C8 普通物理 C1C9 计算机原理 C8拓扑排序结果为 C1 , C2 , C3 , C4 , C5 , C6, C8 , C9 , C7或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6,87,.,四、AOE-网,第六节有向无环图及其应用,如果用有向图的顶点表示事件，用弧表示活动，则称该有向图为边表示活动的网AOE(Activity On Edge)AOE同样是DAGAOE包括估算工程的完成时间,.,五、关键路径,第六节有向无环图及其应用,求工程的完成时间是AOE的一个应用在工程问题中，需要研究的问题有：.完成整个工程至少需要多少时间？.哪些活动是影响工程进度的关键？,89,.,五、关键路径,第六节有向无环图及其应用,1.关键路径工程问题的AOE网中，从工程开始(顶点)到工程结束(顶点)之间路径长度最长的路径叫关键路径提前完成关键路径上的活动，工程进度会加快提前完成非关键路径上的活动，对工程无帮助,90,.,五、关键路径,第六节有向无环图及其应用,2.关键活动关键路径上的所有活动称为关键活动找到工程AOE中的所有关键活动，即找到了关键路径,91,.,五、关键路径,第六节有向无环图及其应用,3.关键活动有关的量e(i)：活动ai最早开始时间l(i)：活动ai最迟开始时间l(i)-e(i)：活动ai开始时间余量如果l(i)=e(i)，则称活动ai为关键活动,92,.,五、关键路径,第六节有向无环图及其应用,3.关键活动有关的量ve(j)：事件vj最早开始时间vl(j)：事件vj最迟开始时间e(i)=ve(j)l(j)=vl(k)-dut() dut()为活动ai的持续时间,93,.,五、关键路径,第六节有向无环图及其应用,3.关键活动有关的量从ve(0)=0开始向前递推 ve(j)=Maxve(i)+dut() T，T是所有以第j个顶点为头的弧的集合从vl(n-1)=ve(n-1)起向后递推 vl(i)=Minvl(j)-dut() S，S是所有以第i个顶点为尾的弧的集合,94,.,五、关键路径,第六节有向无环图及其应用,4.求关键活动算法从始点v0出发，令ve0=0，按拓扑有序求vej从终点vn-1出发，令vln-1=ven-1，按逆拓扑有序求vli根据各顶点的ve和vl值，求每条弧(活动)ai的最早开始时间eai和最迟开始时间lai如果eai=lai，则ai为关键活动,95,.,五、关键路径(举例),第六节有向无环图及其应用,ve(j)=Maxve(i)+dut() vl(i)=Minvl(j)-dut()e(i)=ve(j) l(j)=vl(k)-dut()拓扑有序0,1,3,2,4,
展开阅读全文