一种非常厉害的存图的数据结构！

本质：模拟链表的操作，链式存储图。（2，3都可以模拟链表的操作，替代链表）

 

（1）二维数组存图：Map[x][y]，一维代表出发点，二维代表它所连接的所有点。（不连接设为inf）

（2）链式前向星存图：head[x]相当于一维代表了出发点，之后T[i].next一条链相当于二维代表了所有（与它）连接的点。（不连接的到0就停止了）。

如head[x]，T[head[x]].to，T[head[x]].w，T[head[x]].next，完美表示了一条边的两端点，权值，甚至下一条边存储位置序号。

所以说，二维数组存图很浪费空间（有的题目要求大也存不下），有的点之间没有连接就不用存（我们也不用），但二维数组把没链接的点之间也存下来了并且设为inf。

但链式前向星相当于链表，与某个点连接的所有点存下来形成一条链，有多少存多少，没有的就不存，节省了空间。（至于邻接链表就不说了，不直观操作不方便）

 

好，经过了链式前向星存图原理的诱导！明白了关键之处是：head[x]一维代表了出发点，之后一条链相当于二维代表了所有（与它）连接的点！

既然如此我们完全可以用vector代替链式前向星，因为vector更好理解看起来更直观！（本质：也相当于一条链，必须一个一个尾插入pushback，这就是链表啊！）

（3）vector链式顺序存图：vec[x][i]，x即一维代表了出发点，[i]即二维代表了所有与x相连相关的点的信息依次链式顺序存放，成一条链。

注意：vector容器里面什么都可以塞，各种信息都存放的下，又相当于一个结构体。所以存图，对付空间问题，链式之类的最好用vector，一般都能解决。（虽然不一定比前向星快，但是操作方便，理解直观啊！）

更新实测：数据小量或一般的时候没什么，但大量或极端时，链式前向星比vector快！洛谷P4779，前向星比vector快了200ms左右！

一般情况下先vector好理解，一般够用了，不行了再换链式前向星！

 

前向星

1 int head[maxn];//每个顶点(从i出发)的第一条边(相当于头指针,指向首元结点) 2 struct px 3 { 4     int next; 5     int to; 6     int w; 7 }T[maxm*3];//注意T存的是所有边数(边的连接信息,终点,权值,下条边都在这里),无向图是2倍 8  9 10 void Add(int x,int y,int z)//加边操作11 {12     T[++cnt].next=head[x];//相当于链表前插法,新结点指向了头指针指的结点13     T[cnt].to=y;14     T[cnt].w=z;15     head[x]=cnt;//前插完成,头指针已经指向了新结点16 }17 18 19 for(int i=head[x];i;i=T[i].next)//遍历(与某个点x连接的所有边和点)20 {21     cout<
     
      <<' '<
      
       <
      
     

 vector改进

1 struct px 2 { 3     //int next; 4     int to; 5     int w; 6 }T; 7 vector
     
       vec[maxn]; 8  9 vec[x].push_back(T);//加边操作10 11 for(int i=0;i
     

可以看到，用了vector存图无论是加边，遍历都方便直观了许多！

 

完。