圖的存儲方式之前向星與鄰接表

常用的鄰接矩陣和鄰接表都挺簡單的，就不提了。 這個是ACM版本的前向星，本質就是用數組替換了連結清單，效果就是更友善一些。 雖然不如十字連結清單删除友善，但是也能比較友善地寫出邊删除的操作。

//前向星
struct graph{
    typedef vector<int> VI;
    VI info,next,to;
    //假設現在有n個點，m條邊,info長度為n，next和to長度為m。
    //其中，info儲存着所有節點的第一個邊
    //next儲存着所有邊資訊的下一個邊
    //to儲存着邊的下一個節點資訊。如果是帶權邊，可以增加一個weights數組，與to類似。（所有邊增加主要加的是to）
    graph(int n=0,int m=0):to(0),next(0){
        info.resize(n);
        next.reserve(m);
        to.reserve(m);
    }

    int edge_size(){
        return to.size();//顯然，to即儲存了所有邊的資訊
    }
    int vertex_size(){
        return info.size();//info儲存了所有節點的資訊
    }
    void expand(int i){
        if(info.size()<i+1)
            info.resize(i+1);
    }
    void add(int i,int j){//添加一條從i到j的邊，有向
        expand(i),expand(j);
        to.push_back(j);//壓入新邊的資訊
        next.push_back(info[i]);//新頭的下一個指向原來的指針
        info[i] = to.size()-1;//連結清單頭指針指向新加項目
    }
    void del_back(){
        for(int i=0;i<info.size();i++){
            if(info[i] == to.size()-1){
                info[i] = next.back();
                break;
            }
        }
        to.pop_back();
        next.pop_back();
    }
    void clear(){
        info.clear();
        next.resize(0);
        to.resize(0);
    }
};           

複制

想了一下還是提一下鄰接表吧

struct Edge{
    int from,to,weight;
};
vector<Edge> G[maxn];//可以用來模拟鄰接表
//使用的時候給對應的數組G[node]插入邊即可，其實也挺友善的           

複制

另外一個是劉汝佳的藍書裡面的實作，應該也是鄰接表，隻是

G[maxn][edgeNum]

裡面放的不再是直接放邊對象，而是改為了邊索引号n。這個索引号可以由邊對象數組維護，也可以由多個資料對象數組維護，比較友善。在很多時候，對邊的資訊沒有過多要求時，直接用一兩個int數組就可以表示全其資訊，也比較友善。唯一的問題是不好删除。