图论之图的存储及遍历

今天开始把图论的总结大坑填了

什么是图？

一堆点被很多线连起来，组成的东西叫做图(严格定义请自行查找)

图的存储

1、邻接矩阵 - 不存在实现难度的存图结构

很明显我们只需要把所有的点标号，建立一个二维数组，假设为 arr ，那么假设 1、2 两点相连，则 arr[1][2] = arr[2][1] = 1 即可，对于有向图，后者不需要置为 1;

代码示例

int arr[MAXN][MAXN];
int m; // 边的个数
// u、v 代表相连的两点，w 代表权值
int u, v, w;
for(int i=1; i<=m; i++) {
    cin >> u >> v >> w;
    arr[u][v] = arr[v][u] = w;
}

2、链式前向星 - 最常用的数据结构之一