基于布尔矩阵运算的有向图可达矩阵.pdfVIP

维普资讯 大 庆 石 油 学 院 学 报 第3O卷 第6期 2006年 12月 JOURNAlOFDAQING PETROlEUM INSTITUTE Vo1．3O No．6 Dec． 2006 基于布尔矩阵运算的有向图可达矩阵 庞倩超 (1．浙江大学 计算机学院，浙江 杭州 310000； 2．浙江纺织服装职业技术学院 机电与信 息工程分院，浙江 宁波 315000 ) 摘 要：可达矩 阵是判别一个有向图是否为强连通 图或弱连通 图的有效工具．利用布尔矩 阵的运算性质给 出了计算 有向图可达矩 阵的方法 ，该方法计算简便． 关 键 词 ：有 向图；邻接矩阵；布尔矩阵；可达矩阵 中图分类号：0241．6 文献标识码：A 文章编号 ：1000—1891(2006)06—0099—02 和 1 0 可达矩阵是判别一个有向图是否为强连通图或弱连通 图的有效工具 ，求得有 向图可达矩阵的方 ．． 1●， 法有很多 s州，如利用深度优先有哪些信誉好的足球投注网站算法，利用邻接矩阵和循环法等 ，其方法均显得烦琐．笔者利用布尔矩 阵的运算性质求有向图可达矩阵． 1 有 向图可达矩阵的定义 对有向图G一(V，E)，IVI一”，IEI— ，且V一{l，2，…， }，E一{( ， I ， ∈V}，其中，”为 顶点个数，m为边数．有序对 (i，，表示顶点 到 有一条有向边． 可用一个”×”矩阵 其 一 ∈E， 称A为有向图G的 邻接矩阵． 在有向图G中，两顶点 ，∈V，且睁 ，有一条有向路径 一 ：，：，…， 一 ，其中 ∈V，k一0，1，…，m；(吐l，：∈E，一 1，2，…，m． 则称从顶点 到顶点 ，是可达的． 约定 到自己()可达 ，则可定义 ”×”阶矩阵R一 ( )，其中 f1， 当 到 ，可达， 1≤ i，≤ ”， 10， 其他， R 一 三|『j1R，一 a)G(1b)G(2 图 1 可达矩阵路径 2 有 向图可达矩阵的计算 髁 一 榷 肌 鼬 来定义矩 ． )_J为单位 表示 收稿 日期 ：2006—02—23；审稿人 ：孔令彬 ；编辑 ：王文礼 作者简介：庞倩超(1966一)，女 ，硕士生，副教授 。主要从事软件开发与基础理论方面的研究 · 99 · 维普资讯 大 庆 石 油 学 院 学 报 第 3O卷 2006年 长度为 0的路只有 自己到 自己)，A“一A(A为 G的邻接矩阵)． 计算A ．