资源描述：
《《数据结构A》第09章》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据结构DataStructuresinC++第9章图9.1图的基本概念9.2图的存储结构9.3图的遍历9.4拓朴排序9.5关键路径9.6最小代价生成树9.7单源最短路径9.8所有顶点之间的最短路径9.1图的基本概念9.1.1 图的定义与术语图是数据结构G=（V，E）。结点的偶对称为边，图中的结点常称为顶点。若代表一条边的偶对是有序的，则称其为有向图。用〈u,v〉代表有向图中的一条有向边，u称为边的始点，v称为边的终点。有向边也称弧。若图中代表一条边的偶对是无序的，则称其为无向图。用（u,v）代表无向图中的边。V(G1)=V(G2)={0,1,2,3,4},E(G1)={(0,1),(0
2、,2).(0,4),(1,2),(2,3),(2,4),(3,4）}E(G2)={<0,1>,<1,2>,<2,0>,<2,4>,<3,0>,<3,2>,<3,4>}如果边(u,u)或是允许的，这样的边称为自回路。两顶点间允许有多条相同边的图，称为多重图。如果一个图有最多的边数，称为完全图。无向完全图有n(n-1)/2条边；有向完全图有n(n-1)条边。若（u,v）是无向图的一条边，则称顶点u和v相邻接；若〈u,v〉是有向图的一条边，则称顶点u邻接到(adjacentto)顶点v,顶点v邻接自(adjacentfrom)u，并称边（u,v）或〈u,v〉与顶点u和v相关联。图G的一
3、个子图是一个图G’=（V’,E’），使得V’(G’)V(G),E’(G’)E(G)。在无向图G中，一条从s到t的路径是一个顶点的序列：（s,v1,v2,…,vk,t），使得(s,v1),(v1,v2),…,(vk,t)是图G的边。若图G是有向图，则该路径使得,…,是图G的边。路径上边的数目称为路径长度。如果一条路径上的所有顶点，除起始顶点和终止顶点可以相同外，其余顶点各不相同，则称其为简单路径。一个回路是一条简单路径，其起始顶点和终止顶点相同。一个无向图中，若两个顶点u和v之间存在一条从u到v的路径，则称u和v是连通的。若图中任意一对顶点都是连通的
4、，则称此图是连通图。一个有向图中，若任意一对顶点u和v间存在一条从u到v的路径和一条从v到u的路径，则称此图是强连通图。无向图的一个极大连通子图称为该图的一个连通分量。有向图的一个极大强连通子图称为该图的一个强连通分量。图中一个顶点的度是与该顶点相关联的边的数目。有向图的顶点v的入度是以v为头的边的数目，顶点v的出度是以v为尾的边的数目。一个无向连通图的生成树是一个极小连通子图，它包括图中全部顶点，但只有足以构成一棵树的n-1条边。一棵自由树是不包含回路的连通图。有根有向树是一个有向图，它恰有一个顶点入度为0，其余顶点的入度为1，并且如果略去此图中边的方向，处理成无向图后，图是连通的。不包
5、含回路的有向图称为有向无环图。有向图的生成森林是这样的一个子图，它由若干棵互不相交的有根有向树组成，这些树包含了图中全部顶点。在图的每条边上加上一个数字作权也称代价，带权的图称为网。9.1.2图ADTADTGraph{数据：顶点的非空集合V和边的集合E，每条边由V中顶点的偶对表示。运算：Create()：构造一个不包含任何边的有向图。Destroy()：撤消一个有向图。Exist(u,v)：如果图中存在边，则函数返回true，否则返回false。Insert(u,v,w)：向图中添加权为w的边，若插入成功，则函数返回Success；若图中已存在边，则
6、函数返回Duplicate；其它情况函数返回Failure。Remove(u,v)：从图中删除边，若图中不存在边，则函数返回NotPresent；若图中存在边，则从图中删除此边，函数返回Success；其它情况函数返回Failure。Vertices()：函数返回图中顶点数目。}其它图运算（1）深度优先搜索图voidDFS()（2）宽度优先搜索图voidBFS()（3）拓扑排序voidTopoSort(int*order)（4）关键路径voidCriticalPath()（5）普里姆算法求最小代价生成树voidPrim(int*nearest,T*lowcos
7、t)（6）克鲁斯卡尔算法求最小代价生成树voidKruskal()（7）迪杰斯特拉算法求单源最短路径voidDijkstra(intv,T*d,int*path)（8）弗洛伊德算法求所有顶点之间的最短路径voidFloyd(T**d,int**path)templateclassGraph{public:virtualResultCodeInsert(intu,intv,T&w)=0;virtualRes
