【读书笔记】算法漫步 第7章

问题8 连通

 图在数学上的表示

相邻、邻居、度数

道（walk）、径（trail）、路（path）

 

连通问题：一个图是连通的，当且仅当其任意两个节点之间都存在一条路。

 

这个问题，还可以推论两个问题

1：一个图是连通的，当且仅当其任一个节点与其他所有节点之间都存在路。（这也是判断图是否连通的算法中，常用的认识）

2：一个不连通的图，包含多个连通分量，每个连通分量即其中尽可能打的连通子图。

 

那从计算机处理图的角度的最大特点是什么呢？就是要知道，图在计算机（程序）内部是如何表示的。因为目前计算机存储的特点，所以计算机当前能够存储的图（数据）和人脑、数学中图是不一样的。那么要学习计算机的图算法，首先要学习图在计算机中的表示和存储。要认识到，所有计算机的图算法（程序）都是基于某种图的计算机表示的。

 

本章介绍了计算机表示图的最常见的两种表示形式：“邻接矩阵”和“邻接表”。

 

然后介绍了基于邻接矩阵判断一个图是否连通两个算法：矩阵乘幂法和行列合并法，这个需要一些数学知识。如果有这方面的数学基础，实现这两个算法的程序设计技巧要求并不高（程序就是实现数学方法而已，知道数学方法就能设计出算法）。

 

最后介绍了一个基于邻接表求解图是否连通的一个算法：这个算法是基于图遍历算法的思路来实现的，不仅需要图的数学知识，还需要掌握图遍历算法，这需要算法设计基础，学习和实现起来难度更高一些。

 

 

【作者感受】

本书有多个问题，都和 图有关

这一章介绍的 连通，也是图论中的一个重要性质和研究对象。

图（注意，图不是图像哈）从某种角度来说是可见的，可以从形象思维的角度理解，但是更多的时候，图数据是看不见的（注意，让图数据可视化是图的一个重要研究方法），所以图的学习需要抽象思维，这也是图很难学的原因吧。

 

图论是数学中的一个重要分支，图算法是计算机算法领域中的一个重要组成部分，两者有关联，但是也不完全一致。这一点，也要有认识。