图的储存方式

图是一个好东西，能够使用图来模拟或解决很多生活问题，同时在各大比赛上都少不了有关于图的问题.图是关系与顶点与边的，那么我们该如何来存入图的信息呢?

（1）直接存边

我们开一个数组，数组里每个元素是图的一条边。其中存的每一条边都包含这些信息：顶点 v 与 u , 边的权值。

这就用到结构体数组，对于无向图，只需要存两个顶点 , 有向图的话需要区分起点、终点。

// 直接存边 
struct edge{
    int start; // 起点
    int to;    // 终点
    int cost;  // 花费(权值)
}G[MAXN];

这样做有个缺点 , 每次想要知道两个点之间是否有连边（或者说一条边是否存在），都需要遍历整个数组进行查找.而且如果没有进行排序的话 , 还不能使用二分查找( O(log n) ) , 只能顺序查找 ( O(n) ) , 对于需要多次查找的情况 , 显然是不合适的 . 但在使用 Kruskal 算法求最小生成树的时候能用到这种方法。

应用：

1. 由于直接存边的遍历效率低下，一般不用于遍历图。

2. 在 Kruskal 算法 中，由于需要将边按边权排序，需要直接存边。

3. 在有的题目中，需要多次建图（如建一遍原图，建一遍反图），此时既可以使用多个其它数据结构来同时存储多张图，也可以将边直接存下来，需要重新建图时利用直接存下的边来建图。

（2）邻接矩阵

邻接矩阵的英文名是 adjacency matrix。它的形式是 bool adj[n][n] , 这里需要存 n 个节点，adj[x][y] 表示节点x与节点y 之间是否有边，如果边有权值的话 , 用 int adj[n][n] 直接把边权存进去。

无向图需要 x 与 y 有边则需要存 adj[x][y] 与 adj[y][x] 表示有双向导通 , 有向图则 x -> y 则存 adj[x][y] 就行了 .

#include<bits/stdc++.h>

using namespace std;

int adj[MAXN][MAXN],n,m;  // n 为节点数 , m 为边数

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y,v;
        scanf("%d %d %d",&x,&y,&v);
        adj[x][y]=adj[y][x]=v;//向x,y间添加一个权值为v的边(无向)
        //有向图为adj[x][y]=v;
    }
    return 0;
}

它的优点是 , 在查询两点间是否有边时 , 时间复杂度为 O(1) , 但是缺点是它存边却是极占内存，它的空间(内存)复杂度是 O(n^2) . 对于一个稀疏的图（边相对于点数的平方比较少）来说，用邻接矩阵来存的话，成本偏高。

如果n*m超过3×1e7，内存就超过128MB了，所以当看到类似的 n,m=<1e4时就不要用邻接矩阵 , 需要考虑其他的存储方式。

（3）邻接表

邻接表英文名是 adjacency list . 邻接表是链状的，它实际上是一个离散化的邻接矩阵。edge[i] 代表第 i 号节点 , .to[] 表示到与别的节点联通的路径 ，.v[ ]是 i 到 edge[i].to[j] 号节点的权值， .len 用来标记一共有几个联通 i 号节点的边 (也称节点i的出度)

#include<bits/stdc++.h>
using namespace std;

struct node
{
    int to[1010];  //存储与当前节点相接的节点
    int v[1010];   //两节点间的边的权值
    int olen;      //出度
    //int ilen;      //入度 
}edge[1010];
int n,m;
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y,v1;
        scanf("%d %d %d",&x,&y,&v1);
        edge[x].len++;edge[y].len++;
        edge[x].to[edge[x].len]=y;edge[y].to[edge[x].len]=x;
        edge[x].v[edge[x].len]=edge[y].to[edge[x].len]=v1;//向x,y间添加一个权值为v的边(无向)
        /*有向图为
        edge[x].len++;
        edge[x].to[edge[x].len]=y;
        edge[x].v[edge[x].len]=v1;
        */
    }
    return 0;
}

应用：

1. 存各种图都很适合，除非有特殊需求（如需要快速查询一条边是否存在，且点数较少，可以使用邻接矩阵）。

2. 尤其适用于需要对一个点的所有出边进行排序的场合。

（4）链式前向星

本质上是用链表实现的邻接表，核心代码如下：

// C++ Version
// head[u] 和 cnt 的初始值都为 -1
void add(int u, int v) {
  nxt[++cnt] = head[u];  // 当前边的后继
  head[u] = cnt;         // 起点 u 的第一条边
  to[cnt] = v;           // 当前边的终点
}

// 遍历 u 的出边
for (int i = head[u]; ~i; i = nxt[i]) {  // ~i 表示 i != -1
  int v = to[i];
}