计算机图论教学课件.pdfVIP

3 图论 图论在计算机科学、信息科学、人工智能、网络理论、系统工程、控制论、运筹学和经 济管理等领域 着广泛的应用。但很多图论问题虽易表达，却难 以求解，其中 相当多的图 论 问题均属N P 完全 问题。本章主要介绍工程实用简单图论 问题的并行算法及其M P 1 编程 实现，包括传递闭包、连通分量、最短路径和最小生成树等。 1 . 1 传递闭包 设A 是一个含N 个顶点的 向图G 的布尔邻接矩阵 (Boolean Adjacent Matrix),即