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


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

　　有向图的数据结构

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

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


　　这个方法是把节点直接用有向的边来连接两个节点，从而逐步构建出一个真正的有向图。由于每一个节点都是一个袋式结构的所以可以把他可以通向的每一个节点加入到他这个袋子里。


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

　　有向图的可达性

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

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


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


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


　　使用场景我们会在下章和大家分析和描述，大致代码就是这个样子咯  谢谢大家的支持。
第四十一届CIO班招生
国际CIO认证培训
首席数据官（CDO）认证培训

免责声明：本网站（http://www.ciotimes.com/）内容主要来自原创、合作媒体供稿和第三方投稿，凡在本网站出现的信息，均仅供参考。本网站将尽力确保所提供信息的准确性及可靠性，但不保证有关资料的准确性及可靠性，读者在使用前请进一步核实，并对任何自主决定的行为负责。本网站对有关资料所引致的错误、不确或遗漏，概不负任何法律责任。
本网站刊载的所有内容（包括但不仅限文字、图片、LOGO、音频、视频、软件、程序等）版权归原作者所有。任何单位或个人认为本网站中的内容可能涉嫌侵犯其知识产权或存在不实内容时，请及时通知本站，予以删除。