【数据结构(严蔚敏)】图论

《【数据结构(严蔚敏)】图论》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1第七章图7.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为弧头无向图——无向图G是由两个集合V(G)和E(G)组成的其中：V(G)是顶点的非空有限集E(G)是边的有限集合，边是顶点的无序对，记为（v,w）或（w,v)，并且（v,w)=(w,v)

2、2例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)}3有向完全图——n个顶点的有向图，最大边数是n(n-1)无向完全图——n个顶点的无向图，最大边数是n(n-1)/2若边或弧的个数e

3、——如果图G(V,E)和图G‘(V’,E‘),满足：V’VE’E则称G‘为G的子图4假若顶点v和顶点w之间存在一条边，则称顶点v和w互为邻接点。边(v,w)和顶点v和w相关联；或边(v,w)依附于顶点v和w。顶点的度无向图中，顶点的度为与每个顶点相连的边数有向图中，顶点的度分成入度与出度入度：以该顶点为头的弧的数目出度：以该顶点为尾的弧的数目5例213213有向完全图无向完全图356例245136图与子图例245136G1顶点2入度：1出度：3顶点4入度：1出度：0例157324G26顶点5的度：3顶点2的度：46路径——路径是顶点的序列V={Vi0,

4、Vi1,……Vin}，满足(Vij-1,Vij)E或E,(1

5、，5，2，1简单回路：1，2，3，18连通——在无向图G中，如果从顶点V到顶点W有一条路径，则说V和W是连通的连通图——图中任意两个顶点都是连通的叫~连通分量——无向图中的极大连通子图叫~强连通图——有向图中，如果对每一对Vi,VjV,ViVj,从Vi到Vj和从Vj到Vi都存在路径，则称G是~9连通图例245136强连通图非连通图连通分量例245136ABECF10假设一个连通图有n个顶点和e条边，其中n-1条边和n个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。对非连通图，则称由各个连通分量的生成树的集合为此非连通图的生成森林。BAC

6、DFE117.2图的存储结构多重链表例G12413例15324G2V1V2^^V4^V3^^V1V2V4^V5^V312图的存储表示一、图的数组(邻接矩阵)存储表示二、图的邻接表存储表示三、有向图的十字链表存储表示四、无向图的邻接多重表存储表示13邻接矩阵——表示顶点间相联关系的矩阵定义：设G=(V,E)是有n1个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵例G12413例15324G214特点：无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2有向图邻接矩阵不一定对称；有n个顶点的有

7、向图需存储空间为n²无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和或第i列元素之和有向图中，顶点Vi的出度是A中第i行元素之和顶点Vi的入度是A中第i列元素之和15#defineMAX_VERTEX_NUM20//最大顶点个数typedefstructArcCell{//弧的定义VRTypeadj;//VRType是顶点关系类型。//对无权图，用1或0表示相邻否；//对带权图，则为权值类型。InfoType*info;//该弧相关信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];1

8、6Typedefenum{DG,DN,UDG,UDN}GraphK