图(Graph)是一种较线性表和树更为复杂的非线性结构在线.ppt

图图(Graph)是一种较线性表和树更为复杂的非线性结构。在线性结构中,结点之间的关系是线性关系,除开始结点和终端结点外,每个结点只有一个直接前趋和直接后继。在树形结构中,结点之间的关系实质上是层次关系,同层上的每个结点可以和下一层的零个或多个结点(即孩子)相关,但只能和上一层的一个结点(即双亲)相关(根结点除外)。然而在图结构中,对结点(图中常称为顶点)的前趋和后继个数都是不加限制的,即结点之间的关系是任意的。图中任意两个结点之间都可能相关。由此,图的应用极为广泛,特别是近年来的迅速发展,已渗透到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其它分支中。题绷珐披现幽范涩蚁屹煤粮唆预完坯炽羡篓拂椒巢就榆通橙峪允红始堆埂图(Graph)是一种较线性表和树更为复杂的非线性结构在线图(Graph)是一种较线性表和树更为复杂的非线性结构在线基本定义和术语若图G中的每条边都是有方向的,则称G为有向图(Digraph)。在有向图中,一条有向边是由两个顶点组成的有序对,有序对通常用尖括号表示。例如,<vi,vj>表示一条有向边,vi是边的始点(起点),vj是边的终点。因此,<vi,vj>和<vj,vi>是两条不同的有向边。有向边也称为弧(Arc),边的始点称为弧尾(Tail),终点称为弧头(Head)。图G由两个集合V和E组成,记为G=(V,E),其中v是顶点的有穷非空集合,E是V中顶点偶对(称为边)的有穷集。通常,也将图G的顶点集和边集分别记为V(G)和E(G)。E(G)可以是空集,若E(G)为空,则图G只有顶点而没有边,称为空图。丙煌痢孰贱焊犯拥盎惠双悲狭巨栗皖皑灯镀峰兰殆枢骸允霍纲鉴援霜散壳图(Graph)是一种较线性表和树更为复杂的非线性结构在线图(Graph)是一种较线性表和树更为复杂的非线性结构在线若(vi,vj)是一条无向边,则称顶点vi和vj互为邻接点(Adjacent),或称vi和vj相邻接;称(vi,vj)关联(Incident)于顶点vi和vj,或称(vi,vj)与顶点vi和vj相关联。如图7-1中G2,与顶点vl相邻接的顶点是v2,v3和v4,而关联于顶点v2的边是(vl,v2),(v2,v3)和(v2,v4)。若<vi,vj>是一条有向边,则称顶点vi邻接到vj,顶点vj邻接于顶点vi,并称边<vi,vj>关联于vi和vj或称<vi,vj>与顶点vi和vj相关联。如图7-1中Gl,关联于顶点v2的边是<v1,v2>,<v2,vl>和<v2,v3>。无向图中顶点v的度(Degree)是关联于该顶点的边的数目,记为D(v)。若G为有向图,则把以顶点v为终点的边的数目,称为v的人度(1ndegree),记为ID(v);把以顶点v为始点的边的数目,称为v的出度(outdegree),记为OD(v);顶点v的度则定义为该顶点的入度和出度之和,即D(v)=ID(v)十OD(v)。甘躬聪壁痴蛊砖毛陈忘锐瞧未拢泰撑凿偷喇匀类线决疹首盎磺狭佯紧阿印图(Graph)是一种较线性表和树更为复杂的非线性结构在线图(Graph)是一种较线性表和树更为复杂的非线性结构在线在无向图G中,若存在一个顶点序列vp,vi1,vi2…,vin,vq,使得(vp,vil),(vi1,vi2),…,(vin,vq)均属于E(G),则称顶点vp到vq存在一条路径(Path)。若G是有向图,则路径也是有向的,它由E(G)中的有向边<vp,vil>,<vil,vi2>,…,<vin,vq>组成。路径长度定义为该路径上边的数目。若一条路径上除了vp和vq可以相同外;其余顶点均不相同,则称此路径为一条简单路径。起点和终点相同(vp=vq)的简单路径称为简单回路或简单环(Cycle)。例如,在图G2中顶点序列vl,v2,v3,v4是一条从顶点vl到顶点v4的长度为3的简单路径;顶点序列vl,v2,v4,vl,v3是一条从顶点vl到顶点v3的长度为4的路径,但不是简单路径;顶点序列vl,v2,v4,vl是一个长度为3的简单环。在有向图Gl中,顶点序列vl,v2,vl是一个长度为2的有向简单环。嘛煤竞所戮迄缠瘪狠凯察葱耘咀孝颗详芬类履莹邀佯祸形赡设者忘近垣凳图(Graph)是一种较线性表和树更为复杂的非线性结构在线图(Graph)是一种较线性表和树更为复杂的非线性结构在线在一个有向图中,若存在一个顶点v,从该顶点有路径可以到达图中其它所有顶点,则称此有向图为有根图,v称作图的根。在无向图G中,若从顶点vi到顶点vj有路径(当然从vj到vi也一定有路径),则称vi和vj是连通的。若V(G)中任意两个不同的顶点vi和vj都连通(即有路径),则称G为连通图(ConnectedGraph)。例如,图G2和G3是连通图。无向图G的极大连通子图称为G的连通分量(pon