71 图的定义和基本术语 71 图的定义和基本术语.ppt

第七章图 7 1图的定义和基本术语7 2图的存储结构7 2 1数组表示法7 2 2邻接表7 2 3十字链表7 2 4邻接多重表7 3图的遍历7 3 1深度优先搜索7 3 2广度优先搜索7 4图的连通性问题7 4 1无向图的连通分量和生成树7 4 2最小生成树7 5有向无环图及其应用7 5 1拓扑排序7 5 2关键路径7 6最短路径7 6 1从某个源点到其余各顶点的最短路径7 6 2每一对顶点间的最短路径 图 Graph 是较线性表和树更为复杂的结构 图中任意数据两个元素之间都可能相关 第七章图 G1 V1 A1 V1 v1 v2 v3 v4 A1 G2 V2 E2 V2 v1 v2 v3 v4 v5 E2 v1 v2 v1 v4 v2 v3 v2 v5 v3 v4 v3 v5 7 1图的定义和基本术语 顶点弧弧尾弧头 顶点边 7 1图的定义和基本术语 续一 完全图 n个顶点有n n 1 2条边的无向图有向完全图 n个顶点有n n 1 条弧的有向图稀疏图 有很少条边的图 如边数e nlogn 稠密图 非稀疏图权 与边或弧相关的数网络 带权的图 2 7 4 子图 G V E 和G1 V1 E1 若V1属于V E1属于E则G1是G的子图 7 1图的定义和基本术语 续二 邻接点 无向图中有边相连的两个顶点互为邻接点顶点的度 无向图中和某顶点相连的邻接点数入度 有向图中指向某顶点的弧的数目出度 有向图中从某顶点出发的弧的数目 7 1图的定义和基本术语 续三 路径 两个顶点之间的顶点序列 该序列的每个顶点与其前驱是邻接点 每个顶点与其后继也是邻接点回路 环 第一顶点和最后顶点相同的路径简单路径 顶点不重复的路径连通 两个顶点之间有路径连通图 任意两个顶点之间有路径连通分量 无向图中的极大连通子图 强连通图 任意两个顶点之间有双向路径强连通分量 有向图中的极大强连通子图 连通图的生成树 极小连通子图 不唯一 但n个顶点的生成树有且仅有n 1条边 生成森林 7 2图的存储结构7 2 1数组表示法 defineINFINITYINT MAX defineMAX VERTEX NUM20typedefenum DG DN AG AN GraphKind typedefstructArcCell VRTypeadj InfoType info ArcCell AdjMatrix MAX VERTEX NUM MAX VERTEX NUM typedefstruct VetexTypevexs MAX VERTEX NUM AdjMatrixarc intvexnum arcnum GraphKindkind MGraph 数组表示法 邻接矩阵 无向图 有向图 网均适用易求各顶点的度 例如有向图G1和无向图G2的邻接矩阵为 n2的存储量无向图的邻接矩阵总是对称的 可以采用压缩存储 网及其邻接矩阵 7 2 2邻接表 链式存储结构 defineMAX VERTEX NUM20typedefstructArcNode intadjvex structArcNode nextarc InfoType info ArcNode typedefstruct AdjListverteces intvexnum arcnum intkind ALGraph typedefstructVNode VetexTypedata ArcNode firstarc Vnode AdjList MAX VERTEX NUM 邻接表的链式存储结构示意图 G1的邻接表 G2的邻接表 G1的逆邻接表 邻接表 求出度容易 求入度难 邻接表 求入度容易 求出度难 7 3图的遍历 图的遍历 从图的某顶点出发 访问所有顶点 且每个顶点仅被访问一次 两种遍历图的路径 深度优先搜索和广度优先搜索它们对无向图和有向图都适用深度优先搜索类似于树的先根遍历广度优先搜索类似于树的层次遍历 7 3 1深度优先搜索 V1 遍历顺序 非连通的图重复上述过程 使每个顶点均被访问 V1 V2 stack V4 V8 V5 深度优先搜索算法 Booleanvisited MAX Status VisitFunc intv voidDFSTraverse GraphG Status visit intv VisitFunc visit for v 0 v G vexnum v visited v FALSE for v 0 v G vexnum v if visited v DFS G v voidDFS GraphG intv visited v TRUE VisitFunc v for w FirstAdjVex G v w w NextAdjVex G v w if visited w DFS G w 7 3 2广度优先搜索 12345678 遍历顺序 非连通的图重复上述过程 使每个顶点均被访问 voidBFSTraverse GraphG Status visit intv for v 0 v G vexnum v visited v FALSE IntiQueque Q for v 0 v G vexnum v if visited v EnQueue Q v while QueueEmpty Q DeQueue u visited u TRUE Visit u for w FirstAdjVex G u w w NextAdjVex G u w if visited w visited w TRUE visited w EnQueue G w 广度优先搜索算法 7 4图的连通性问题 7 4 1无向图的连通分量和生成树 7 4 3最小生成树 连通网的生成树一棵生成树的代价 树上