石油大学软件技术基础 ch32图课件.ppt

《石油大学软件技术基础 ch32图课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、3.2图3.2.1图的基本概念3.2.2图的存储结构3.2.3图的遍历3.2.4生成树和最小生成树3.2.5小结13.2.1图的基本概念图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)其中：V(G)是顶点的非空有限集E(G)是边的有限集合，边是顶点的无序对或有序对23.2.1图的基本概念有向图——有向图G是由两个集合V(G)和E(G)组成的其中：V(G)是顶点的非空有限集E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为，v,w是顶点，v为弧尾，w为弧头245136有向

2、图G1图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>}33.2.1图的基本概念无向图——无向图G是由两个集合V(G)和E(G)组成的其中：V(G)是顶点的非空有限集E(G)是边的有限集合，边是顶点的无序对，记为（v,w）或（w,v)，并且（v,w)=(w,v)无向图G21573246图G2中：V(G2)={1,2,3,4,5,6,7}E(G2)={(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,

3、7)}4有向完备图——任意两个顶点之间都有方向相反的两条弧相连接，n个顶点的有向图最大边数是n(n-1)无向完备图——任意两个顶点都有一条直接边相连接，n个顶点的无向图最大边数是n(n-1)/2213213有向完备图无向完备图当一个图接近完备图时，则称该图为稠密图；相反地，当一个图含有较少的边数时，则称该图为稀疏图。5无向图中，对于任意两个顶点vi和顶点vj，若存在边(vi，vj)，则称顶点vi和顶点vj互为邻接点，同时称边(vi，vj)依附于顶点vi和顶点vjV1V2V3V4V5V1的邻接点：V2、V4V2的邻接点：V

4、1、V3、V5邻接、依附6有向图中，对于任意两个顶点vi和顶点vj，若存在弧，则称顶点vi邻接到顶点vj，顶点vj邻接自顶点vi，同时称弧依附于顶点vi和顶点vj。V1V2V3V4V1的邻接点：V2、V3V3的邻接点：V4邻接、依附71452375318642网图权——在一个图中，每条边可以标上具有某种含义的数值，此数值称为该边上的权，通常权是一个非负实数。权可以表示从一个结点到另一个结点的距离、花费的代价或时间等含义。网图（网络）：边上标有权的图称为网，也称为带权图（weightedgrap

5、h）。8子图——如果图G(V,E)和图G‘(V’,E‘)，满足：V’VE’E则称G‘为G的子图356245136图与子图9顶点的度无向图中，顶点的度TD(Vi)为与Vi顶点相连的边数有向图中，顶点的度分成入度ID(V)与出度OD(V)入度ID(V)：以该顶点为头的弧的数目出度OD(V)：以该顶点为尾的弧的数目例245136G1顶点2入度ID(2)=1出度OD(2)=3顶点4入度ID(4)=1出度OD(4)=0例157324G26顶点5的度TD(5)=3顶点2的度TD(2)=4TD(2)=ID(2)+OD(2)=1+3

6、=410顶点的度无向图中，顶点的度TD(Vi)为与Vi顶点相连的边数有向图中，顶点的度分成入度ID(V)与出度OD(V)入度ID(V)：以该顶点为头的弧的数目出度OD(V)：以该顶点为尾的弧的数目对于具有n个顶点、e条边的图，顶点v的度TD(v)与顶点的个数以及边的数目满足关系：(书139页有错，请改正）TD(vi))/2n∑i=1e=(11路径——顶点vp到顶点vq之间的路径（path）是指顶点序列vp,vi1,vi2,…,vim,vq.。其中，（vp,vi1），(vi1,vi2)，…,(vim,.vq)分别为图中的边

7、。路径长度——沿路径边的数目或沿路径各边权值之和回路——第一个顶点和最后一个顶点相同的路径叫~简单路径——序列中顶点不重复出现的路径叫~简单回路——除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫~G1245136路径：1，2，3，5，6，3路径长度：5简单路径：1，2，3，5回路：1，2，3，5，6，3，1简单回路：3，5，6，312连通——从顶点V到顶点W有一条路径，则说V和W是连通的连通图——图中任意两个顶点都是连通的叫~连通图24513613连通分量——非连通无向图的极大连通子图称为~V1V2V3V4V

8、5V6V7V1V2V3V4V5V6V7非连通图G非连通图G的两个连通分量14强连通图——有向图中，如果对每一对Vi，VjV,且ViVj，从Vi到Vj和从Vj到Vi都存在路径，则称G是~强连通分量——非连通有向图中的极大强连通子图称为该有向图的~强连通图356536241536非连通图G非连通图G的强连通分量15生