网站建设优化服务公司,汉中软件开发项目管理,网站做成软件免费,项目外包公司可以去吗第五章 图 图的基本概念图的应用背景图的定义和术语 图的存储结构邻接矩阵邻接表 图的遍历连通图的深度优先搜索连通图的广度优先搜索 图的应用最小生成树拓扑排序 小试牛刀 图的基本概念 图结构中#xff0c;任意两个结点之间都可能相关#xff1b;而在树中#xff0c;结点… 第五章 图 图的基本概念图的应用背景图的定义和术语 图的存储结构邻接矩阵邻接表 图的遍历连通图的深度优先搜索连通图的广度优先搜索 图的应用最小生成树拓扑排序 小试牛刀 图的基本概念 图结构中任意两个结点之间都可能相关而在树中结点具有层次关系每一层结点只能和上一层至多一个结点相关但可能和下一层多个结点相关 图的应用背景 上图中圆圈称为顶点连线称为边连线附带的数值称为边的权图结构可以用来描述通信网络
图的定义和术语 图G由两个集合V和E组成记作G(V,E)V是顶点的集合有穷非空E是边的集合 有向图边是有序的边带箭头“单行道”、用顶点1顶点2表示从顶点1到顶点2的边无向图边是无序的边不带箭头、用顶点1顶点2表示顶点1和2之间的边弧弧头弧尾弧有向图的边称为弧vw表示从v到w的一条弧其中v称为弧尾或始点w称为弧头或终点 任何两点之间都有边的无向图称为无向完全图任何两点之间都有弧的有向图称为有向完全图 权图的边的附带数值实际应用中可以表示从一个顶点到另一个顶点的距离、代价或耗费等带权图每条边都带权的图称为带权图顶点的度D、入度ID、出度OD无向图中顶点的度是与该顶点相关联的边的数目有向图中则把以顶点为终点的弧的数目称为该顶点的入度以该顶点为始点的弧的数目称为该顶点的初读有向图中的度为入度和出度的和子图设G(V,E)是一个图若E’是E的子集V’是V的子集并且E’中的边仅有与V’中的顶点相关联。则G’称为G的子图路径、路径长度从一个顶点到另一个顶点称为路径路径长度就是路径或弧上边的数之和简单路径、回路、简单回路简单路径序列中顶点不重复出现第一个顶点和最后一个顶点相同的路径称为回路或环除了第一个顶点和最后一个顶点外其余顶点不重复的回路称为简单回路或简单环连通、连通图、联通分量连通图在无向图中如果从顶点v到顶点v’有路径则称其为连通连通图图中任意两个顶点都是连通的连通分量无向图中的极大连通子图强连通、强连通图、强连通分量强连通图有向图任意一对顶点双向连通强连通分量有向图的极大连通子图生成树、生成森林生成树包含所有顶点的一个极小连通子图生成森林在非连通图中每个连通分量都可得到一个极小的连通子图即一棵生成树这些连通分量的生成树就组成了一个非连通图的生成森林
图的存储结构
邻接矩阵
二维矩阵来实现两顶点连通为1不连通为0行列分别表示全部顶点如下图所示 注也可用邻接矩阵表示带权图没有边的用无穷表示有的则用权其余正常
邻接表 邻接表是顺序存储与链式存储相结合的存储方式 有向图的邻接表以顶点Vi为尾的弧 无向图的邻接表第i个单链表中的结点表示依赖于Vi的边 逆邻接表逆邻接表是指以每个顶点作为索引记录各个顶点的入边即指向该顶点的边的数据结构。有向图的邻接表记录的是出边 图的遍历 图的遍历是指从图的某个顶点出发系统的访问图的每个顶点并且每个顶点只能被访问一次 连通图的深度优先搜索 以图中某个顶点出发首先访问出发点然后任选一个未访问过的邻接点以邻接点为新出发点继续依此类推直到所有顶点都被访问 连通图的广度优先搜索 从图中某个顶点出发访问了该顶点后依次访问该顶点的邻接点然后从邻接点出发继续访问直到结束 图的应用
最小生成树 对于有n个顶点的无向图所有生成树都有且仅有n-1条边 Prim算法假设G(V,E)是一个带权图生成的最小生成树为MinT(V,T),其中V为顶点的集合T为边的集合 初始化U{u0}T{}。其中U为一个新设置的顶点的集合初始U中只含有顶点u0这里假设从顶点u0出发对所有u∈Uv∈V-U中找一条权最小的边u’,v’将这条边加入集合T中将顶点v’加入集合U中如果UV则算法结束否则重复 克鲁斯卡尔算法 设GV,E令最小生成树初始状态为只有n个顶点而无边的非连通图TV{}每个顶点自成一个连通分量在E中选取代价最小的边若该边依附的顶点落在T中不同的连通分量上则将此边加入到T中否则舍去此边选取下一条代价最小的边依此类推直到T中所有顶点都在同一连通分量上为止 Dijkstra求单源最短路径(设置顶点集合S开始时S中只含有源点v) 创建一个节点集合初始时只包含起点节点以及一个距离表记录起点到各个节点的当前最短距离和路径。从起点开始遍历与起点相邻的节点并更新距离表中的距离和路径。选择一个距离表中未访问过的节点中距离最短的节点将其加入节点集合中并继续遍历与该节点相邻的节点。若找到更短的路径更新距离表中的距离和路径。重复步骤3直到所有节点都被加入节点集合或者目标节点被加入节点集合。最终距离表中记录的就是起点到各个节点的最短距离和路径。
拓扑排序
AOV网工程或者某种流程可分为若干个小的工程或阶段这些小的工程或阶段就称为活动若以图中顶点表示活动有向边表示活动之间的优先关系这种有向图称为AOV网 拓扑排序 完成拓扑排序的前提条件是AOV网中不能出现回路 有向图拓扑排序算法的基本步骤如下
- 图中选择一个入度为0的顶点输出该顶点
- 从图中删除该顶点及其相关联的弧调整被删弧的弧头结点的入度入度减1
- 重复执行上述步骤直到所有入度为0的顶点均被输出小试牛刀
一个有n个顶点的无向连通图最少有______条边无向图的邻接矩阵是_______矩阵给出下图的邻接矩阵和邻接表 分别给出下图的邻接矩阵、邻接表和逆邻接表 分别给出下图从v5出发按深度优先搜索和广度优先搜索算法遍历得到的顶点序列
