图论

图的存储

1.邻接矩阵

用二维数组存储即可，int g[N][N];
无向图：g[i][j]=g[j][i],g[i][i]=0;
有向图：g[i][j]!=g[j][i],

缺点：

1. 空间复杂度太高，只适合于存储稠密图，
2. 不能存储重边

2.邻接表

struct edge{//边类型
    int from,to,w;
    edge(int a,int b,int c){
        from=a;to=b;w=c;
    }
};
vector<edge> e[N];

        //初始化
    for(int i=1;i<=n;i++){
        a[i].clear();
    } 
    //存边
    e[a].push_back(edge(a,b,c));//起点a,终点b，结点权值c 
    //查询u结点的每一个邻居
    for(int i=0;i<e[u].size();i++){
        ...
    }