数据结构：图的存储与遍历（待续）

        图（Graph）是一种较线性表和树更为复杂的非线性结构。在图结构中，对结点（图中常称为顶点）的前驱和后继个数不加限制， 即结点之间的关系是任意的。

一、基本概念和一般结论

因为一条边关联两个顶点，而且使得这两个顶点的度数 分别增加1。因此顶点的度数之和就是边的两倍。

关于连通图：

无向图：连通图，连通子图，极大连通子图（连通分量，即一个图中最大的某个连通子图，即无法增加顶点以及边 使其构成更大的连通图）

有向图：强连通图，强连通子图，强连通分量。

连通分量不一定唯一。

二、图的存储结构

（1）邻接矩阵

邻接矩阵可以方便求出图中顶点的度：

对于邻接矩阵的第i行，如果其第j列有一个1（或者一个权值），则说明有一条边从vi指向vj。如果是有向图，则表示存在一条边<vi,vj>，通过行可以看出出度，通过列可以看出入度。

（2）邻接表

        总的来说就是，顺序存储图中的所有顶点信息，每个顶点信息包括顶点编号（也可以不用，因为顺序存储用数组标识的话，数组位置就是顶点编号），以及顶点的边链表头结点指针。一个顶点的边链表是将 以该顶点为起始的 连向的其他顶点信息。

       有向图的邻接表，边链表结点个数等于有向边的条数。（因为每条有向边有且仅有一个起始和一个终止）

        无向图的邻接表，边链表结点个数等于无向边的条数*2。（无向边是双向的）

struct Edge{//边链表结点
    int VerName;//顶点编号
    int cost;//边权值
    Edge *next;//指向下一个边链表结点
}
struct Vertex{//顶点表结点
    int VerName;//顶点编号
    Edge * adjacent;//边链表指针
}

（3）链式前向星

        实际上就是使用静态链表实现的邻接表。数据结构：静态链表（编程技巧）-CSDN博客

这样做的好处是，不需要使用指针，也不需要使用指针访问，直接通过数组下标即可访问，速度更快，内存更少。

插入表尾：

vector<int> head(n,-1);//n个顶点，head[i]指向边链表，初始都没有
vector<int> VerName;//边链表，adjacent[i]存的是边链表顶点信息
vector<int> next;//边链表的指针信息
vector<int> cost;//边的权值
/*可以理解为：
struct head{
    Edge* head[i];//head[i]表示的是第i个顶点的边链表表头。这里实际上是一个下标
}
struct Edge{//他们仨 下标是一样的
    int VerName;
    Edge* next;
    int cost;
};
*/
int Vertex;
int edge;
int cos;

while(cin>>Vertex>>edge>>cos){//假定输入都是正确的，没有重边
    //为了复杂化，我们先找到边链表的最后一个结点
    int adj=head[Vertex];
    if(adj!=-1)
        while(next[adj]!=-1){
            adj=next[adj];
        }
    /*创建一个新结点 其之后无指向即next=-1*/
    VerName.push_back(edge);
    next.push_back(-1);
    cost.push_back(cos);
    /*-adj为Vertex边链表的最后一个元素-*/
    if(adj!=-1)
        next[adj]=next.size()-1;//VerName.size()-1、cost.size()-1均可 就是指向最后一个嘛。
    if(adj==-1){//只可能是顶点还没有边
        head[Vertex]=next.size()-1;
    }
}

//顺次输出边
for(int i=0;i<n;++i){
    int adj=head[i];
    while(adj!=-1){
        cout<<i<<"--->"<<VerName[adj]<<"  cost为:"<<cost[adj]<<endl;
        adj=next[adj];
    }
}
//我们会发现，将adj当做一个结构体指针Edge *，那么VerName[adj]相当于adj->VerName了

直接插入表头：

while(cin>>Vertex>>edge>>cos){/*直接创建点，插入在Vertex的边链表表头*/
    VerName.push_back(edge);
    next.push_back(head[Vertex]);
    cost.push_back(cos);
    head[Vertex]=next.size()-1;
}