邻接表

在图的描述中，经常会用到邻接表，有时我们会用到邻接矩阵来保存图的边和权值等信息，但是这回产生\(N^2\)的空间复杂度，在数据量比较大的多数情况下，我们是无法存储的，所以这是就需要用到空间复杂度为\(N\)的邻接表来存储图。

存储

对于邻接表的存储方式，我们除了保存边的三个数组\(u,v,w\)之外还需要两个数组\(first,next\),其中\(first\)用来保存与第i号顶点相连的第1条边是第k号边（\(first[i]=k\)），\(next\)数组用来保存连在同一个顶点上的边的先后关系，\(first,next\)均初始化为-1。

例：

4 5//点数和边数
1 4 9//边的描述，链接u顶点和v顶点，权值为w
4 3 8
1 2 5
2 4 6
1 3 7
序号 \(u\) \(v\) \(w\) \(first\) \(next\)
1 1 4 9 5 -1
2 4 3 8 4 -1
3 1 2 5 -1 1
4 2 4 6 2 -1
5 1 3 7 -1 3

每次加入一条边，如果这条边是以左顶点开始的第一条边，那么此时的\(next\)为-1，\(first\)为此时边的编号，如果不是第一条边，那么\(next\)为者条边的坐定点对应的上一条边的编号也就是\(first\)，而\(first\)修改为此时边的编号。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

const int maxn=11111;

class AdjacencyList {
private:
    int w[maxn],v[maxn],u[maxn],first[maxn],nxt[maxn];
    int n,m;
public:
    void GetGraph();
    void TraverseG();
};

void AdjacencyList::GetGraph() {
    memset(first,-1,sizeof(first));
    memset(nxt,-1,sizeof(nxt));
    cin >> n >> m;
    for(int i=1; i<=m; i++) {
        cin >> u[i] >> v[i] >> w[i];
        nxt[i] = first[u[i]];
        first[u[i]] = i;
    }
    return;
}

void AdjacencyList::TraverseG() {
    for(int i=1; i<=n; i++) {
        int k = first[i];
        while(k!=-1) {
            cout << u[k] << " " << v[k] << " " << w[k] <<endl;
            k = nxt[k];
        }
    }
    return;
}

int main(int argc, char const *argv[])
{
    freopen("in.in","r",stdin);
    AdjacencyList mygraph;
    mygraph.GetGraph();
    mygraph.TraverseG();
    return 0;
}