图的存储方式之前向星与邻接表

[wtysos11]

常用的邻接矩阵和邻接表都挺简单的，就不提了。 这个是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);
    }
};

[wtysos11]

想了一下还是提一下邻接表吧

struct Edge{
    int from,to,weight;
};
vector<Edge> G[maxn];//可以用来模拟邻接表
//使用的时候给对应的数组G[node]插入边即可，其实也挺方便的

另外一个是刘汝佳的蓝书里面的实现，应该也是邻接表，只是G[maxn][edgeNum]里面放的不再是直接放边对象，而是改为了边索引号n。这个索引号可以由边对象数组维护，也可以由多个数据对象数组维护，比较方便。在很多时候，对边的信息没有过多要求时，直接用一两个int数组就可以表示全其信息，也比较方便。唯一的问题是不好删除。