数据结构A第9章(南邮)2014课件.ppt

第9章 图;内容提要 1、图的基本概念 2、图的存储结构 包括图的邻接矩阵表示和邻接表表示法及其实现 3、图的遍历：深度优先和宽度优先遍历 4、拓扑排序 5、关键路径 6、最小代价生成树：普里姆算法 7、单源最短路径及所有顶点间的最短路径 ;9.1 图的基本概念;n1 L1 n2 C2 n3 L2 n4; 图中的结点又称为顶点(vertex)。 结点的偶对称为边(edge)，例如（1，2）； 图(graph)：是数据结构 G=(V,E)，其中V(G)是G中结点的有限非空集合；E(G)是G中边的有限集合。 ;有向图(directed graph)：指图中代表边的偶对是有序的。 用u，v代表一条有向边（又称为弧），则u称为该边的始点（尾），v称为边的终点（头）。 无向图(undirected graph)：指图中代表边的偶对是无序的 在无向图中边(u，v )和(v，u)是同一条边。;图9.2 图的例子;自回路：如果图中存在无向边(u,u)或有向边u,u， 则称这样的边为自回路。 多重图：指图中两个顶点间允许有多条相同的边。;邻接:如果(u,v)是无向图中的一条边，则称顶点u和v相邻接，并称边(u,v)与顶点u和v相关联。 例如：顶点1和2是相邻接的。;子图：图G的一个子图是图G’=(V’,E’)，其中V’(G’)?V(G), E’(G’)?E(G).;;;求无向图的连通分量应该注意： 1.图中（强）连通分量可能有多个，不能只写顶点个数最多的那个连通分量。 2. 每个（强）连通分量必须是极大的。3. 每个（强）连通分量必须写出该（强）连通分量顶点之间所有的边。;强连通图：有向图中如果任意两个顶点u和v之间，存在一条从u到v的路径，同时存在一条从v到 u的路径，则称该有向图为强连通图。 强连通分量：有向图的极大连通子图。;顶点的度：与该顶点相关联的边的数目。 入度：有向图中顶点v的入度指以v为头的弧的数目； 出度：有向图中顶点v的出度指以v为尾的弧的数目。 有向图中，顶点的度=入度+出度。 例如左图中，顶点1,2度分别为2和4。 右图中，顶点0的入度和出度分别为3和1，顶点0的度为4;生成树：无向图的生成树是一个极小连通子图，它包含图中所有顶点，但只有足以构成一棵树的(n-1)条边。再加上一条边将构成回路。;9.1.2 图的抽象数据类型;程序9.1 Graph类 template class T class Graph { public: virtual ResultCode Insert(int u,int v, T w)=0; virtual ResultCode Remove(int u,int v)=0; virtual bool Exist(int u,int v)const=0; virtual int Vertices()const {return n;} . . . protected: int n,e; // n是图中顶点数，e是边数 };对于图的操作，还有其它成员函数，将在以后陆续介绍。 主要有： 1. void DFS(); //深度优先有哪些信誉好的足球投注网站图 2. void BFS(); //宽度优先有哪些信誉好的足球投注网站图 3. void Toposort(int *order); //拓扑排序 4. void CriticalPath(); //关键路经 5. void Prim(int k,int *nearest,T *lowcost); //普里姆算法求最小代价生成树 6. void Kruskal(); //克鲁斯卡尔算法求最小代价生成树 7. void Dijkstra(int v,T *d,int *p); //迪杰斯特拉算法求单源最短路经 8. void Floyd(T **d,int **path); //弗洛伊德算法求所有顶点之间的最短路经;1 图的矩阵表示法及其实现 2 图的邻接表表示法及其实现 ; 设V={0,1,2,……,n-1}, 如果G是无向图，则A的元素定义为：;(e) 图G2的邻接矩阵;程序9.2 MGraph类 templateclass T class MGraph:public GraphT { public: MGraph(int mSize,const T noedg); ?MGraph(); ResultC