有向图之数据类型和可达性分析

本篇主要讲有向图的两个方面,1、有向图的数据类型,2有向图的可达性分析。要是了解的同学欢迎讨论 。当然拉觉得无趣的也可以跳过。

在我们生活中常见的图数据结构除了无向图以外,还有有向图,这两者的区别就是我无向图向连的两个节点,是可以互相访问的,而再有向图中相连的两个节点只能从其中一个访问被指向的另一个节点。例如儿子和爸爸,你不可能让爸爸叫儿子爸爸,只能儿子叫他爹叫爸爸。

有向图的数据结构

有向图的叔叔类型主要描述有向图的如何用java代码实现的一个过程,方便大家理解后面关于有向图的内容。

这一块是他对应的构造方法,这是以一个有V个节点的但没有边的有向图,他把每一个节点都放到一个袋数据结构中,而对目前这个有向图来说他只有一些节点,而没有对应的节点之间的关系。这就需要我们下面的一个方法。

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 void addEdge(int v, int w) {
   adj[v].add(w);
   E++;
}

整个类最主要的方法就是这两个。靠他们就可以构造出以一个有向图。

有向图的可达性

有向图的可达性是为了解决一个节点是否可以通向另一个节点的问题。例如是否存在s到达给定顶点v的有向路径。

在可达性分析中运用的理念是标记-清除的过程。例如 我从a-》b。然后把b标记,然后去看b可以到达那些节点,并去标记由此,一个一个节点逐渐标记。按这个过程

这个方法的用处是出便利当前节点中的袋结构中的每一个节点看是否便利过要是没有便利过则递归调用dfs方法来对可到达的每一个点进行便利。从而可以看出v可以到达的是有节点。

private void dfs(Digraph G, int v) {
   marked[v] = true;
   for (int w : G.adj(v)) {
      if (!marked[w]) {
         dfs(G, w);
      }
   }
}

而可达性分析就是基于这个方法上上的从而找出s点所有可以直接到达的节点。

public DirectedDFS(Digraph G, int s) {
   marked = new boolean[G.V()];
   dfs(G, s);
}

使用场景我们会在下章和大家分析和描述,大致代码就是这个样子咯 谢谢大家的支持。

原文发布于微信公众号 - 大数据和云计算技术(jiezhu2007)

原文发表时间:2018-07-13

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏海天一树

小朋友学数据结构(16):基于邻接矩阵的的深度优先遍历和广度优先遍历

这两个图其实是一样的,只是画法不同罢了。第一张图更有立体感,第二张图更有层次感,并且把A点置为顶点(事实上图的任何一点都可以做为顶点)。

1.2K5
来自专栏数据结构与算法

3525:上台阶

3525:上台阶 总时间限制: 1000ms 内存限制: 65536kB描述 楼梯有n(100 > n > 0)阶台阶,上楼时可以一步上1阶,也可以一步上2阶...

3885
来自专栏偏前端工程师的驿站

(cljs/run-at (JSVM. :all) "一次说白DataType、Record和Protocol")

前言  在项目中我们一般会为实际问题域定义领域数据模型,譬如开发VDOM时自然而言就会定义个VNode数据类型,用于打包存储、操作相关数据。clj/cljs不单...

1978
来自专栏C语言及其他语言

[每日一题]C语言程序设计教程(第三版)课后习题4.9

题目描述 输入一个华氏温度,要求输出摄氏温度。公式为 c=5(F-32)/9 输出要求有文字说明,取位2小数。 输入 一个华氏温度,浮点数 输出 摄氏温度,浮点...

3096
来自专栏刘望舒

JNI的实现原理

JNI是Java Native Interface的缩写,它为java提供了调用C和C++代码的能力。java.lang包下的很多类都用到了native方法,比...

4582
来自专栏Java技术栈

跟我学 Java 8 新特性之 Stream 流(二)关键知识点

我们的第一篇文章,主要是通过一个Demo,让大家体验了一下使用流API的那种酣畅淋漓的感觉。如果你没有实践,我还是再次呼吁你动手敲一敲,自己实实在跑一遍上一篇的...

1414
来自专栏Core Net

一个插排引发的设计思想 (三) 委托与事件

2798
来自专栏用户2442861的专栏

互联网公司笔试常见陷阱

7.   阅读下面代码,程序会打印出来的值是(D)------------------------------(腾讯2014实习生笔试)

2493
来自专栏恰童鞋骚年

《你必须知道的.NET》读书笔记一:小OO有大智慧

此篇已收录至《你必须知道的.Net》读书笔记目录贴,点击访问该目录可以获取更多内容。

602
来自专栏程序员的诗和远方

谈谈 JavaScript 中的 TDZ

本来过年期间想写这个的,不过要准备些东西,一直没抽出时间,刚好今天有点空闲。上个月阮一峰阮老师在微博上发布了这样一条信息 于是评论区炸开了锅,很多人留言指出,这...

3297

扫码关注云+社区

领取腾讯云代金券