图-数据结构与算法.pptVIP

6.1 图的基本概念 6.2 图的存储结构 6.3 图的遍历 6.4 无向图的应用 6.5 有向图的应用 6.6 最短路径 6.1 图的基本概念 图定义 图是由顶点集合(V)及顶点间的关系集合E所组成的一种数据结构： Graph＝ V, E 其中 V = { x | x ? 某个数据对象} 是顶点的非空有限集合； E = {(x, y) | x, y ? V } //边(Edge)集合 或 E = {x, y | x, y ? V } //弧(Arc)集合 是顶点之间关系的有限集合. 6.2 图的存储结构 在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表，还有一个表示各个顶点之间关系的邻接矩阵。 设图 G = (V, E)是一个有 n 个顶点的图，则G的邻接矩阵是如下定义的N*N的矩阵AG={A[i][j]}n*n： A[i][j]= 无向图的邻接矩阵是对称的，有向图的邻接矩阵不一定对称的。 6.2 图的存储结构 在无向图中, 第 i 行 (列) 1 的个数即为顶点i 的度。 在有向图中, 第 i 行 1 的个数即为顶点 i 的出度，第 j 列1 的个数即为顶点 j 的入度。 带权图的邻接矩阵 6.2.2 邻接表 (Adjacency List)表示法 图的操作在邻接表的上的实现 int FirstAdjVex(int v){ return ghead[v]-firstout.adjvex； } // FirstAdjVex int NextAdjVex(int v，int w) { p=ghead[v]-firstout； while (p p-adjVex!=w) p=p-link； if (!p || !p-link) return 0； else return p-link-adjVex； } // NextAdjVex 6.2.3 邻接多重表表示法 邻接多重表是只用来存储无向图的另一种存储结构 . 在邻接多重表表示法中每一条边只对应一个边结点(EdgeNode)，在边结点中，每一条边对应的边结点有五个域： EdgeNode: 邻接多重表类型说明如下： class EdgeNode{ // 边结点 Tag mark； //访问标记 int vex1,vex2； // 该边所指向的顶点的序号 EdgeNode *link1，*link2； // 指向下一条边的指针 public: EdgeNode(int adj) ; }; // EdgeNode 6.2.4 十字链表 十字链表是只用来存储有向图的另一种存储结构。可以把十字链表看成是将有向图的邻接表和逆邻接表结合起来而得到的一种链表 有向图中每一条弧对应于一个弧结点（ArcNode），每个顶点也对应于一个顶点结点（Vnode）。在弧结点中，每一条弧对应的弧结点有五个域。 弧结点： 十字链表类型说明如下： class ArcNode { // 弧结点 Tag mark； //访问标记 int hvex,tvex; //与该弧所关联的两个顶点的序号 ArcNode *hlink,*tlink； // 分别指向与该弧所关联的两个顶点的下一条弧 public: ArcNode(int adj); };// ArcNode 6.3 图的遍历 从图中某一顶点出发，按照某种有哪些信誉好的足球投注网站路径访问图中所有的顶点，使得每个顶点被访问一次且仅被访问一次，就叫做图的遍历。 深度优先遍历DFS ( Depth First Search ) 图的深度优先遍历算法如下: void DFSTraverse( ){ //深度优先求图的连通分量 int visited[n]； //设置访问标志数组 for (v=0；vn；v++) visited[v]=0； //初始化访问标志数组 for (v=0；vn；v++) if (!visited[v]) DFS(G，v)； //每次从尚未