图的定义和基本术语图的定义和基本术语.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)是较线性表和树更为复杂的结构。 图中任意数据两个元素之间都可能相关。 7.1 图的定义和基本术语 7.1 图的定义和基本术语(续一) 7.1 图的定义和基本术语(续二) 7.1 图的定义和基本术语(续三) 7.2 图的存储结构 7.2.1 数组表示法 数组表示法(邻接矩阵) 无向图、有向图、网均适用易求各顶点的度。 例如有向图G1和无向图G2的邻接矩阵为 网及其邻接矩阵 7.2.2 邻接表--- 链式存储结构 邻接表的链式存储结构示意图 7.3 图的遍历 图的遍历：从图的某顶点出发，访问所有顶点，且每个顶点仅被访问一次。 两种遍历图的路径： 深度优先有哪些信誉好的足球投注网站和广度优先有哪些信誉好的足球投注网站 它们对无向图和有向图都适用 深度优先有哪些信誉好的足球投注网站类似于树的先根遍历 广度优先有哪些信誉好的足球投注网站类似于树的层次遍历 7.3.1 深度优先有哪些信誉好的足球投注网站 深度优先有哪些信誉好的足球投注网站算法 7.3.2 广度优先有哪些信誉好的足球投注网站 广度优先有哪些信誉好的足球投注网站算法 7.4 图的连通性问题 7.4.1 无向图的连通分量和生成树 7.4.3 最小生成树 连通网的生成树 一棵生成树的代价---树上各边的代价之和 最小生成树---- 一个连通网的所有生成树中代价最小的生成树 求最小生成树的Prim算法 求最小生成树的Kruskal算法 Prim算法示意图 Kruskal算法示意图 * * G1 = (V1, { A1}) V1 = {v1,v2,v3,v4} A1 = {v1,v2,v1,v3,v3,v4,v4,v1} G2 = (V2, { E2}) V2 = {v1,v2,v3,v4,v5} E2 = {(v1,v2),(v1,v4),(v2,v3),(v2,v5) ,(v3,v4),(v3,v5)} V1 V3 V4 V2 有向图 G1 V1 V4 V5 V2 无向图 G2 V3 顶点 弧 弧尾 弧头 顶点 边 完全图：n个顶点有n(n-1)/2条边的无向图 有向完全图： n个顶点有n(n-1)条弧的有向图 稀疏图：有很少条边的图（如边数e nlogn) 稠密图：非稀疏图 权： 与边或弧相关的数 网络： 带权的图 V1 V3 V2 V1 V3 V2 2 7 4 子图： G =(V,{E})和G1 = (V1,{E1}) 若V1属于V, E1属于E 则G1是G的子图 V1 V1 V3 V4 V2 V3 V1 V3 V4 V1 邻接点：无向图中有边相连的两个顶点互为邻接点 顶点的度：无向图中和某顶点相连的邻接点数 入度：有向图中指向某顶点的弧的数目 出度：有向图中从某顶点出发的弧的数目 路径：两个顶点之间的顶点序列，该序列的每个顶点与其前驱是邻接点，每个顶点与其后继也是邻接点 回路（环）：第一顶点和最后顶点相同的路径 简单路径： 顶点不重复的路径 连通： 两个顶点之间有路径 连通图： 任意两个顶点之间有路径 连通分量： 无向图中的极大连通子图。 强连通图：任意两个顶点之间有双向路径 强连通分量：有向图中的极大强连通子图。 连通图的生成树：极小连通子图。 不唯一，但n个顶点的生成树 有且仅有n-1条边。 生成森林： #define INFINITY INT_MAX #define MAX_VERTEX_NUM 20 typedef enum{DG, DN, AG, AN} GraphKind; typedef struct ArcCell{ VRType adj; InfoType *info; }ArcCell, AdjMatrix[MAX_VERTEX_NUM ][MAX_VERTEX_NUM ] typedef struct { VetexType vexs[MAX_VER