计算机软件技术基础(邮电)1-7.ppt

《计算机软件技术基础(邮电)1-7.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计算机软件技术基础课件第一章数据结构第二章操作系统第三章软件工程第四章数据库1第一章数据结构第一单元第二单元第三单元第四单元第五单元第六单元第七单元第八单元2图的基本概念第七单元第一章数据结构31.4.1图的基本概念图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：Graph＝(V,E)其中V={x

2、x某个数据对象}是顶点的有穷非空集合；E={(x,y)

3、x,yV}或E={

4、x,yV&&Path(x,y)}是顶点之间关系的有穷集合，也叫做边(edge)集合。Path(x,y)表示从x到y的一条单向通

5、路,它是有方向的。图定义:41.4.2有向图和无向图1.有向图(DirectedGraph)在有向图中，若图G中的每条边都是有方向的，顶点对是有序的。则称G为有向图图1-59有向图G1图1-60无向图G2ABCDEABCDE5(1)有向边的表示在有向图中,一条有向边是由两个顶点组成的有序对,有序对通常用尖括号表示。弧(Arc)有向边也称为弧(Arc)，弧尾(Tail)边的始点称为弧尾(Tail)，弧头(Head)终点称为弧头(Head)。和是两条不同的有向边。ABCDE6例:

6、表示一条有向边，Vi是边的始点(起点)，Vj是边的终点。因此，和是两条不同的有向边。(2)有向图的表示：图1－57中的G1是一个有向图。该有向图G1的顶点集和边集分别为：V(G1)={A,B,C,D,E}E(G1)={,,,,,}ABCDE图1-59有向图G172.无向图(Undigraph)在无向图中，若图G中的每条边都是没有方向的，则称G为无向图。如图1－60的无向图G2。顶点对(x,y)是无序的。⑴无向边的表示：无向图中的边均是顶点的无序对

7、，无序对通常用圆括号表示。例:无序对(Vi，Vj)和(Vj，Vi)表示同一条边。ABCDE8(2)无向图的表示：例如，对于图1－58的无向图G2，其顶点集和边集分别为：V(G2)={A，B，C，D，E}E(G2)={(A，B)，(A，E)，(C，A)，(C，D)，(C，E)，(E，D)}ABCDE图1－60的无向图G2。注意：在以后的讨论中，不考虑顶点到其自身的边。即若(V1，V2)或是E(G)中的一条边，则要求V1≠V2。此外，不允许一条边在图中重复出现，即只讨论简单的图。93．图G的顶点数n和边数e的关系(1)完全

8、无向图若G是无向图，则0≤e≤n(n-1)/2。恰有n(n-1)/2条边的无向图称为完全无向图(UndirectedCompleteGraph)。例:图1－61的完全无向图G3。1234图1-61完全无向图G310(2)完全有向图若G是有向图，则0≤e≤n(n-1)。恰有n(n-1)条边的有向图称为完全有向图(DirectedCompleteGraph)。例:如图1－62的完全有向图G4。注意：完全图具有最多的边数。任意一对顶点间均有边相连。1234图1-62完全有向图114．图的边和顶点的关系(1)无向边和顶点关系：若(Vi,Vj

9、)是一条无向边,则称顶点Vi和Vj互为邻接点(Adjacent),或称Vi和Vj相邻接；并称(Vi,Vj)依附或关联(Incident)于顶点Vi和Vj,或称(Vi，Vj)与顶点Vi和Vj相关联。(2)有向边和顶点关系：若是一条有向边，则称顶点Vi邻接到Vj，顶点Vj邻接于顶点Vi；并称边关联于Vi和Vj或称与顶点Vi和Vj相关联。125．顶点的度(Degree)(1)无向图中顶点v的度(Degree)：一个顶点v的度是与它相关联的边的条数。记作TD(v)。G1１2345无向图如图G1所示

10、v3的度是3。(2)有向图顶点v的度(Degree)：在有向图中,顶点的度等于该顶点的入度与出度之和。13顶点v的入度是以v为终点的有向边的条数,记作ID(v);顶点v的出度是以v为始点的有向边的条数,记作OD(v)。例：图G2中顶点v1的入度:ID(v1)=1顶点v1的出度:OD(v1)=2度：TD(v1)=ID(v1)+OD(v1)=3有向图１234G214边与度的关系另外，若图中有n个顶点，e条边或弧，第i个顶点的度为di，则有151.4.3子图与路径1.子图设有两个图G＝(V,E)和G‘＝(V’,E‘)。若V’V且

11、E‘E,则称图G’是图G的子图16例:设V'={v1，v2，v3}，E'={(vl，v2)，(v2，v4)}，显然，V'属于V(G3)，E'属于E(G3)，但因为E'中有序偶对(v2，v4)所关联的顶点v4不在V'中，所以(V'，E