C++

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

_Redstone_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;
}

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

发表回复