北京师范大学数据结构教学资料 第8章——图.ppt
《北京师范大学数据结构教学资料 第8章——图.ppt》由会员分享,可在线阅读,更多相关《北京师范大学数据结构教学资料 第8章——图.ppt(146页珍藏版)》请在三一文库上搜索。
1、146-1 n图的基本概念 n图的存储表示 n图的遍历与连通性 n最小生成树 n最短路径 n活动网络 第八章 图 罢 么 乎 渠 舞 情 皇 汐 破 项 哦 帝 粱 魄 声 墨 湾 萤 租 宋 贼 蹬 瞎 糊 辕 燎 掌 想 莉 牺 奖 卷 北 京 师 范 大 学 数 据 结 构 教 学 资 料 第 8 章 图 北 京 师 范 大 学 数 据 结 构 教 学 资 料 第 8 章 图 146-2 图的基本概念 n图定义 图是由顶点集合(vertex)及顶点间的 关系集合组成的一种数据结构: Graph( V, E ) 其中 V = x | x 某个数据对象 是顶点的有穷非空集合; E = (x,
2、 y) | x, y V 或 E = | x, y V 顶点 v 的出度是以 v 为始点的有向 边的条数, 记作 OD(v)。 n路径 在图 G(V, E) 中, 若从顶点 vi 出发, 沿 一些边经过一些顶点 vp1, vp2, , vpm,到达顶 点vj。则称顶点序列 (vi vp1 vp2 . vpm vj) 为从顶 点vi 到顶点 vj 的路径。它经过的边(vi, vp1)、 (vp1, vp2)、.、(vpm, vj) 应是属于E的边。 炮 饲 季 谰 瞧 采 缔 莎 亦 冒 稿 坷 煌 婆 闪 谣 价 咬 盼 佛 甥 四 揍 玩 复 骆 颧 轨 噶 碉 亭 朔 北 京 师 范 大
3、学 数 据 结 构 教 学 资 料 第 8 章 图 北 京 师 范 大 学 数 据 结 构 教 学 资 料 第 8 章 图 146-6 n路径长度 非带权图的路径长度是指此路径上 边的条数。带权图的路径长度是指路径上各边 的权之和。 n简单路径 若路径上各顶点 v1, v2, ., vm 均不 互相重复, 则称这样的路径为简单路径。 n回路 若路径上第一个顶点 v1 与最后一个顶 点vm 重合, 则称这样的路径为回路或环。 0 12 3 0 12 3 0 12 3 泞 囱 险 扰 密 母 雹 菊 惋 度 蝇 粮 咖 殉 玖 蹿 皇 腰 榷 洲 千 过 泣 未 子 歹 夜 厩 乞 典 倘 碑 北
4、 京 师 范 大 学 数 据 结 构 教 学 资 料 第 8 章 图 北 京 师 范 大 学 数 据 结 构 教 学 资 料 第 8 章 图 146-7 n连通图与连通分量 在无向图中, 若从顶点v1 到顶点v2有路径, 则称顶点v1与v2是连通的。 如果图中任意一对顶点都是连通的, 则称此图 是连通图。非连通图的极大连通子图叫做连 通分量。 n强连通图与强连通分量 在有向图中, 若对于 每一对顶点vi和vj, 都存在一条从vi到vj和从vj到 vi的路径, 则称此图是强连通图。非强连通图 的极大强连通子图叫做强连通分量。 n生成树 一个连通图的生成树是其极小连通子 图,在 n 个顶点的情形下
5、,有 n-1 条边。 孽 字 赌 中 有 许 犹 饲 驾 冯 勾 廷 呈 垮 掣 毡 豹 罗 桩 壁 荣 甭 猎 墨 蜂 困 父 钥 蝶 佩 状 儡 北 京 师 范 大 学 数 据 结 构 教 学 资 料 第 8 章 图 北 京 师 范 大 学 数 据 结 构 教 学 资 料 第 8 章 图 146-8 图的抽象数据类型 class Graph /对象: 由一个顶点的非空集合和一个边集合构成 /每条边由一个顶点对来表示。 public: Graph();/建立一个空的图 void insertVertex (const T /插入一个顶点vertex, 该顶点暂时没有入边 void inser
6、tEdge (int v1, int v2, int weight); /在图中插入一条边(v1, v2, w) void removeVertex (int v); /在图中删除顶点v和所有关联到它的边 戚 详 挨 蜡 蓉 奋 放 怯 曰 颇 洋 株 翻 膜 山 膳 钙 想 捂 疮 脊 萝 不 佃 魁 锈 剩 镶 恕 闰 哪 木 北 京 师 范 大 学 数 据 结 构 教 学 资 料 第 8 章 图 北 京 师 范 大 学 数 据 结 构 教 学 资 料 第 8 章 图 146-9 void removeEdge (int v1, int v2); /在图中删去边(v1,v2) bool I
7、sEmpty(); /若图中没有顶点, 则返回true, 否则返回false T getWeight (int v1, int v2); /函数返回边 (v1,v2) 的权值 int getFirstNeighbor (int v); /给出顶点 v 第一个邻接顶点的位置 int getNextNeighbor (int v, int w); /给出顶点 v 的某邻接顶点 w 的下一个邻接顶点 ; 株 陵 汝 媳 镀 沧 揽 条 足 奢 螟 瘫 醛 寸 蹈 声 彤 思 颐 囤 篙 藕 值 郝 烩 议 腆 眩 哺 缎 胜 摈 北 京 师 范 大 学 数 据 结 构 教 学 资 料 第 8 章 图
8、 北 京 师 范 大 学 数 据 结 构 教 学 资 料 第 8 章 图 146-10 图的存储表示 n图的模板基类 在模板类定义中的数据类型 参数表 中,T是顶点数据的 类型,E是边上所附数据的类型。 n这个模板基类是按照最复杂的情况(即带权 无向图)来定义的,如果需要使用非带权图 ,可将数据类型参数表 改 为 。 n如果使用的是有向图,也可以对程序做相应 的改动。 檄 押 嗜 臂 扦 溜 克 概 戌 辽 狂 格 驾 纲 份 毡 融 蔑 峻 腆 矢 夺 窿 哨 标 索 琴 坯 札 帧 肥 聋 北 京 师 范 大 学 数 据 结 构 教 学 资 料 第 8 章 图 北 京 师 范 大 学 数
9、据 结 构 教 学 资 料 第 8 章 图 146-11 图的模板基类 const int maxWeight = ; /无穷大的值(=) const int DefaultVertices = 30; /最大顶点数(=n) template class Graph /图的类定义 protected: int maxVertices; /图中最大顶点数 int numEdges; /当前边数 int numVertices; /当前顶点数 int getVertexPos (T vertex); /给出顶点vertex在图中位置 public: 垂 龟 峙 邦 敝 檄 擞 揽 摆 迫 症 恰
10、仓 耘 扁 舜 械 遣 勿 兽 悟 尧 讶 鼓 戚 渍 英 癌 识 唐 萝 下 北 京 师 范 大 学 数 据 结 构 教 学 资 料 第 8 章 图 北 京 师 范 大 学 数 据 结 构 教 学 资 料 第 8 章 图 146-12 Graph (int sz = DefaultVertices); /构造函数 Graph();/析构函数 bool GraphEmpty () const /判图空否 return numEdges = 0; int NumberOfVertices () return numVertices; /返回当前顶点数 int NumberOfEdges () r
11、eturn numEdges; /返回当前边数 virtual T getValue (int i);/取顶点 i 的值 virtual E getWeight (int v1, int v2); /取边上权值 virtual int getFirstNeighbor (int v); /取顶点 v 的第一个邻接顶点 又 继 侄 瓢 嘱 狮 蹲 份 加 衅 泰 届 肝 挠 锤 番 逞 倒 搓 亮 愁 牲 谨 诈 波 厨 信 呻 剐 禾 蹋 便 北 京 师 范 大 学 数 据 结 构 教 学 资 料 第 8 章 图 北 京 师 范 大 学 数 据 结 构 教 学 资 料 第 8 章 图 146-
12、13 virtual int getNextNeighbor (int v, int w); /取邻接顶点 w 的下一邻接顶点 virtual bool insertVertex (const T vertex); /插入一个顶点vertex virtual bool insertEdge (int v1, int v2, E cost); /插入边(v1,v2), 权为cost virtual bool removeVertex (int v); /删去顶点 v 和所有与相关联边 virtual bool removeEdge (int v1, int v2); /在图中删去边(v1,v2)
13、 ; 逃 败 瞒 乓 刺 俭 侣 录 迫 氓 陡 烩 铱 辟 披 搔 哮 红 越 森 旁 崖 抽 襟 丙 约 毗 磐 咕 维 御 桩 北 京 师 范 大 学 数 据 结 构 教 学 资 料 第 8 章 图 北 京 师 范 大 学 数 据 结 构 教 学 资 料 第 8 章 图 146-14 邻接矩阵 (Adjacency Matrix) n在图的邻接矩阵表示中,有一个记录各个顶 点信息的顶点表,还有一个表示各个顶点之 间关系的邻接矩阵。 n设图 A = (V, E) 是一个有 n 个顶点的图, 图的 邻接矩阵是一个二维数组 A.edgenn,定义 : 迅 骋 崔 靖 狭 嫩 砾 醛 桩 胖 崩
14、 烹 狸 期 叛 官 凄 念 隧 纹 沁 牟 悯 苯 肃 垫 咳 聪 徒 纯 宠 坦 北 京 师 范 大 学 数 据 结 构 教 学 资 料 第 8 章 图 北 京 师 范 大 学 数 据 结 构 教 学 资 料 第 8 章 图 146-15 n无向图的邻接矩阵是对称的; n有向图的邻接矩阵可能是不对称的。 0 12 3 0 1 2 傣 茬 离 辣 刊 酌 欣 恍 凸 择 啃 腑 疲 撑 耸 硷 展 匙 鸭 吁 胡 痉 龄 伺 佰 穷 羊 屹 贴 菲 耍 鸣 北 京 师 范 大 学 数 据 结 构 教 学 资 料 第 8 章 图 北 京 师 范 大 学 数 据 结 构 教 学 资 料 第 8
15、章 图 146-16 n在有向图中, 统计第 i 行 1 的个数可得顶点 i 的出度,统计第 j 列 1 的个数可得顶点 j 的入 度。 n在无向图中, 统计第 i 行 (列) 1 的个数可得顶 点i 的度。 网络的邻接矩阵 旬 琳 轰 适 竣 鞘 蝶 损 姐 咖 盐 拽 课 芋 次 阜 氯 拷 韩 祷 寨 令 簧 骆 嚎 饼 缮 趁 的 蛾 央 减 北 京 师 范 大 学 数 据 结 构 教 学 资 料 第 8 章 图 北 京 师 范 大 学 数 据 结 构 教 学 资 料 第 8 章 图 146-17 8 6 3 1 2 9 5 4 2 0 3 1 用邻接矩阵表示的图的类定义 templa
16、te class Graphmtx : public Graph friend istream/输入 新 租 颇 欠 仟 瘁 北 消 碑 入 恋 牵 激 鄂 樟 炉 言 镑 龄 遏 雾 涝 记 近 谴 歪 堆 沦 晰 酪 膏 欢 北 京 师 范 大 学 数 据 结 构 教 学 资 料 第 8 章 图 北 京 师 范 大 学 数 据 结 构 教 学 资 料 第 8 章 图 146-18 friend ostream/输出 private: T *VerticesList; /顶点表 E *Edge;/邻接矩阵 int getVertexPos (T vertex) /给出顶点vertex在图中的
17、位置 for (int i = 0; i = 0 numVertices = 0; numEdges = 0; int i, j; VerticesList = new TmaxVertices; /创建顶点表 Edge = (int *) new int *maxVertices; for (i = 0; i int Graphmtx:getFirstNeighbor (int v) /给出顶点位置为v的第一个邻接顶点的位置, /如果找不到, 则函数返回-1 if (v != -1) for (int col = 0; col int Graphmtx:getNextNeighbor (in
18、t v, int w) /给出顶点 v 的某邻接顶点 w 的下一个邻接顶点 if (v != -1 col struct Edge /边结点的定义 int dest; /边的另一顶点位置 E cost; /边上的权值 Edge *link; /下一条边链指针 Edge () /构造函数 Edge (int num, E cost) /构造函数 : dest (num), weight (cost), link (NULL) bool operator != (Edge /判边等否 ; 耽 窍 窍 凡 力 窍 娱 汞 碧 仰 津 啼 筐 帮 耀 捡 摄 挽 圣 休 啡 庞 电 宠 胆 欺 鹏 呕
19、 惑 存 昧 骄 北 京 师 范 大 学 数 据 结 构 教 学 资 料 第 8 章 图 北 京 师 范 大 学 数 据 结 构 教 学 资 料 第 8 章 图 146-30 template struct Vertex /顶点的定义 T data; /顶点的名字 Edge *adj; /边链表的头指针 ; template class Graphlnk : public Graph /图的类定义 friend istream /输入 friend ostream /输出 捂 页 笔 谬 什 眺 讲 栖 胃 岁 漆 兼 端 年 咋 娥 车 锨 郁 豌 亲 致 钝 肢 嘉 锥 试 围 垃 弊 浙
20、 辟 北 京 师 范 大 学 数 据 结 构 教 学 资 料 第 8 章 图 北 京 师 范 大 学 数 据 结 构 教 学 资 料 第 8 章 图 146-31 private: Vertex *NodeTable; /顶点表 (各边链表的头结点) int getVertexPos (const T vertx) /给出顶点vertex在图中的位置 for (int i = 0; i = 0 numVertices = 0; numEdges = 0; NodeTable = new VertexmaxVertices; /创建顶点表数组 if (NodeTable = NULL) cerr
21、 Graphlnk:Graphlnk() /析构函数:删除一个邻接表 for (int i = 0; i *p = NodeTablei.adj; while (p != NULL) NodeTablei.adj = p-link; delete p; p = NodeTablei.adj; delete NodeTable; /删除顶点表数组 剑 胃 订 尉 惶 漆 凉 黄 中 究 九 献 蹿 尝 奋 龚 侈 搂 泳 吐 跨 站 瘟 刨 荷 频 氛 赠 贡 嫡 扮 摧 北 京 师 范 大 学 数 据 结 构 教 学 资 料 第 8 章 图 北 京 师 范 大 学 数 据 结 构 教 学 资
22、料 第 8 章 图 146-35 template int Graphlnk:getFirstNeighbor (int v) /给出顶点位置为 v 的第一个邻接顶点的位置, /如果找不到, 则函数返回-1 if (v != -1) /顶点v存在 Edge *p = NodeTablev.adj; /对应边链表第一个边结点 if (p != NULL) return p-dest; /存在, 返回第一个邻接顶点 return -1;/第一个邻接顶点不存在 柑 情 卸 妮 牺 遮 廖 嘘 蚕 烷 玻 佑 脱 砚 繁 据 山 辰 伍 膝 憎 虏 删 苗 韭 眯 奥 遣 匹 奔 款 伦 北 京 师
23、范 大 学 数 据 结 构 教 学 资 料 第 8 章 图 北 京 师 范 大 学 数 据 结 构 教 学 资 料 第 8 章 图 146-36 template int Graphlnk:getNextNeighbor (int v, int w) /给出顶点v的邻接顶点w的下一个邻接顶点的位置, /若没有下一个邻接顶点, 则函数返回-1 if (v != -1) /顶点v存在 Edge *p = NodeTablev.adj; while (p != NULL if (p != NULL /返回下一个邻接顶点 return -1; /下一邻接顶点不存在 苫 篆 啃 奔 算 爷 沏 陨 皑
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 北京师范大学数据结构教学资料 第8章图 北京师范大学 数据结构 教学 资料
链接地址:https://www.31doc.com/p-5895961.html