C++ – 树与图的基础操作

点对点

建立一个数组,用下标表示不同的点,用其内容表示这个点所连接的点。例如数组名为graph,然后可以用graph[0] = 1表示0点可以通向1点。

其中,如果一个点可以连向多个点,可以使用二维数组存储,例如graph[0][0] = 1和graph[0][1] = 2表示0点所连接的点有1点和2点。通常,这个二维数组的第二维不会被填满,所以,可以使用向量作为第二维,像下面一样:

#include <vector>
using namespace std;
const int MAXN = 1e6 + 100;

int main() {
    vector<int> graph[MAXN]; 
    return 0;
}

这样的储存方式看起来像这样:

PS:这种方式不适合储存带权的图

邻接矩阵

用一个二维数组存放顶点间关系(边或弧)的数据,这个二维数组称为邻接矩阵。邻接矩阵又分为有向图邻接矩阵和无向图邻接矩阵。( 对无向图而言,邻接矩阵一定是对称的 )例如 graph[0][1] = 1 表示0点与1点之间有一条边,权为1。

在邻接矩阵中,自己到自己的权常常保存为0或负数,例如graph[0][0] = 0。如果两点之间没有边,常常保存成MAX_DATA。(MAX_INT = 0x7FFFFFFF)

using namespace std;
const int MAXN = 1e6 + 100;
const int MAX_INT = 0x7FFFFFFF;

int main() {
    int graph[MAXN][MAXN];
    return 0;
}

这样的储存方式看起来像这样:

发表回复