猫史档案馆

图是树的延伸。树是从根节点分裂到它的子节点，又分裂到它的子节点……而图允许出现回路，换个话说就是可以从子“节点”到父“节点”。图的应用比树更加广泛，比如可以设计地图、项目安排等。

树中的点叫做“节点”，图中的点叫做“顶点”，顶点一般记为“V”。当顶点非常多时，可以记为“V1”“V2”“V3”等。

假设有一个图中有两个顶点（以下分别称为V1和V2），这两个顶点中间有一条线，换个话说就是V1可以到V2。如果V1可以到V2且V2可以到V1，这个图就称为“无向图”。V1和V2中间一定是要用一条线连接，这条线就叫做“边”。如果V1可以到V2，但反之V2不可以到V1，这个图就被称为“有向图”，因为它有方向。有向图的边一般记为箭头状，表示一个顶点可以到另一个顶点但反之不行。

有的时候，图的边上会有数，这些数我们称它为“权”，可以表示在地图里两个地点的距离、项目中两个项目完成的时间差等等。如果它是个无向图且有权，我们称它为“带权无向图”；如果它是个有向图且有权，我们称它为“带权有向图”。

树的保存方法可以用二维列表，图的保存方法有很多，对于kitten（scratch）来说，最快捷的方法是邻接矩阵。邻接矩阵也是一个二维列表，下面举一个例子说明：

起\终　V1　V2　V3
V1 　　0　 1　 1
V2 　　1　 0　 1
V3 　　1　 1　 0

第一行和第一列在kitten（scratch）里编程的时候不用写的，这里只是让大家看的清楚一点才写的。

V1行V1列为0，表示V1不能到V1；V1行V2列为1，表示V1可以到V2。

这是一个无向图的邻接矩阵，如果用这些数据来生成图的话，生成出的是一个无向的三角形。

可以看到，无向图的邻接矩阵是沿对角线对称的，表格的行列必定相同，因为无向图没有方向。

再来看看一个有向图的邻接矩阵：

起\终　V1　V2　V3
V1 　　0　 0　 1
V2 　　1　 0　 1
V3 　　0　 1　 0

这个有向图画出来的依然是个三角形，只不过有方向了。

V1行V2列为0，但V2行V1列为1，V2可以到V1但V1不可以到V2，这就有方向了。

再来看看带权有向图的邻接矩阵。

起\终　V1　　V2　　V3
V1 　无穷　 无穷　无穷
V2 　　3　　无穷　　5
V3 　无穷　 　1　　无穷

（无穷符号打不出来，Infinity太占格子，所以就用无穷二字代替了）

这里对互不能到达的顶点设为无穷，能到达的顶点设为它们的权。

另外，无穷不能替换为0，否则有可能表达权数为0，有可能表达无法到达，存在歧义，所以就用无穷代替。

下一次教程帖，我们来讲如何生成随机的带权有向图！