第七章 图5 4.pptVIP

7 图 主要内容 图的定义和术语 图的存储结构 邻接矩阵、邻接表、十字链表、多重邻接表 图的遍历 深度优先、广度优先 图的连通性问题 连通分量、生成树、最小生成树 有向无环图的应用 拓扑排序、关键路径 最短路径问题 Dijkstra算法、Floyd算法 图定义 图是由顶点集合V(Vertex)及顶点间的关系集合E组成的一种数据结构：G = ( V,E ) V = {Vi|Vi?某个数据对象}，是顶点的有穷非空集合 E是顶点之间的关系(边)的集合，边用(vi,vj)或vi,vj来表示 邻接点 对于无向图G={V,{E}}，若边(v,v’)?E，则称v和v’互为邻接点 称边(v,v’)依附于顶点v和v’ 或者说边(v,v’)和顶点v,v’相关联 顶点的度 顶点v的度TD(V)=和v相关联的边的数目 入度和出度 对于有向图G={V,{A}}： v的入度ID(v) = 以顶点v为头的弧的数目 v的出度OD(v) = 以顶点v为尾的弧的数目 有向图中，顶点的度 = 入度 + 出度 一个有n个顶点，e条边的图满足下列等式： 即边(或弧)的总数 = 各个顶点的度的总数的一半 若有n个顶点的无向图有 条边，则此图为完全无向图 路径 在无向图中，若从顶点v出发，沿一些边经过一些顶点vi,0,vi,1,...,vi,m，到达顶点v’。则称顶点序列(v,vi,0,vi,1,...,vi,m,v’)为从顶点v 到顶点v’的路径，其中(vi,j-1,vi,j)?E 如果G是有向图，则路径也是有向的 路径的长度 路径上的边或弧的数目 回路(环) 第一个顶点和最后一个顶点相同的路径 简单路径 序列中顶点不重复出现的路径(即不含回路的路径) 简单回路 除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路 连通图 在无向图G中，如果从顶点v到顶点v’有路径，则称v和v’是连通的 如果对于图中的任意两个顶点vi和vj都是连通的，则称G是连通图 是否连通是对无向图来说的 网络的邻接矩阵 wi,j, ifi,j∈E or(i,j)∈E A[i][j]= ∞, otherwise 邻接矩阵的类型定义 无向图的邻接表 核心思想:对具有n个顶点的图建立n个线性链表存储该图 邻接表的类型定义 有向图的邻接表和逆邻接表 网络的邻接表 邻接表的操作(计算某个顶点的度、出度、入度) 无向图:链表中表结点的个数即某顶点的度 有向图： 邻接表：链表中表结点的个数即某个顶点的出度 逆邻接表：链接中表结点的个数即某顶点的入度 判断任意两个顶点(Vi,Vj)是否有边或弧 需要有哪些信誉好的足球投注网站第i个或第j个链表 找出某个顶点的所有邻接顶点 只需找到表示这个顶点的头结点 邻接表 无向图每一条边(vi,vj)有两个结点，浪费空间，操作不方便 多重邻接表 每一条边只用一个结点表示 本节小结 4种存储结构 能够手工完成：图 -- 存储结构 重点是邻接矩阵和邻接表 思考题2 自己随手画一个图，试着画出这个图的2种存储结构 深度优先遍历——仿树的前序遍历过程 访问顶点v 依次从v的每一个未被访问的邻接点出发进行深度优先遍历 若此时图中尚有顶点未被访问，则任选其一为起点 重复，直至图中所有顶点都被访问到 练习 写出对下图进行深度优先遍历的结果 void DFSTranverse(Graph G) { //初始时将所有顶点都设置为未访问 for(v = 0; v n; v++) visited[v] = false; //从每一个顶点出发 for(v = 0; v n; v++) //没访问过就开始遍历 if(!visited[v]) DFS(v); } void DFS(int v) { visited[v] = true; //将点v设为已访问 VisitFunc(v); //调用访问函数 //依次对v的每一个邻接点，调用DFS函数 for(w = 0; w n; w++) if(!visited[w]) DFS(w); } 广度优先遍历——仿树的层次遍历过程 访问顶点v 依次访问顶点v的各个未被访问的邻接点 分别从这些邻接点出发，依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于”后被访问的顶点的邻接点”被访问 若此时图中尚有顶点未被访问，则任选其一为起点，重复，直至图中所有顶点都被访问到 注意对比树的层序遍历 练习 写出对下图进行广度优先遍历的结果(从A出发) 练习 写出对下图(从A出发)进行深度优先遍历和广度优先遍历的结果 算法 对比二叉树的层序遍历算法 在遍历的过程中需要辅助数组，vis