-
有向图
2018-10-30 11:25:35有向图 1、术语 在有向图中,边是单向的。每条边所连接的两个顶点都是一个有序对,他们的邻接性是单向的。 出度:该顶点指出的边的总数 入度:指向该顶点的边的总数 一条有向边的第一个顶点称为它的头,第二个...有向图
1、术语
在有向图中,边是单向的。每条边所连接的两个顶点都是一个有序对,他们的邻接性是单向的。
出度:该顶点指出的边的总数
入度:指向该顶点的边的总数一条有向边的第一个顶点称为它的头,第二个顶点称为它的尾。将有向边画为由头指向尾的一个箭头。
用 v -> w 表示有向图中一条由v指向w的边。有向路径
有向环
简单有向环:除了起点和终点必须相同之外,不含有重复的顶点和边的环路径或环的长度即为其中所包含的边数。
有向图的可达性:当存在从v到w的路径时,称顶点w能够由顶点v达到。
无向图的连通性
2、有向图的数据结构
有向图的API
reverse() 方法,返回该有向图的一个副本,但将其中所有边的方向反转。这样用例就可以找出指向每个顶点的所有边。
有向图的表示:邻接表。边 v -> w 表示为顶点v所对应的邻接链表中包含一个w顶点。
在用邻接表表示无向图时,如果v 在w 的链表中,那么w必然也在v的链表中。但在有向图中这种对称性是不存在的,因为每条边都只会出现一次。
有向图的数据结构
Digraph数据类型与Graph数据类型基本相同。区别是 addEdge() 只调用了一次 add(),而且它还有一个 reverse() 方法来返回图的反向图。
/*DiGraph数据类型*/ public class DiGraph{ private final int V; //顶点数目 private int E; //边的数目 private Bag<Integer>[] adj; //邻接表 public DiGraph(int V){ this.V = V; this.E = 0; adj = (Bag<Integer>[]) new Bag[V]; //创建邻接表 for(int v = 0; v < V; v++) //将所有链表初始化为空 adj[v] = new Bag<Integer>(); } public Graph(In in){ this(in.readInt()); //读取V并将图初始化 int E = in.readInt(); //读取E for(int i = 0;i < E; i++){ int v = in.readInt(); int w = in.readInt(); addEdge(v, w); //添加一条由v指向w的边 } } public int V(){ return V; } public int E(){ return E; } public void addEdge(int v, int w){ adj[v].add(w); //!!!!与无向图的区别,只调用了一次add() E++; } public Iteralbe<Integer> adj(int v){ return adj[v]; } public Digraph reverse(){ //!!!!与无向图的区别,有一个 reverse() 方法来返回图的反向图 Digraph R = new Digraph(V); for(int v = 0; v < V; v++) for(int w : adj(v)) R.addEdge(w, v); return R; } }
3、有向图的可达性
深度优先搜索 DFS 解决了单点连通性的问题,使得用例可以判定其他顶点和给定的起点是否连通。
同样在有向图中,
单点可达性给定一幅有向图和一个起点s,回答“是否存在一条从s到达给定顶点v的有向路径?”等类似问题。
多点可达性给定一幅有向图和顶点的集合,回答“是否存在一条从集合中的任意顶点到达给定顶点v的有向路径?”等类似问题。DirectedDFS 算法实现
/* * 有向图的可达性。用例能够判断从给定的一个或者一组顶点能到达哪些其他顶点。 */ public class DirectedDFS{ private boolen[] marked; //使用一个boolean数组来记录和起点s连通的所有顶点 public DirectedDFS(Digraph G, int s){ marked = new boolen[G.V()]; dfs(G, s); } public DirectedDFS(Digraph G, Iterable<Integer> sources){ marked = new boolen[G.V()]; for(int s: sources) if(!marked[s]) dfs(G, s); } private void dfs(Graph G, int v){ marked[v] = true; for (int w : G.adj(v)){ if (!marked[w]) dfs(G, w); } } public boolen marked(int v){ return marked[v]; } }
下图显示了这个算法在处理有向图的操作轨迹。这份轨迹比相应的无向图算法的轨迹稍稍简单些,因为深度优先搜索本质上是一种适用于处理有向图的算法,每条边都只会被表示一次。
有向图路径问题
单点路径 DepthFirstPaths
单点最短路径 BreadFirstPaths
-
有向图和无向图
2019-04-13 18:51:19有向图、无向图 有向图和无向图是我们常用到的术语,本文属于简单的科普帖。 全部由无向边构成图称为无向图(Undirected Graph),全部由有向边构成图称为无向图(Directed Graph)。有向,顾名思义,有方向。本文...有向图、无向图
有向图和无向图是我们常用到的术语,本文属于简单的科普帖。
全部由无向边构成图称为无向图(Undirected Graph),全部由有向边构成图称为有向图(Directed Graph)。有向,顾名思义,有方向。本文中顶点Vertex(V),边Edge(E)
(1)出度和入度:如图D,以点A为例子,在所有与A关联的边中,以A为起点的边的条数称为出度。而入度则刚好相反,以A为终点的边的条数则称为入读。其中,入度+出度,我们称为A的度。注意特殊情况:如图:A有一个自环,起点和终点都是自己,此时出度算一度,入度也算一度。如图:A的出度为3,入度也为2,A的度的5。
(2)描述图的邻接矩阵和关联矩阵
【邻接矩阵】定义:
设无向图G=(V,E),其中顶点集V=v1,v2,…,vn,边集 E=e1,e2,…,eε。用aij表示顶点vi与顶点vj之间的边数,可能取值为0,1,2,…,称所得矩阵A=A(G)=(aij)n×n为图G的邻接矩阵。邻接矩阵可以描述有向图和无向图。示例,求图所示简单图的邻接矩阵?
解:根据定义,可求得该无向图的邻接矩阵为
邻接矩阵的存储特点:
(a)无向图的邻接矩阵一定是一个对称矩阵,有向图不一定是。
*(b)邻接矩阵所需的存储空间值域只与顶点数有关系。
(c)用邻接矩阵存储图,容易判断两个点之间是否有边。
(d)如果一个有向图的邻接矩阵为三角矩阵(主对角线为0),则它的拓扑排序一定存在。
*(e)小技巧:
无向图:邻接矩阵的第i行或者第i列的非零元素的个数正好是第i个顶点Vi的度;
有向图:邻接矩阵的第i行的非零元素个数正好是第i个顶点Vi的出度,第i列非零元素的个数正好是第i个顶点Vi的入度。【关联矩阵】
定义:
设任意图G=(V,E),其中顶点集V=v1,v2,…,vn,边集E=e1,e2,…,eε。用mij表示顶点vi与边ej关联的关系,可能取值为0,1,-1,称所得矩阵M(G)=(mij)n×ε为图G的关联矩阵。
mij 表示i行j列,探究顶点Vi和边Ej之间的关系,形成下列的关联矩阵
示例:
关联矩阵
连通图、连通分量
连通图:无向图中,若从顶点u到顶点v有路径,称为u,v是连通的。若图中任意两个顶点均是连通的,则称为连通图。
连通分量:无向图中极大连通子图称为连通分量。强连通图、强连通分量
强连通图:有向图中,若从顶点u到顶点v有路径,称为u,v是连通的。若图中任意两个顶点均是连通的,则称为强连通图。
连通分量:无向图中极大连通子图称为强连通分量。特:强连通图只有强连通分量(本身),非强连通图有多个强连通分量。另外,本文参考路了下面两位作者的优秀博客
https://blog.csdn.net/Hanging_Gardens/article/details/55670356
https://blog.csdn.net/legendaryhaha/article/details/83049101 -
数据结构——图的五种种类【无向图-有向图-简单图-完全无向图-有向完全图】
2020-02-11 09:23:16二:有向图 1.定义 2.图形化解释 3.结合表达式介绍 有向图和无向图区别: 三:简单图 1.定义 2.图形化解释 四:完全无向图 1.定义 2.图形化解释 五:有向完全图 1.定义 2.图形化解释 一:无向图 1....目录:
一:无向图
1.定义
若顶点
到
之间的边没有方向,则称这条边为 无向边(Edge)
用无序偶对
来表示
如果图中任意两个顶点之间的边都是无向边,则称该图为 无向图
无向图顶点的边数叫做 度
2.图形化解释
下图所示即为无向图:
3.结合
表达式介绍
由于无向图是无方向的,连接顶点
的边
可以表示成无序对
也可以写成
对于上图中的无向图
来说
其中顶点集合
边集合
二:有向图
1.定义
若从顶点
到
的边有方向,则称这条边为 有向边,也称为 弧(Arc)
用有序偶
来表示,
称为弧尾(Tail),
称为弧头(Head)
如果图中任意两个顶点之间的边都是有向边,则称该图为 有向图(Directed graphs)
有向图顶点分为 入度(箭头朝自己) 和 出度(箭头朝外)
2.图形化解释
如下图所示即为一个有向图:
3.结合
表达式介绍
连接到顶点
到
的有向边就是弧
是弧尾
是弧头
表示弧,注意不能写成
对于上图的有向图
其中顶点集合
弧集合
有向图和无向图区别:
注:看清楚了,无向边用小括号
表示
而有向边则是使用尖括号
表示
三:简单图
1.定义
在图中,若不存在顶点到其自身的边,且同一条边不重复出现,则称这样的图为简单图
2.图形化解释
如下所示的两个图就不属于简单图:
四:完全无向图
1.定义
在无向图中,如果任意两个顶点之间都存在边,则称该图为 无向完全图
2.图形化解释
如下图所示即为一个无向完全图:
五: 有向完全图
1.定义
在有向图中,如果任意两个顶点之间都存在 方向互为相反 的两条弧,则称该图为 有向完全图
2.图形化解释
如下图所示即为一个有向完全图:
-
23.有向图和无向图
2017-09-04 20:29:24 -
有向图与无向图判断有环
2015-11-17 12:38:59最近开始认真学习算法,用的是...而判断环问题又分为有向图与无向图,我会分别对无向图和有向图判断环问题进行阐述,然后比较他们之间的不同. 首先介绍一下无向图,无向图的边没有方向,或者说每一条无向图的边都是双 -
有向图和无向图的相关概念
2020-04-29 15:44:42图的定义: 图在数据结构中是中一对多的关系,一般分为无向图与无向图 常用 邻接矩阵 或者 邻接链表 来...对于图7-1所示的无向图G1和有向图G2,它们的数据结构可以描述为: G1=(V1,E1), 其中 V1={a,b,c,d... -
有向图的环和有向无环图
2018-07-25 07:10:00本篇主要分享关于有向图的环和有向无环图(DAG,估计做大数据的同学到处都可以看到),所以相关概念我就不做详细介绍了。 用有向图中各个节点代表着一个又一个的任务,... -
有向图和无向图以及拓扑的复习
2018-10-14 17:43:361)关于有向图,百科中是这样描述的:一个有向图D是指一个有序三元组(V(D),A(D),ψD),其中ψD为关联函数,它使A(D)中的每一个元素(称为有向边或弧)对应于V(D)中的一个有序元素(称为顶点或点)对。 理解:如图D,... -
概率图模型之有向图与无向图
2016-06-12 20:32:18图模型用图结构描述随机变量之间的依赖关系,结点表示随机变量,边表示随机变量之间的依赖关系,可以是有向图和无向图。 一 无向图模型 无向图模型又叫马尔可夫网络、马尔可夫随机场,是关于一组有马尔可夫性 -
有向图删除边得到有向无环图
2019-04-26 00:30:05给定用邻接表表示的有向图G,从G中删除一些边,将G转化为有向无环图 具体思路 判定是否是有向图可以通过DFS或者拓扑排序来完成,笔者采用的是DFS的方式。具体的思路为:对图进行DFS,在每一个没有被访问的过的结点做... -
有向图 无向图 欧拉路 欧拉图
2018-11-03 19:56:05如果图G中的一个路径...有向图: 欧拉回路:图连通,所有节点的出度等于入度。 欧拉路:图连通,所有节点的出度等于入度;或者除两个节点以外的其余节点的入度和出度都相等,且这两个节点一个满足出度-入度==1,... -
有向图的连通性
2020-04-21 16:17:47文章目录 无向图: ...单向连通:有向图中,任意结点对中,至少从一个到另一个是可达的,就是单向连通。 强连通:有向图中,强连通图是任意对中都互相可达。 PS:弱连通图不一定是单向连通。 ... -
【图结构专题】有向图
2018-03-19 22:00:26有向图 一. 有向图的相关术语 在有向图中,边是单向的:每条边连接的两个顶点都是一个有序对,它们的邻接性是单向的。我们开发过程中碰到的很多场景都是有向图:比如任务調度的依赖关系,社交网络的任务关系等等... -
有向图是否有环,无向图是否有环
2014-11-25 06:05:43有向图是否有环,无向图是否有环 detect -
算法——图之有向图
2017-05-24 20:02:431.有向图的表示 有向图的可达性 有向图的路径 2. 判断有向图中是否有环 拓扑排序,优先级限制下的调度问题 3. 有向图的强连通性 有向图的可达性 有向图的表示 和无向图中的一样,我们也采用邻接表矩阵的方式来... -
有向图邻接表
2019-01-11 18:18:09邻接表有向图是指通过邻接表表示的有向图。 有向图可以理解为一种数据结构,处理特定场景的问题会比较简单 对于java来说,用map实现有向图比较便于进行查找操作。 实现有向图这种数据结构并不困难,难的是如何... -
数据结构 c语言 有向图和无向图邻接表的建立、插入、和删除操作
2020-05-05 16:12:00c语言实现数据结构中有向图和无向图邻接表的建立、插入、删除操作 -
DFS应用——遍历有向图+判断有向图是否有圈
2015-11-24 09:56:17【0】README0.1) 本文总结于 数据结构与算法分析, 源代码均为原创, 旨在 理解 “DFS应用——遍历有向图+判断有向图是否有圈” 的idea 并用源代码加以实现 ; 0.2) 判断有向图是否有圈的rule—— 一个有向图是无... -
由邻接矩阵画有向图、无向图
2017-07-19 10:39:08由邻接矩阵画有向图、无向图 由邻接矩阵画有向图的逻辑如下: 设邻接矩阵的行(列)数为N,矩阵中非零元素的个数为M,画布宽为W、高为H 1、有向图顶点数为N、有向边数为M,问题转化为:画正N边形的所有顶点、以及顶点... -
有向图中有向环检测
2018-01-02 10:55:08寻找有向图中是否存在有向环是判定一个任务优先级问题的前提边的类型从某个点开始的深度搜索过程中遇到了后向边,可作为找到有向环的标志代码实现private boolean[] onStack = new boolean[V];public void dfs(int s... -
Python 邻接矩阵实现无向图、有向图的三种方法,并绘图显示
2017-11-12 17:39:46网上查了很多资料,发现主要是使用邻接表来实现图,并进行遍历的。而采用邻接矩阵的就非常少...不想看的可以直接下载:python 邻接矩阵三种方法实现有向图、无向图,并绘图显示不废话。上代码首先图类 class Graph_Matr -
判断无向图/有向图中是否存在环
2019-02-03 11:54:50本文主要针对如何判断有向图/无向图中是否存在环的问题进行简单的论述。 一 无向图 1.利用DFS进行判断 利用DFS判断有向图是否存在环,是最为常用的一种方法,虽然这种方法很常用,但可参考的代码的实现比较少,... -
有向图及拓扑排序
2018-10-20 23:06:53有向图 在无向图中,边没有方向,两条边之间的顶点是单向可达的,而有向图的边是单向的。虽然边的性质不同,但我们仍然可以用邻接表来表示有向图。对有向图的结构定义如下: #include <map> #include <... -
Gephi画无向图和有向图(显示节点和边序号)
2019-11-28 16:43:37Gephi画无向图和有向图(显示节点和边序号) 数据形式 如果画无向图只要把Type这一列设置成undirected,不填入数据默认是directed 导入数据以后就可以设计节点以及边的属性了,如下: 显示的有向图如下: ... -
算法——图之加权有向图
2017-05-27 15:26:17这篇讨论加权有向图。 加权有向图是在有向图的基础上,边的赋予权重信息的。 加权有向图有很多应用。最典型的就是最短路径问题。我们日常生活中也经常遇到这种问题,例如从一个点出发,到达另外一个点,怎么过去才是... -
有向图、无向图是否有环的判断
2016-07-21 20:54:32今天在做数据库的调度冲突可串行性判别的程序,中间要用到有向图中环判定的问题,特摘录如下。这些算法和思想都是来自网上的,在此感谢原作者! 先介绍一下无向图的判断算法,这个比较简单: 判断无向图中是否... -
无向图与有向图的深度优先与广度优先算法
2018-07-05 19:19:04无向图与有向图的深度优先与广度优先算法 -
Python绘制拓扑图(无向图)、有向图、多重图。最短路径计算
2019-10-08 16:55:45前言: 数学中,“图论”研究的是定点和边组成的图形。 计算机中,“网络拓扑”是...有向图 两个节点之间只有一条线相连接,且有方向。方向可以单向,也可以双向。 多重图 两个节点之间只有多条线相连接。 ... -
概率有向图模型
2017-03-05 21:11:44个人感觉概率有向图模型最大的意义在于:一个特定的有向图表示将联合概率分布分解为条件概率分布乘积的形式。 2. 概念 2.1 等价概念 概率有向图模型、贝叶斯网络(Bayesian network)、信念网络...