数据结构第9章图

图的基本概念图的存储表示图的遍历图的应用图的基本概念图(Graph)图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：Graph＝(V,E)其中:V={x|x某个数据对象}是顶点的有穷非空集合；E={(x,y)|x,yV}或E={x,y|x,yV}是顶点之间关系的有穷集合。125634abcd无向图有向图V={1,2,3,4,5,6}E={(1,2),(1,5),(1,6),(2,3),(2,4),(3,4),(4,5),(4,6)}（边）V={a,b,c,d}E={a,b,a,d,b,d,c,a,d,a,d,b,d,c}（弧）弧尾顶点，弧头顶点ADTGraph{数据对象:D={ai|1in,n0,ai属Elemtype类型数据关系:R1={ai,aj|ai,ajD,1in,1jn,每个元素可以有多个直接前驱和可以有多个直接后继}基本运算:InitGraph(t);ClearGraph(t);DSF(t);BSF(t);}抽象数据类型数的定义完全图若有n个顶点的无向图有n(n-1)/2条边,则此图为完全无向图。有n个顶点的有向图有n(n-1)条边,则此图为完全有向图。abc1234邻接顶点如果(u,v)是E(G)中的一条边，则称u与v互为邻接顶点。例：存在(1,2)，则顶点1与2互为邻接点。存在a,b,则顶点a与b互为邻接点。125634abcd顶点的度一个顶点v的度是与它相关联的边的条数。记作TD(v)。在有向图中,顶点的度=入度+出度。顶点v的入度是以v为终点的有向边的条数,记作ID(v);顶点v的出度是以v为始点的有向边的条数,记作OD(v)。TD(v)=ID(v)+OD(v)例：TD(1)=3TD(4)=4TD(5)=2例：TD(b)=ID(b)+OD(b)TD(d)=ID(d)+OD(d)=2+1=3=2+3=5子图设有两个图G＝(V,E)和G‘＝(V’,E‘)。若V’V且E‘E,则称图G’是图G的子图。0123子图0130123023权某些图的边具有与它相关的数,称为权。这种带权图叫做网络。任意图都是其自身子图abcd819341123路径在图G＝(V,E)中,若从顶点vi出发,沿一些边经过一些顶点vp1,vp2,…,vpm，到达顶点vj。则称顶点序列(vivp1vp2...vpmvj)为从顶点vi到顶点vj的路径。125634例：V1到V3的路径：123、123423、16423、1544……..路径长度非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和。简单路径若路径上各顶点v1,v2,...,vm均不互相重复,则称这样的路径为简单路径。回路若路径上第一个顶点v1与最后一个顶点vm重合,则称这样的路径为回路或环。路径长度：2、5、4、3……..连通图与连通分量在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图。非连通图的极大连通子图叫做连通分量。生成树一个连通图的生成树是其极小连通子图。n个顶点、n-1条边、连通子图。12563441532连通图非连通图两个连通分量125634125634强连通图与强连通分量在有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。abcdabcd强连通图非强连通图cabd两个强连通分量图的存储表示邻接矩阵(AdjacencyMatrix)),(,否则或若01EjiEjiaij=abefcdvexs123456abcdefA=010011101100010100011011100100100100利用数组vertex[]存储顶点基本思想：利用矩阵A表示顶点之间的关系无向图的邻接矩阵是对称矩阵),(,否则或若EjiEjiWijaij=A=abcd819341123vexs1234A=abcd1111111000000000A=abefcdvexs123456abcdef482196731084931112341984198262633107107A=010011101100010100011011100100100100邻接矩阵所占存储空间与顶点数成正比但图中有无关系都分配存储空间边的插入和删除不影响存储空间大小0100？求顶点的度邻接矩阵的数据类型A=vexs1234typedefstruct{intno;InfoTypeinfo;}VertexTtypetypedefstruct{intedges[MAXV][MAXV];/*各顶点之间的关系或权值*/intn,e;/*顶点数，边（或弧）的个数*/VertexTypevexs[MAXV];/*存储顶点元素*/}MGraph;建立邻接矩阵*邻接矩阵初始化（置0或）*输入顶点数，弧数ga-nga-e*输入各顶点信息存入ga-vexs[]*输入各边信息（或权值）存入ga-edages[][]A=vexs1234邻接表(AdjacencyList)基本思想：在无向图中，将依附于某个顶点的所有边（边结点）以单链表形式链接，每个链表设立一个表头结点。abefcd123456abcdef(a,b)(a,e)(a,f)256(b,a)(b,c)(b,d)134(c,b)(c,d)24(d,b)(d,c)(d,e)(d,f)2356(e,a)(e,d)(f,a)(f,d)1414datafirstarc4821967310481987426adjvexinfonextarc36107231910adjvexnextarc注：在无向图中每个边生成两个结点？插入和删除(d,f)=(f,d)?求顶点的度datafirstarc1234abcd859371113邻接表：在有向图中，将以该顶点作为弧尾顶点的所有弧链接成单链表。abcda,ba,d2847b,d49c,a13d,ad,bd,c15211313datafirstarc1234abcdc,ad,a3345a,bd,bd,c413a,db,d184111749逆邻接表逆邻接表：在有向图中，将以该顶点作为弧头顶点的所有弧链接成单链表。？求顶点的度邻接表的结点结构和数据类型datafirstarc表头结点typedefstructANode{intadjvex;/*邻接点存储序号*/InfoTypeinfo;/*若是网络存储权值*/structANode*nextarc;/*指向下一个边结点*/}ArcNode;typedefstruct{Vertexdata;/*存储顶点元素*/ArcNode*firstarc;/*指向依附于该顶点的第一边*/}VNode;typedefVNodeAdjList[MAXV];typedefstruct{AdjListadjlist;intn,e;}ALGraph;adjvexnextarc边结点adjvexinfonextarcdatafirstarcadjvexinfonextarc123456abcdef256134242356141448198742636107231910abefcd4821967310建立邻接表*邻接表初始化（置各单链表为空表ga[].firstarc=NULL）*输入各顶点信息存入ga[].data*输入各边信息，生成新结点，插入相应的单链中。abcd859371113datafirstarc1234abcd2847491315211313邻接表的基本操作插入：b,c*确定单链表*生成新结点636*头插链表注：有向图只插入(或删除）一个结点，而无向图需插入（或删除）两个结点。删除：d,c*确定结点*删除结点*释放结点c,a十字链表(有向图)abcd859371113aaabacada12a,ba14a,da24b,da31c,aa41d,aa42d,ba43d,ctailvexheadvexhlinktlinkinfo弧结点datafirstinfirstout顶点结点datafirstinfirstout顶点结点tailvexheadvexhlinktlinkinfo弧结点typedefstructArcNode{inttailvex,headvex;structArcNode*hlink,*tlink;InfoTypeinfo;}ArcNode;typedefstructVexNode{VertexTypedata;ArcNode*firstin,*firstout;}VexNode;十字链表的数据类型a46(d,f)abefcd4821967310ABCDEFa12(a,b)a15(a,e)a16(a,f)a23(b,c)a24(b,d)a34(c,d)a45(d,e)邻接多重表（无向图）markivexilinkjvexjlink边结点datafirstedge顶点结点datafirstedge顶点结点markivexilinkjvexjlink边结点typedefstructENode{intmark;intivex,jvex;structENode*ilink,*jlink;InfoTypeinfo;}ENode;邻接多重表的数据类型typedefstructVNode{VertexTypedata;ENode*firstedge;}VNode;图的遍历(GraphTraversal)图的遍历从图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次。为了避免重复访问，设置一个的辅助数组visited[]标志各顶点是否被访问过。图的遍历的分类：深度优先搜索DFS(DepthFirstSearch)广度优先搜索BFS(BreadthFirstSearch)12563478深度优先搜索DFS(DepthFirstSearch)visited12345678DFS基本思想：*访问顶点v0。*依次从v0未被访问的邻接点出发进行深度优先搜索遍历。遍历序列：1231256414521426264545262653178177383883733780000000011111111注：访问v0的邻接点与访问v0方法一样，用递归方式实现。12563478DFS(v0)的主要步骤：(1)访问顶点v0(2)确定第一邻接点w(3)若w未访问，则从w出发进行遍历DFS(w)(4)确定下一个邻接点w(5)重复(3)(4)直到所有邻接点都处理结束DFS(v0)的主要步骤：(1)访问顶点v0(2)确定第一邻接点w(3)若w未访问，则从w出发进行遍历DFS(w)(4)确定下一个邻接点w(5)重复(3)(4)直到所有邻接点都处理结束深度优先搜索DFS(DepthFirstSearch)DFS(v0){visite(v0);visited[v0]=1;w=FIRST(v0);while(存在w){if(visited[v0]==0)DFS(w);w=NEXT(v0,w);}}125634datafirstarc123456abcdef5623142435624114DFS(v0){visite(v0);visited[v0]=1;w=FIRST(v0);while(存在w){if(visited[v0]==0)DFS(w);w=NEXT(v0,w);}}第一邻接点:p=G-adjlist[v].firstarc下一个邻接点：p=p-nextarc广度优先搜索BFS(BreadthFirstSearch)12563478BFS基本思想：