英语门户网站织梦源码,查国外企业信息的网站,wordpress有商城吗,临沂企业网站建设公司图 引自#xff1a;《数据结构教程》。 概念 图可以使得元素之间的关系是 多对多。图中任意两个数据元素之间都可能存在连接关系。图作为一种数据结构#xff0c;可以表达数据元素之间广泛存在着的更为复杂的关系。在众多应用之中#xff0c;如电子线路分析、工程计划分析、…
图 引自《数据结构教程》。 概念 图可以使得元素之间的关系是 多对多。图中任意两个数据元素之间都可能存在连接关系。图作为一种数据结构可以表达数据元素之间广泛存在着的更为复杂的关系。在众多应用之中如电子线路分析、工程计划分析、寻找最短路径等等图是描述这类关系的一个十分自然的模型。有关图论的内容是离散数学的主要内容之一这里仅仅介绍一些概念和存储方法。 有向图/无向图若图中每一条边都是没有方向的则为无向图。如图中每一条边都具有方向则称为有向图。 通常需要将图中顶点按照一个顺序进行标号如果某个顶点在一个序列中的位置为 i那么该顶点为顶点 i。 权/网与边有关的数据信息被称为权。在具体应用中权值可以有实际意义比如线路的长度或等级、电路中两个端点之间的电阻电流或电压值等等。每条边上都带权的图称为网络或 网。问题所属的领域不同顶点和边的实际意义也就不同。 度顶点的度是指连接在某顶点 v 的边数记 TD(v)。对于有向图某顶点 v 的入度是指以顶点 v 为终点的弧的数目记 ID(v)某顶点 v 的出度是指以顶点 v 为起点的弧的数目记 OD(v)有 TD(v) ID(v) OD(v)。如果用 n 表示图中顶点的数目用 e 表示边或弧的数目用 TD(vi) 表示顶点 vi 的度则有以下关系2e 从 i 1 到 i n 累加 TD(vi)。从这个关系可知具有 n 个顶点的无向图最多有 n(n - 1)/2这样的图称为 完全图具有 n 个顶点的有向图最多有 n(n - 1) 条边这样的有向图称为 有向完全图。若一个图接近于完全图则称为稠密图若边或弧的数目很少的图为稀疏图。 路径/环回路/有跟图在无向图中两个顶点之间的顶点序列可以使得两顶点之间连通一条通路即路径。这条路径上所包含边的数目被称为该路径的长度。对于有向图则该路径也是有相的。对于 带权图 路径长度是指路径上所有边的权值之和。若出发顶点和结束顶点为一个顶点则该路径为回路或环。在一个有向图中若存在一个顶点使得从该顶点出发的路径可以到达图中其他所有顶点则称该有向图为有根图该顶点为该有向图的根。 子图一个图的子集包括图的一部分顶点和边。 图的连通对于无向图若从定点 vi 到顶点 vji ≠ j有路径则称 vi 到 vj 之间是连通的。如果无向图中任意两个顶点之间都是连通的则称该无向图为连通图。无向图中的极大连通子图称为该图的连通分量显然对于一个图其只有一个。若有向图中任意两个顶点之间都是连通的则称该有向图是 强连通图有向图 中的 极大 强连通子图 称为该 有向图 的 强连通分量。 生成树一个 连通图 的 极小连通子图 称为该图的一个 生成树。生成树中不含有回路在生成树中添加任意一条边必然会产生回路若在生成树中减少任意一条边则一定会使它成为非连通的。 生成森林若一个有向图恰好有一个顶点的入度为 0其余顶点的入度均为 1则是一棵有向树一个有向图的生成森林由若干棵有向树组成。 图的基本操作 图的存储 邻接矩阵法不适合稀疏图因为空间性价比低。 邻接表法。 有向图的十字链表法。略。 图的遍历 从给定图中任意指定的顶点出发按照某个原则系统的访问图中的其他顶点每个顶点仅仅被访问一次得到由该图中顶点组成的一个序列这个过程称为图的遍历。 图的遍历 通常采用 深度优先搜索 与 广度优先搜索 方式进行。具体看本文下面的 “DFS BFS深度/广度优先搜索”一节。 深度优先遍历(Depth First Search)的主要思想是首先以一个未被访问过的顶点作为起始顶点沿当前顶点的边走到未访问过的顶点。当没有未访问过的顶点时则回到上一个顶点继续试探别的顶点直至所有的顶点都被访问过。引自 深度优先遍历与连通分量 | 菜鸟教程 (runoob.com) 广度优先搜索其遍历原则是从图中指定顶点出发访问该顶点后再依次访问该顶点的各个未被访问过的邻接点然后从这些邻接点出发按照同样的原则依次访问他们的未被访问过的邻接点以此类推直到图中所有访问过的顶点的临界点都被访问若此时图中还存在未被访问过的顶点则从另一个未被访问过的顶点出发继续进行上述过程直到图中所有顶点都被访问。广度优先搜索与深度优先搜索不同首先访问指定的出发点然后依次访问该顶点的所有未被访问过的邻接点再接下来访问邻接点的未被访问过的邻接点以此类推实现这个过程需要设置一个队列结构。 图的存储方式、遍历的出发点、遍历的方式等的不同均会使遍历后的序列各不相同。 后续概念 最小生成树、最短路径、AOV网与拓扑结构排序、AOE网与关键路径等。 图论基础和表示 | 菜鸟教程 (runoob.com)。
