图论初步讲义(编辑修改稿)

图论初步讲义(编辑修改稿)内容摘要：

0 0 1 V4 1 0 0 0 V1 V2 V3 V4 V1 0 1 1 1 V2 1 0 0 1 V3 1 0 0 0 V4 1 1 0 0 入度 出度 1 1 1 1 2 1 0 1 度数 3 2 1 2 Houfeng Wang, ICL of PKU 21 网的邻接矩阵表示 • 如果 G是带权的图， wij是边 (vi,vj)或 vi,vj的权，则其关系矩阵定义为 ∶ Houfeng Wang, ICL of PKU 22 B A C D 6 3 2 1 5 4 A B C D A 0 3  2 B  0 5 4 C   0 6 D 1   0 Houfeng Wang, ICL of PKU 23 邻接矩阵的表示 • define MAXVEX 常数 1 typedef char VexType。 typedef float AdjType。 typedef struct { VexType vexs[MAXVEX]。 // 顶点信息 AdjType arcs[MAXVEX][MAXVEX]。 // 边信息 int n。 // 图的顶点个数 }GraphMatrix。 Houfeng Wang, ICL of PKU 24 V1 V3 V2 V4 1 2 3 4 2 1 1 ∧ 1 3 4 ∧ 4 ∧ 2 ∧ 1 ∧ 3 ∧ 4 ∧ 1 2 3 4 V1 V3 V2 V4 4 ∧ 图的邻接表表示法： 即对图中每个顶点建立一个单链表，第 i个单链表中的结点表示依附于该顶点 Vi的边（或弧） 出边表 也可以设 入边表 Houfeng Wang, ICL of PKU 25 无向图的邻接表的特点 1）在 G邻接表中，同一条边对应两个结点； 2）顶点 v的度：等于 v对应线性链表的长度； 3）判定两顶点 v ， u是否邻接：要看 v对应线性链表中有无对应的结点 4）在 G中增减边 ： 要在两个单链表插入 、 删除结点 ； 5）设存储顶点的一维数组大小为 m(m图的顶点数n), 图的边数为 e， G占用存储空间为： m+2*e。 G占用存储空间与 G的顶点数、边数均有关；适用于边稀疏的图； Houfeng Wang, ICL of PKU 26 图的周游 • 从图中某个顶点出发，按照某种方式访问图中的所有顶点，使每个顶点仅被访问一次。 图的周游也称 图的遍历。 • 周游方法（二种）： – 深度优先：类似于二叉树的深度优先。 – 广度优先：类似于二叉树的广度优先。 Houfeng Wang, ICL of PKU 27 从顶点 v0出发进行深度优先周游，得到的一个 DFS序列为 ∶ v0， v1， v3， v7， v4， v2， v5， v6 从顶点 v0出发的一个 BFS序列为 ∶ v0, v1, v2, v3, v4, v5, v6, v7 Houfeng Wang, ICL of PKU 28 深度优先算法 一 深度优先遍历 从图中某顶点 v出发： 1）访问顶点 v； 2）从 v的未被访问的邻接点出发，继续对图进行深度优先遍历； 起点不唯一 + 访问先后顺序也不唯一 Houfeng Wang, ICL of PKU 29 2 3 8 10 1 4 5 9 11 6 7。