C++ 数据结构提高

神不在的世界

1.1 图的定义和相关术语

什么是图？直白地说，就是类似于地图的东西，例如下图展示的学生生活路线就是一个图。



抽象出来看，图由顶点（Vertex）和边（Edge）组成，每条边的两端都必须是图的两个顶点（可以是相同的顶点）。而记号G（V，E）表示图G的顶点集为V、边集为E。下图是一个抽象出来的图。


一般来说，图可分为有向图和无向图。
有向图的所有边都有方向，即确定了顶点到顶点的一个指向；而无向图的所有边都是双向的，即无向边所连接的两个顶点可以互相到达。
在一些问题中，可以把无向图当作所有边都是正向和负向的两条有向边组成，这对解决一些问题很有帮助。
下图是有向图和无向图的举例。


顶点的度是指和该顶点相连的边的条数。
特别是对于有向图来说，顶点的出边条数称为该顶点的出度，顶点的入边条数称为该顶点的入度。例如上图的无向图中，V1 的度为 2 ，V2 的度为4；有向图例子中，V2 的出度为 1 、入度为 2 。
顶点和边都可以有一定属性，而量化的属性称为权值，顶点的权值和边的权值分别称为点权和边权。
权值可以根据问题的实际背景设定，例如点权可以是城市中资源的数目，边权可以使两个城市之间来往所需要的时间或花费。
1.2 图的存储

一般来说，图的存储方式有两种∶邻接矩阵和邻接表。这两种存储方式各有优势，需要在不同的情况下选择使用。
1.2.1 邻接矩阵

设图 G(V,E) 的顶点标号为 0，1，…，N-1，那么可以令二维数组 G[N][N] 的两维分别表示图的顶点标号，即如果  G[j] 为1，则说明顶点 i 和顶点 j 之间有边；如果 G[j] 为 0，则说明顶点 i 和顶点 j 之间不存在边，而这个二维数组 G[][] 则被称为邻接矩阵。
另外，如果存在边权，则可以令 G[j] 存放边权，对不存在的边可以设边权为 0、-1 或是一个很大的数。
下图是一个作为举例的无向图以及对应的邻接矩阵（边权为 0 表示不存在边），显然对无向图来说，邻接矩阵是一个对称矩阵。


虽然邻接矩阵比较好写，但是由于需要开一个二维数组，如果顶点数目太大，便可能会超过题目限制的内存。因此邻接矩阵只适用于顶点数目不太大（一般不超过 1000 ）的题目。
1.2.2 邻接表

设图 G(V,E) 的顶点编号为 0，1，…，N-1，每个顶点都可能有若干条出边，如果把同一个顶点的所有出边放在一个列表中，那么 N 个顶点就会有 N 个列表（没有出边，则对应空表）。
这 N 个列表被称为图 G 的邻接表，记为 Adj[N] ，其中 Adj 存放顶点i的所有出边组成的列表，这样Adj[0] ，Adj[1]，Adj[N-1] 就分别都是一个列表。


由于列表可以用链表实现，如果画出上图对应的邻接表，就会得到图上图。


其中 Adj[0] 用链表连接了两个结点，每个结点存放一条边的信息（括号外的数字是边的终点编号，括号内的数字是边权），于是 0 号顶点有两条出边：
一条的终点为 1 号顶点（边权为 2 ）；
另一条边的终点为4号顶点（边权为 1 ）。
而对 Adj[4] 来说，它表示 4 号顶点的三条出边的信息，这三条出边的终点分别是 0 号顶点、1 号顶点、3 号顶点，边权分别为1、2、1。
对初学者来说可能会不太容易很快就熟练使用链表来实现邻接表，因此此处介绍另一种更为简单的工具来实现邻接表：vector ，它能让初学者更快上手并易于使用，且不易出错。
由于 vector 有变长数组之称，因此可以开一个 vector 数组 Adj[N] ，其中 N 为顶点个数。这样每个 Adj 就都是一个变长数组 vector ，使得存储空间只与图的边数有关。
如果邻接表只存放每条边的终点编号，而不存放边权，则 vector 中的元素类型可以直接定义为 int 型，如下所示：
vector<int> Adj[N];
下图为把上图中的邻接表采用 vector 数组进行存储的情况（只存放边的终点编号）。



如果想添加一条从 1 号顶点到达 3 号顶点的有向边，只需要在 Adj[1] 中添加终点编号 3 即可，代码如下所示（如果是无向边，就再添加一条从 3 号顶点到达 1 号顶点的有向边）：
Adj[1].push_back (3);如果需要同时存放边的终点编号和边权，那么可以建立结构体 Node ，用来存放每条边的终点编号和边权，代码如下所示：
struct Node
{
    int V;         //边的终点编号
    int w;        //边权
};
这样 vector 邻接表中的元素类型就是 Node 型的，如下所示：
vector<Node> Adj [N];
此时如果想要添加从 1 号到达 3 号顶点的有向边，边权为 4 ，就可以定义一个 Node 型的临时变量 temp ，令 temp.v=3、temp.w=4，然后把 temp 加入到 Adj[1] 中即可，代码如下所示：
Node temp;
temp.v = 3;
temp.w = 4;
Adj[1].push_back(temp);
当然，更快的做法是定义结构体 Node 的构造函数，代码如下所示：
struct Node
{
    int v,w;
    Node(int _v,int _w):V(_v),w(_w) {} //构造函数
}

这样就能不定义临时变量来实现加边操作，代码如下所示：
Adj[1].push back(Node (3,4));

于是就可以使用 vector 来很方便地实现邻接表，在些顶点数目较大（一般顶点个数在1000 以上）的情况下，一般都需要使用邻接表而非邻接矩阵来存储图。