当前位置:首页 > 开发 > 编程语言 > Java > 正文

java 图论二 有向图遍历 warshall

发表于: 2012-11-21   作者:blackproof   来源:转载   浏览次数:
摘要: java的有向连通图遍历   有向连通图 顶点: A B C D E                 连通性表 AC BACE C DEC EC   WarShall算法 算法思路: 输入联通矩阵,生成其图的传递闭包。传递闭包是不考虑路径,当X节点能到达Y节点时,则传递闭包包括XY,X

java的有向连通图遍历

 

有向连通图 顶点: A B C D E

                连通性表 AC BACE C DEC EC

 

WarShall算法

算法思路:

输入联通矩阵,生成其图的传递闭包。传递闭包是不考虑路径,当X节点能到达Y节点时,则传递闭包包括XY,XY为可通。在传递闭包中,有矩阵ajm[X][Y]=1;

判断是否有通路,根据如果矩阵中[X][Y]为1,则通路,如果[X][Y]为0,但[X][K]=1并且[K][Y]=1,则[X][Y]通路。此时只完成一次合并。得出一次合并的传递闭包。

算法规则:

[X][Y]是否为1,遍历所有K,如何[X][K]=1并且[K][Y]=1

 

warshall算法的关键代码片段:

 

       for (int k = 0; k < N; k++) {  
            for (int i = 0; i < N; i++) {  
                for (int j = 0; j < N; j++) {  
                    M[i][j] = M[i][j] + M[i][k] * M[k][j];  
                }  
            }  
        }  

 

java 图论二 有向图遍历 warshall

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
本章是通过C++实现邻接表有向图。 目录 1. 邻接表有向图的介绍 2. 邻接表有向图的代码说明 3. 邻接
前面分别介绍了邻接矩阵有向图的C和C++实现,本文通过Java实现邻接矩阵有向图。 目录 1. 邻接矩阵有
前面分别介绍了邻接表有向图的C和C++实现,本文通过Java实现邻接表有向图。 目录 1. 邻接表有向图的
本章是通过C++实现邻接矩阵有向图。 目录 1. 邻接矩阵有向图的介绍 2. 邻接矩阵有向图的代码说明 3.
求(有向)图中任意两点间所有路径 1建图: 图类中包括如下信息:顶点集合,邻接矩阵。 节点类中包
图的广度优先算法是图的基本算法,也是最小生成树以及单源最短路径算法的基础。最近把广度优先遍历
图的广度优先算法是图的基本算法,也是最小生成树以及单源最短路径算法的基础。最近把广度优先遍历
邻接矩阵有向图的介绍 邻接矩阵有向图是指通过邻接矩阵表示的有向图。 上面的图G2包含了"A,B,C,D,E,
邻接表有向图是指通过邻接表表示的有向图。 上面的图G2包含了"A,B,C,D,E,F,G"共7个顶点,而且包含了
简介 前面讨论的很多文章里,都是针对无向图进行的分析。无向图的一个特性就是其中一旦两个节点a和b
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号