图论基础

今天，我们大家来讨论的数据结构为：图结构。图论是计算机科学中非常重要的内容。

首先，让我们来了解一下什么是图论：图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。一个图就像下图所示。

节点和节点之间用边连接起来，以此用来抽象的表示我们现实生活中的情况。例如：我们可以用来模拟交通运输，点为城市，点之间的边为城市之间的距离。又比如对社交模式来说，每个点代表一个用户，而边代表用户之间是否为好友。甚至，在闹区的活动的研究中，每一个点代表大脑之中的一个脑区，而边代表脑区之间的信息传递。

图根据边的方向性可以分为有向图和无向图两种。无向图就是边是没有方向的，比如两个人之间的边代表的好友关系就是不存在方向性的。而对于有向图来说，就是图中的边是具有方向性的。例如在城市之间，边可以代表城市之间的单行道，只能从一个城市转移到另一个城市。

另外，无向图是一种特殊的有向图，即一条无向边可以表示为两条方向相反的有向边，如下图所示：

另外，根据图中边是否带有权值，我们还可以把图分为有权图和无权图。所谓的权我们可以理解为一个数值，即节点和节点之间的边有没有一个数值与之对应。例如，两个用户之间的边代表两人是否为好友时，此时的边为无权图。如果两个用户之间的边代表用户之间的亲密度时，则此时边就具有了具体的数值含义，即权值，这时候图就为有权图。例如下图的城市交通图中，节点就代表城市，边就代表两个城市之间的距离或者两个地点之间的运输费用。

对于下面这张图中，它可以表示为3个图，

也可以表示为1个图，比如把节点比作人把边比作朋友关系，

则下图表示存在着三个小团体。

在图的边种类中，还存在着自环边和平行边。

举个例子，平行边就好比城市之间的道路不仅仅只有一条道路，

可以有多条道路从一个城市到另一个城市。

在后面的图的算法中，我们暂时不涉及自环边和平行边的讨论。