青岛网站建设微动力,张家港外贸型网站建设,wordpress主题 幻灯片,wordpress移动模板图的基本概念首先#xff0c;你要明确图是什么样子的#xff0c;就是下面这个样子的 图的定义与术语有向图和无向图直接对比图就可以看出来#xff0c;有向图和无向图的区别了#xff0c;这个没有什么难的。 有向图和无向图的表示法有略微的区别#xff0c;注意看 G1有箭头…图的基本概念首先你要明确图是什么样子的就是下面这个样子的 图的定义与术语有向图和无向图直接对比图就可以看出来有向图和无向图的区别了这个没有什么难的。 有向图和无向图的表示法有略微的区别注意看 G1有箭头有向图表示方法是 V{V~0~V~1~V~2~V~3~} E {V~0~V~1~V~1~V~2~V~1~V~0~V~2~V~0~V~2~V~3~} G2无箭头无向图表示方法是 V{V~0~V~1~V~2~V~3~} E {(V~0~V~1~)(V~1~V~2~)(V~0~V~2~)(V~2~V~3~)}弧、弧头、弧尾有向图的边称为弧。无向图叫做边。有序偶对表示有向图从v到w的一条弧v称为弧尾或始点w称为弧头或终点。任何两点之间都有边的无向图称为无向完全图。 任何两点之间都有弧的有向图称为有向完全图。权、带权图图的边附带数值这个数值叫权。每条边都带权的图称为带权图。顶点的度、入度、出度 1. 无向图中顶点v的度是与该顶点相关联的边的数目记为D(v)。 2. 有向图中把以顶点v为终点的弧的数目称为v的入度记为ID(v)把以顶点v为始点的弧的数目称为v的出度记为OD(v)。有向图顶点v的度为入度和出度之和即Dv IDv ODv。简单路径、回路、简单回路序列中顶点不重复出现的路径称为简单路径。第一个顶点和最后一个顶点相同的路径称为回路。除了第一个顶点和最后一个顶点外其余顶点不重复的回路称为简单回路或简单环。下面还有一些需要了解的术语连通、连通图、连通分量、极大连通子图、强连通、强连通图、强连通分量、生成树、生成森林如果精力足够都看看吧图的存储结构图的存储结构有很多中例如 邻接矩阵、邻接表、十字链表和邻接多重表邻接矩阵矩阵中标记1有边标记0没有边注意无向图的邻接矩阵是一个对称矩阵 带权图的邻接矩阵 邻接矩阵自考/期末考试真题 尝试着画出无向图吧邻接表邻接表是顺序存储与链式存储相结合的存储方法。下图中左侧是无向图右侧是该无向图的邻接表注意看∧该符号表示结束没有连接的顶点了。 有向图及其类似这个就不在做图扩充图的遍历图的遍历是指从图的某个顶点出发系统地访问图的每个顶点并且每个顶点只被访问一次。 遍历图的基本方法有两种深度优先搜索和广度优先搜索。连通图的深度优先搜索深度优先就是往下走走不动了返回上一级在走 连通图的广度优先搜索顺着一个顶点然后都遍历完。图的应用最小生成树的概念概念一个图的最小生成树是图所有生成树中权总和最小的生成树构造最小生成树的Prim算法每次都找权值最小的看案例 构造最小生成树的克鲁斯卡尔算法 与 单源最短路径 这两种算法自己看一下吧。拓扑排序AOV网 工程或者某种流程可以分为若干个小的工程或阶段这些小的工程或阶段就称为活动。 如果以图中的顶点来表示活动有向边表示活动之间的优先关系这种用顶点表示活动的有向图称为AOV网。 2. 拓扑排序 设G(VE) 是一个具有n个顶点的有向图V中顶点的序列v~1~v~2~...v~n~称为一个拓扑序列当且仅当该顶点序列满足下列条件若在有向图G中从顶点v~i~ ~ v~j~ 有一条路径则在拓扑序列中顶点v~i~必须排在v~j~之前。找到一个有向图的一个拓扑序列的过程称为拓扑排序。完成拓扑排序的前提条件是AOV网中不允许出现回路。拓扑排序算法的时间复杂度为O(ne)n是图的顶点个数e是图的弧的数目。拓扑排序算法的基本步骤如下图中选择一个入度为0的顶点输出该顶点从图中删除该顶点及相关联的弧调整被删弧的弧头结点的入度入度减1重复执行上述两个步骤直到所有的入度为0好好理解一下拓扑排序算法吧自考/数据结构期末考试真题 画图说明步骤 更多图示 https://dwz.cn/r4lCXEuL 拓扑排序不唯一~
