吉林大学数据结构课件 第五章 图

第五章图图（Graph）是一种较线性表和树更为复杂的非线性结构。在图结构中，对结点（图中常称为顶点）的前趋和后继个数都是不加限制的，即结点之间的关系是任意的。图中任意两个结点之间都可能相关。图状结构可以描述各种复杂的数据对象。图的应用极为广泛，特别是近年来的迅速发展，已渗透到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其它分支中。图状结构的实际背景在城市之间建立通讯网络，使得其中的任意两个城市之间有直接或间接的通讯线路，假设已知每对城市之间通讯线路的造价，要求找出一个造价最低的通讯网络。城市航线网天津北京上海广州深圳计算机网络computerconnection不一定具有一个根结点没有明显的父子关系从一个顶点到另一个可能有多个（或0个）路径图VS.树概念和定义定义：图G由两个集合V和E组成，记为G=(V,E)；其中V是顶点的有穷非空集合，E是连接V中两个不同顶点的边的有穷集合。通常，也将图G的顶点集和边集分别记为V(G)和E(G)。若图中的边限定为从一个顶点指向另一个顶点，则称此图为有向图。若图中的边无方向性，则称之为无向图。无向图G=(V,E)V={V1,V2,V3,V4,V5}E={(V1,V4),(V1,V2),(V2,V3),(V2,V5),(V3,V4),(V3,V5)}V1V4V3V2V5有向图G=（V，E）V={v1，v2，v3，v4}E={v1,v2,v1,v3,v3,v4，v4,v1}v1v3v2v4在一个无向图中，若存在一条边(w,v)，则称w,v为此边的两个端点，它们是相邻的，并称它们互为邻接顶点。在一个有向图中，若存在一条边w,v,则称顶点w邻接到顶点v，顶点v邻接自顶点w.v1v3v2v4oooov1v2v3v4子图有两个图G和H，若V(H)V(G)，E(H)E(G)，则称H是G的子图，G是H的母图。如果H是G的子图，并且V(H)＝V(G)，则称H是G的支撑子图。V5V1V2V3V4V1V1V2V5V2V3……V5V1V2V3V4V4V3V2V1V1V2V1V4V3V2V1V4V3V1……度无向图中，顶点的度是以该顶点为端点的边的个数。有向图中，以某顶点为弧头的弧的数目称为该顶点的入度。以某顶点为弧尾的弧的数目称为该顶点的出度。该顶点的度=入度+出度。度:TD(v)入度:ID(v)出度:OD(v)TD(v)=ID(v)+OD(v)Graph2V5V1V2V3V4V4V3V2V1Graph1设图G(可以为有向或无向图)共有n个顶点，e条边，若顶点vi的度数为TD(vi)，则102niiTDve因为一条边关联两个顶点，而且使得这两个顶点的度数分别增加1。因此顶点的度数之和就是边的两倍。路径和回路：设G是图，若存在一个顶点序列vp，v1，v2，…，vq，使得vp,v1，v1,v2，…，vq-1,vq或(vp,v1)，(v1,v2)，…，(vq-1,vq)属于E(G)，则称vp到vq存在一条路径。路径的长度是该路径上的边的个数（非权图）。如果一条路径上没有相同的顶点，则称此路径为简单路径。如果一条简单路径除了起点和终点相同外，没有相同的顶点，且路径长度大于等于2，则称之为简单回路。V5V4V2V1V3V1V2V3V4路径：v1v3v4v3v5简单路径：v1v3v5简单回路：v1v2v3v1路径：v1v3v2v4v3v2简单路径：v1v3v2简单回路：v1v3v2v1可及和连通图若从顶点vi到顶点vj有路径，则称vi与vj可及(连通的）。若G为无向图，且V(G)中任意两顶点都可及，则称G为连通图。若G为有向图，且对于V(G)中任意两个不同的顶点vi和vj，vi与vj可及，vj与vi也可及，则称G为强连通图。V5V4V2V1V3V1V2V3V4连通分量连通分量设G=(V,E)是非（强）连通图，若G的子图Gk是一个（强）连通图，则称Gk为G的连通分量。最大连通分量对于G的一个连通分量Gk，如果不存在G的另一个连通分量G’，使得V(Gk)⊂V(G’)，则称Gk为G的最大连通分量。连通分量ALCFDEIGHJKMBDEIGHKALCFJMB强连通分量V4V3V1V2V4V3V2V1Graph1权图设G=(V,E)是图，若将图中的每条边l都赋上一个实数w(l)作为边的权值，则称G为权图。并规定：∀u∈V,有w((u,u))=0或w(u,u)=0∀u,v∈V,若(u,v)∉E(G)或u,v∉E(G)则w((u,v))=＋∞或w(u,v)=＋∞权通常用来表示从一个顶点到另一个顶点的距离或费用。V1V2V3V42357无向图有向图端点弧弧头弧尾相邻的邻接到邻接自度出度入度连通图强连通图,单连通图邻接矩阵邻接表(逆邻接表)十字链表多重邻接表图的存储结构用顺序方式或链接方式存储图的顶点表v0,v1,…vn-1,图的边用n×n阶矩阵A=(aij)表示，A的定义如下：（a）若图为权图，aij对应边vi,vj的权值；（b）若图为非权图，则（1）aii=0；（2）aij=1，当i≠j且vi,vj或(vi,vj)存在时；（3）aij=0，当i≠j且vi,vj或(vi,vj)不存在时。称矩阵A为图的邻接矩阵。邻接矩阵无向图的邻接矩阵有向图的邻接矩阵[例1]无向图的邻接矩阵无向图的邻接矩阵是对称阵。012301111001100111100123V0V3V2V1[例2]有向图的邻接矩阵V0V3V4V1V201234010001000101010100000001001234[例3]权图的邻接矩阵0123035830∞45∞0284200123V0V3V2V135284特点：–无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2–有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n²借助邻接矩阵,可以很容易地求出图中顶点的度。–无向图邻接矩阵的第i行（或第i列）的非零元素的个数是顶点Vi的度。–有向图邻接矩阵第i行的非零元素的个数为顶点Vi的出度；第i列的非零元素的个数为顶点Vi的入度。Graph1V4V3V2V1Graph2V5V1V2V3V401100000000110000101010101010111010001100邻接表定义:邻接表是图的一种链式存储结构。对图的每个顶点建立一个单链表（n个顶点建立n个单链表），第i个单链表中的结点包含顶点Vi的所有邻接顶点。由顺序存储的顶点表和链接存储的边链表构成的图的存储结构被称为邻接表。权图中边结点结构为（VerAdj,cost,link）.非权图中边结点结构为（VerAdj,link）顶点的结构非权图的邻接表权图的邻接表VerAdjcostlinkVerNameadjacent[例1]无向图的邻接表。V0V3V2V1V0V1V2V30231123∧012∧03∧03∧[例2]有向图的邻接表。V0V1V2V3V4024311∧3∧0∧0∧4∧1∧3∧V0V3V4V1V2[例3]有向图的逆邻接表。V0V3V4V1V2V0V1V2V3V4024311∧0∧2∧2∧4∧1∧3∧∧[例4]带权图的邻接表V0V3V2V135284V0V1V2V30231133∧825082∧214053∧2033∧4有向图的十字链表表示法弧结点：tailvex,headvex;弧尾、弧头在表头数组中位置hlink；指向弧头相同的下一条弧tlink;指向弧尾相同的下一条弧tailvexheadvexhlinktlink顶点结点：data;存与顶点有关信息firstin；指向以该顶点为弧头的第一个弧结点firstout;指向以该顶点为弧尾的第一个弧结点datafirstinfirstout例bdacabcd123413123431434241^^^^^^^^从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历(GraphTraversal)。图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组visited[]，它的初始状态为0，在图的遍历过程中，一旦某一个顶点i被访问，就立即让visited[i]为1，防止它被多次访问。图的遍历5.3.1深度优先遍历●深度优先遍历又被称为深度优先搜索DFS(DepthFirstSearch)●基本思想:DFS在访问图中某一起始顶点v后，由v出发，访问它的任一邻接顶点w1；再从w1出发，访问与w1邻接但还没有访问过的顶点w2；然后再从w2出发，进行类似的访问，…如此进行下去，直至到达所有的邻接顶点都被访问过的顶点u为止。接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。深度优先搜索DFS(DepthFirstSearch)深度优先搜索的示例1递归算法算法DepthFirstSearch(v,visited)/*图的深度优先递归遍历算法*/DFSearch1[初始化]PRINT(v).visited[v]⟵1.p⟵adjacent(Head[v]).DFSearch2[深度优先遍历图]WHILEp≠∧DO(IFvisited[VerAdj(p)]≠1THENDepthFirstSearch(VerAdj(p),visited).p⟵link(p).)▐DFSearch1[初始化]PRINT(v).visited[v]⟵1.p⟵adjacent(Head[v]).DFSearch2[深度优先遍历图]WHILEp≠∧DO(IFvisited[VerAdj(p)]≠1THENDepthFirstSearch(VerAdj(p),visited).p⟵link(p).)▐深度优先遍历V1V2V4V3V8V7V6V51234051717262534V1V2V3V4V5V6V7V86001234567Fori=0ton-1DOvisited[i]⟵0.Forj=0ton-1DOIFvisited[j]=0depthFirstSearch(v[j],visited)V1V2V3算法分析图中有n个顶点，e条边。如果用邻接表表示图，沿FirstNeighbor可以找到某个顶点v的所有邻接顶点w。由于总共有2e个边结点，所以扫描边的时间为O(e)。而且对所有顶点递归访问1次，所以遍历图的时间复杂性为O(n+e)。如果用邻接矩阵表示图，则查找每一个顶点的所有的边，所需时间为O(n)，则遍历图中所有的顶点所需的时间为O(n2)。2迭代算法●基本思想:初始顶点压入堆栈；①检测堆栈是否为空。若堆栈为空，则迭代结束；否则，从栈顶弹出一个顶点v；②访问v，将visited[v]值更新为1；③求出v的邻接顶点表，将v的未被访问的邻接顶点压入栈，执行步骤①。算法DFS(Head,v0,visited.visited)/*图的深度优先非递归遍历算法*/DFS1[初始化]CREATS(S)./*创建堆栈S*/visited[v0]1.Sv0./*将v压入栈中*/DFS2[利用堆栈S深度优先遍历图]WHILENOT(ISEMTS(S))DO/*当S不空时*/(vS./*弹出堆栈顶元素*/PRINT(v).padjacent(Head[v]).WHILEpDO(IFvisited[VerAdj(p)]=0THEN(SVerAdj(p).visited[VerAdj(p)]1.)plink(p)))▐A0243156BCDEFG16∧2∧34∧5∧0∧5∧4∧ACGBFED深度优先遍历（非递归）5C栈SAGFB访问过4B栈SAGF访问过AGFBC访问过E6D栈S1A栈S访问过G2B栈SA访问过F3B栈SAG访问