在刷题的过程中经常会碰到一些关于图论的问题，下面我将根据自己刷题的经验来对这些问题做一个总结。
解决图论中的问题首先要解决的问题就是图的表示方法这一问题，图的表示方法主要有两种，一种使用链接表的方法来表示，另一种是用链接矩阵的方法来表示。在解题的过程中我用的几乎都是用邻接矩阵的方法来表示。用邻接矩阵来表示的话既可以用二维数组也可以用二维向量来表示。用二维向量来表示的好处是，如果题目中没有给出边的权重，只是让我们求解图的连通性问题的话，我们可以不指定vector数组的大小，例如：vector[i].push_back(x)，以此来表示i与x相连。这样来表示的话又有一些链接表的感觉。
就PAT考察的范围，以及刷题的经验来看，这里面涉及到的算法主要包括DFS、BFS、并查集、Dijkstra（最短路径）、Kruskal（最小生成树）以及求连通分量的问题。
原文：https://www.cnblogs.com/ruruozhenhao/p/13198829.html