当前位置:首页 > 开发 > 编程语言 > 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

    震惊

    震惊

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号