数据结构与算法分析第六章图1

第六章图6.1图的概念6.1.1图的定义•图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)其中：V(G)是顶点的非空有限集E(G)是边的有限集合，边是顶点的无序对或有序对•有向图——有向图G是由两个集合V(G)和E(G)组成的其中：V(G)是顶点的非空有限集E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为v,w，v,w是顶点，v为弧尾，w为弧头•无向图——无向图G是由两个集合V(G)和E(G)组成的其中：V(G)是顶点的非空有限集E(G)是边的有限集合，边是顶点的无序对，记为（v,w）或（w,v)，并且（v,w)=(w,v)例245136G1图G1中：V(G1)={1,2,3,4,5,6}E(G1)={1,2,2,1,2,3,2,4,3,5,5,6,6,3}例157324G26图G2中：V(G2)={1,2,3,4,5,6,7}E(G1)={(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)}6.1.2图的基本术语•有向完全图——n个顶点的有向图最大边数是n(n-1)•无向完全图——n个顶点的无向图最大边数是n(n-1)/2•权——与图的边或弧相关的数叫权•网——带权的图叫网•子图——如果图G(V,E)和图G’(V’,E’),满足：V’⊆VE’⊆E称G’为G的子图•顶点的度–无向图中，顶点的度为与每个顶点相连的边数–有向图中，顶点的度分成入度与出度»入度：以该顶点为头的弧的数目»出度：以该顶点为尾的弧的数目例213213有向完全图无向完全图356例245136图与子图例245136G1顶点2入度：1出度：3顶点4入度：1出度：0例157324G26顶点5的度：3顶点2的度：4•路径——路径是顶点的序列V={Vi0,Vi1,……Vin}，满足(Vij-1,Vij)∈E或Vij-1,Vij∈E,(1j≤n)•路径长度——沿路径边的数目或沿路径各边权值之和•回路——第一个顶点和最后一个顶点相同的路径•简单路径——序列中顶点不重复出现的路径•简单回路——除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路例157324G26例245136G1路径：1，2，3，5，6，3路径长度：5简单路径：1，2，3，5回路：1，2，3，5，6，3，1简单回路：3，5，6，3路径：1，2，5，7，6，5，2，3路径长度：7简单路径：1，2，5，7，6回路：1，2，5，7，6，5，2，1简单回路：1，2，3，1连通——从顶点V到顶点W有一条路径，则说V和W是连通的连通图——图中任意两个顶点都是连通连通分量——非连通图的每一个连通部分强连通图——有向图中，如果对每一对Vi,Vj∈V,Vi≠Vj,从Vi到Vj和从Vj到Vi都存在路径，则称G是强连通图~连通图例245136强连通图356例非连通图连通分量例2451366.1.2图的抽象数据类型•6.2图的存储结构(1)邻接矩阵(2)邻接表(3)十字链表(4)邻接多重表6.2.1邻接矩阵——表示顶点间相联关系的矩阵1。定义：设G=(V,E)是有n≥1个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵⎪⎩⎪⎨⎧∈=，其它0E(G)v,v或)v,(v若1,],[jijijiA例G12413例15324G2⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎣⎡0011000101110101010101010fedcgcdefg⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡0001100000000110cdeffedc2。特点：™无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2™有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n²™无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和™有向图中，•顶点Vi的出度是A中第i行元素之和•顶点Vi的入度是A中第i列元素之和例G12413⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡0001100000000110cdeffedc3。网的邻接矩阵网络的邻接矩阵可定义为：v5v1v6v2v4v35489573156∞5∞7∞∞∞∞4∞∞∞8∞∞∞∞9∞∞5∞∞6∞∞∞5∞∞3∞∞∞1∞v2v3v1v4v5v1v2v3v4v5v6v6⎪⎩⎪⎨⎧∈=，其它0E(G)v,v或)v,(v若,],[jijiijjiAω∞6.2.2邻接表•实现：为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧）顶点序号//邻接点域，存放与Vi邻接的点在表头数组中的位置指针//链域，指示下一条边或弧顶点序号指针顶点序号权值指针例G1bdac例aecbdG21234acdbdatafirst3241^^^^destvtxnext1234acdbdatafirst4212^^^destvtxxnext5e435^15323^•特点–无向图中顶点Vi的度为第i个单链表中的结点数–有向图中»顶点Vi的出度为第i个单链表中的结点个数»顶点Vi的入度为整个单链表中邻接点域值是i的结点个数–逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表例G1bdac1234acdbdatafirstc41^1^^3^destvtxnext™十字链表有向图的表示法弧结点：typedefstructarcnode{inttailvex,headvex;//弧尾、弧头在表头数组中位置structarcnode*hlink；//指向弧头相同的下一条弧structarcnode*tlink;//指向弧尾相同的下一条弧}AD;tailvexheadvexhlinktlink顶点结点：typedefstructdnode{intdata;//存与顶点有关信息structarcnode*firstin；//指向以该顶点为弧头的第一个弧结点structarcnode*firstout;//指向以该顶点为弧尾的第一个弧结点}DD;DDg[M];//g[0]不用datafirstinfirstout例bdacabcd123413123431434241^^^^^^^^™邻接多重表无向图的表示法顶点结点：data;//存与顶点有关的信息*firstedge;//指向第一条依附于该顶点的边a[M];datafirstedge边结点：info;//标志域ivex,jvex;//该边依附的两个顶点在表头数组中位置*ilink,*jlink;//分别指向依附于ivex和jvex的下一条边infoivexilinkjvexjlink例aecbd1234acdb5e121434323552^^^^^⎪⎩⎪⎨⎧∈=，其它0E(G)v,v或)v,(v若1,],[jijijiA例G12413例15324G2⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎣⎡0011000101110101010101010fedcgcdefg⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡0001100000000110cdeffedc6.2.5图的实现u邻接矩阵邻接矩阵ureturn-1；}例G1bdac例aecbdG21234acdbdatafirst3241^^^^destvtxnext1234acdbdatafirst4212^^^destvtxxnext5e435^15323^u邻接表邻接表u顶点序号权值指针§6.3图的遍历从图中某个顶点出发，沿路径使图中从图中某个顶点出发，沿路径使图中每个顶点每个顶点被被访问且仅被访问一次访问且仅被访问一次的过程，称为的过程，称为遍历图遍历图。。两种常用遍历图的方法两种常用遍历图的方法深度优先搜索深度优先搜索广度优先搜索广度优先搜索1.深度优先搜索（深度优先搜索（depthdepth--firstfirst--search)search)~(stack)¾¾访问指定的某顶点访问指定的某顶点VV，将，将VV作为当前顶点作为当前顶点¾¾访问当前顶点的下一未被访问过的邻接点，并以该访问当前顶点的下一未被访问过的邻接点，并以该邻接点作为当前顶点邻接点作为当前顶点¾¾重复重复22，直到所有和当前顶点有路径相通的顶点都被，直到所有和当前顶点有路径相通的顶点都被访问到访问到¾¾沿搜索路径回退，退到尚有邻接点未被访问过的某沿搜索路径回退，退到尚有邻接点未被访问过的某结点结点¾¾将该结点作为当前结点，重复以上步骤，直到所有将该结点作为当前结点，重复以上步骤，直到所有顶点被访问过的为止顶点被访问过的为止0123456dfs(0)visited[1..n]visited[1..n]是一个辅助数组，是一个辅助数组，记载顶点是否被访问记载顶点是否被访问过过visited[vi]=true,已访问过false,未访问过（初值）深度优先搜索算法深度优先搜索算法11--------邻接矩阵邻接矩阵visited[1..n]visited[1..n]是一个辅助数组，是一个辅助数组，记载顶点是否被访问记载顶点是否被访问过过visited[vi]=true,已访问过false,未访问过（初值）深度优先搜索算法深度优先搜索算法22--------邻接表邻接表2.广度优先搜索（广度优先搜索（breadth-firsttraversal))~(queue)¾¾首先访问指定顶点首先访问指定顶点vv00，将，将vv00作作为当前顶点为当前顶点¾¾访问当前顶点的所有未访问过访问当前顶点的所有未访问过的邻接点，并的邻接点，并¾¾依次将访问的这些邻接点作依次将访问的这些邻接点作为当前顶点为当前顶点¾¾重复重复22，，直到所有顶点被访问直到所有顶点被访问为止为止0123456bfs(0)2.广度优先搜索广度优先搜索算法6.3.3无向图的连通分量