资源描述：
《数据结构课件非常详细 ch7.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
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)例24
2、5136G1图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)}有向完全图——n个顶点的有向图最大边数是n(n-1)无向完全图——n个顶点的无向图最大边数是n(n-1)/2权——与图的边或弧相关的数叫~网——带权的图叫~子图——如果图G(V,E)和图G‘(V’,E‘),满足：V’VE’E则称G‘为
3、G的子图邻接点——对于无向图G(V,E),如果边(v,v’)E,则称v和v’互为邻接点。即：v和v’相邻接。依附——边(v,v’)依附于顶点v和v’。相关联——边(v,v’)和顶点v和v’相关联。顶点的度无向图中，顶点的度为与每个顶点相连的边数有向图中，顶点的度分成入度与出度入度：以该顶点为头的弧的数目出度：以该顶点为尾的弧的数目如果顶点vi的度记为TD(vi)，则有n个顶点，e条边或弧的图，满足：路径——路径是顶点的序列V={Vi0,Vi1,……Vin}，满足(Vij-1,Vij)E或E,(14、沿路径各边权值之和回路/环——第一个顶点和最后一个顶点相同的路径叫~简单路径——序列中顶点不重复出现的路径叫~简单回路/简单环——除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫~连通——在无向图中，从顶点V到顶点W有一条路径，则说V和W是连通的连通图——图中任意两个顶点都是连通的叫~连通分量——非连通图的每一个连通部分叫~强连通图——有向图中，如果对每一对（Vi,Vj）V,ViVj,从Vi到Vj和从Vj到Vi都存在路径，则称G是~强连通分量——有向图中的极大强连通子图叫~生成树——一个连通图的生成树是一个极小连通子图，它含有图中的全部顶点，但只
5、有足以构成一棵树的n-1条边例213213有向完全图无向完全图356例245136图与子图例245136G1顶点2入度：1出度：3顶点4入度：1出度：0例157324G26顶点5的度：3顶点2的度：4例157324G26例245136G1路径：1，2，3，5，6，3路径长度：5简单路径：1，2，3，5回路：1，2，3，5，6，3，1简单回路：3，5，6，3路径：1，2，5，7，6，5，2，3路径长度：7简单路径：1，2，5，7，6回路：1，2，5，7，6，5，2，1简单回路：1，2，3，1连通图例245136强连通图356例非连通图例2451367.2图的存储
6、结构多重链表例G12413例15324G2V1V2^^V4^V3^^V1V2V4^V5^V3邻接矩阵——表示顶点间相联关系的矩阵定义：设G=(V,E)是有n1个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵例G12413例15324G2特点：无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n²无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和有向图中，顶点Vi的出度是A中第i行元素之和顶点Vi的入度是A中第i列元素之和网络的
7、邻接矩阵可定义为：例1452375318642关联矩阵——表示顶点与边的关联关系的矩阵定义：设G=(V,E)是有n1个顶点，e0条边的图，G的关联矩阵A是具有以下性质的ne阶矩阵4321例G124131234例15324G2123456432156例BDAC123456ABCD432156特点关联矩阵每列只有两个非零元素，是稀疏矩阵；n越大，零元素比率越大无向图中顶点Vi的度TD(Vi)是关联矩阵A中第i行元素之和有向图中，顶点Vi的出度是A中第i行中“1”的个数顶点Vi的入度是A中第i行中“-1”的个数邻接表实现：
8、为图中每个顶点建立一个单链表，第i个单
