$$图的存储方式$$

• 矩阵存储
• 链表存储

其中矩阵存储有两种常见方法:

1. 二维数组。 对于稀疏图，空间消耗极大，一般不用
2. vector, 需要对vector的操作熟悉

//存储方式代码：
1. 二维数组

    g[MAXN][MAXN];
    g[i][j] --> i 指向 j

    2. vector

    初始化:
    vector<int> g[MAXN];

    g[u].push_back(v); --> u 指向 v

    for(int i = 0; i < g[u].size(); i++)    int v =  g[u][i];

    vector存储多种信息：

    struct Node{
        int v, w;
        ...
    }; 
    vector<Node>g[MAXN];

    //g[u][i] 每个 i 里面存了 v(指向的边) 和 w(权重) 
    g[u].push_back(Node(v,w));

    for(int i = 0; i < g[u].size(); i++){
        int v = g[u][i].v;  // 指向的边 
        int w = g[u][i].w;  // 边的权重 
    }

单链表存储:

e[i] –> 第 i 节点的值 ne[i] –> 第 i 节点指向下一个节点的指针 h[i] –> 节点 i 的头

//测试代码
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 +  5;

int e[N], ne[N], h[N], w[N], idx;
int n;

// 不加权边
void add(int x,int y){
    e[idx] = y; ne[idx] = h[x]; h[x] = idx++;
}

// 加权边
void add(int x,int y, int z){
    e[idx] = y; w[idx] = z; ne[idx] = h[x]; h[x] = idx ++ ;
}

int main(){
    memset(h, -1 ,sizeof h);

    cin>>n;

    for(int i = 1, x, y; i <= n; i ++){
        cin>>x >> y;
        add(x,y);
    }

    for(int i = 1,x; i <= n / 2; i++,puts（""){
        cin>>x;
        for(int j = h[x]; j != -1; j = ne[j])
            cout << e[j]<<' ';
    }

    return 0;
}