3图论.doc
文本预览下载声明
3 图论
图论在计算机科学、信息科学、人工智能、网络理论、系统工程、控制论、运筹学和经济管理等领域有着广泛的应用。但很多图论问题虽易表达,却难以求解,其中有相当多的图论问题均属NP完全问题。本章主要介绍工程实用简单图论问题的并行算法及其MPI编程实现,包括传递闭包、连通分量、最短路径和最小生成树等。
传递闭包
设A是一个含N个顶点的有向图G的布尔邻接矩阵(Boolean Adjacent Matrix),即元素aij=1当且仅当从顶点i到j有一条有向边。所谓A的传递闭包(Transitive Closure),记为A+,是一个N×N的布尔矩阵,其元素bij=1当且仅当:①i=j;或②从i出发存
显示全部