首先,你要明确图是什么样子的,就是下面这个样子的
图的定义与术语
有向图和无向图
直接对比图就可以看出来,有向图和无向图的区别了,这个没有什么难的。
有向图和无向图的表示法有略微的区别,注意看
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的一条弧,v称为弧尾或始点,w称为弧头或终点。
任何两点之间都有边的无向图称为无向完全图。
任何两点之间都有弧的有向图称为有向完全图。
权、带权图:图的边附带数值,这个数值叫权。每条边都带权的图称为带权图。
顶点的度、入度、出度:
简单路径、回路、简单回路:序列中顶点不重复出现的路径称为简单路径。第一个顶点和最后一个顶点相同的路径称为回路。除了第一个顶点和最后一个顶点外,其余顶点不重复的回路,称为简单回路或简单环。
下面还有一些需要了解的术语
连通、连通图、连通分量、极大连通子图、强连通、强连通图、强连通分量、生成树、生成森林
如果精力足够,都看看吧
图的存储结构有很多中,例如 邻接矩阵、邻接表、十字链表和邻接多重表
矩阵中标记1,有边,标记0,没有边
注意:无向图的邻接矩阵是一个对称矩阵
带权图的邻接矩阵
尝试着,画出无向图吧!
邻接表是顺序存储与链式存储相结合的存储方法。
下图中,左侧是无向图,右侧是该无向图的邻接表,注意看,∧
该符号,表示结束,没有连接的顶点了。
有向图及其类似,这个就不在做图扩充
图的遍历是指从图的某个顶点出发,系统地访问图的每个顶点,并且每个顶点只被访问一次。
遍历图的基本方法有两种:深度优先搜索和广度优先搜索。
深度优先,就是往下走,走不动了,返回上一级在走
顺着一个顶点,然后都遍历完。
概念:一个图的最小生成树是图所有生成树中权总和最小的生成树
构造最小生成树的prim算法
每次都找权值最小的
看案例
构造最小生成树的克鲁斯卡尔算法
与 单源最短路径
这两种算法,自己看一下吧。
aov网
工程或者某种流程可以分为若干个小的工程或阶段,这些小的工程或阶段就称为活动。
如果以图中的顶点来表示活动,有向边表示活动之间的优先关系,这种用顶点表示活动的有向图称为aov网。
拓扑排序算法的时间复杂度为o(n+e),n是图的顶点个数,e是图的弧的数目。
拓扑排序算法的基本步骤如下:
好好理解一下拓扑排序算法吧
画图说明步骤
更多图示: https://dwz.cn/r4lcxeul
拓扑排序不唯一~
如对本文有疑问, 点击进行留言回复!!
HBase Filter 过滤器之FamilyFilter详解
去 HBase,Kylin on Parquet 性能表现如何?
如何找到Hive提交的SQL相对应的Yarn程序的applicationId
网友评论