数据结构:邻接表

思路描述
当图是稀疏图时，使用邻接表来存储，可以大大提高效率。那要怎么做呢?使用5个数组来存储图的信息。假设一个图由n个顶点和m条边组成，数组a,b,c三个数组表示边的信息，对于第i条边，a[i]表示出发点,b[i]表示目标点,c[i]表示从a[i]到b[i]的权重。依次读入图的每条边的信息，数组a、b、c就保存了边的信息。还有一个问题就是边与边的关系也需要保存，要不然没办法遍历。数组last表示每个顶点的最后一条边，pre表示每个顶点的最后一条边的前一条边。对于last中的第i个数据last[i],就是第i个顶点的最后一条边的序号。pre[i]表示第i条边的前一条边的序号。

构建代码

vector<vector<int>>createGraph(vector<vector<int>> edges,int n,int m) {
    vector<int>a(m+1);vector<int>b(m+1);vector<int>c(m+1);
    vector<int>last(n+1);vector<int>previous(n+2);
    for(int i = 1;i < n+1;i++) {
        last[i] = -1;
    }
    for(int i = 0;i < edges.size();i++) {
        auto tmp = edges[i];
        a[i+1] = tmp[0];
        b[i+1] = tmp[1];
        c[i+1] = tmp[2];
        previous[i+1] = last[tmp[0]];
        last[tmp[0]] = i+1;
    }
    return {a,b,c,last,previous};
}

遍历代码

vector<vector<int>>traverse(vector<vector<int>> graph,int n) {
    vector<vector<int>> ans;
    for(int i = 1;i <= n;i++) {
        int k = graph[3][i];
        while (k != -1) {
            vector<int> e = {graph[0][k],graph[1][k],graph[2][k]};
            ans.emplace_back(e);
            k = graph[4][k];
        }
    }
    return ans;
}