谈谈图

今天说一个在《数据结构》这么课程中特别重要的数据结构，即图，其具体形象如下图所示。

图具有2种表示方式，分别是邻接矩阵和连接表。

先说说邻接矩阵，如下图所示，假如图的节点数为n，其实就是一个二维数组arr[n][n]，若节点i和节点j之间有连线时，arr[i][j]=1，同理，在无线图中，此时节点j和节点i之间也是有连线的，arr[j][i]=1，反之，若节点i和节点j之间没有连线时，arr[i][j]=0，同理，在无线图中，此时节点j和节点i之间也是没有连线的，arr[j][i]=0。在下图可以看出，i节点和i节点之间是默认没有连线的，arr[i][i]=0。另外，这个矩阵关于对角线对称。

看看代码。

如上图所示，adjIterator为SparseGraph的内部类，这个类是用来对SparseGraph遍历的，上述代码已经有详细注释了，这里就不进行赘述了。

邻接表，如下图所示，其实就是一个链表数组，数组的每一个元素都是一个链表，而每个链表的表头都是一个节点，其链表中的元素都是与这个链表的表头即这个节点相连的节点。若节点i与节点j、k、z有直线相连，而在以i为表头的链表中，存在着j、k、z这3个元素。

邻接表相对于邻接矩阵相比，是节省了不少的空间，但这也并非意味着邻接矩阵毫无用武之地。一般来说，邻接表适合表示一个稀疏图，而邻接矩阵适合表示一个稠密图。

看看代码。

如上图所示，DenseGraph也有adjIterator这个内部类内部类，这个类是用来对DenseGraph遍历的，上述代码已经有详细注释了，这里就不进行赘述了。