乍一听，链式前向星这个名字很屌。实际上就是邻接表的静态实现。
它的优点是节省了分配内存的时间，效率更高。
链式前向星的构成由一个结构体（包括目标点、边权值和下一个同起点的边）和head数组（用于存放某点的第一条出边），必要的时候还可以添加一个统计入度的数组，因为进行BFS DFS的时候是依靠点的出度和出边的邻接关系来进行的。假如有多于一个点的入度为0，那么将只能遍历到其中一个点以及往后的内容。
对于链式前向星，总的一句话：链式前向星每添加一条边就会更新head数组，使得head数组存放的总是最新添加的某点的出边，此出边的next总指向head数组之前存放的出边的序号。
关于链式前向星的声明和初始化：
1 typedef struct Edge { 2 int v; //到达点 3 int w; //边权值 4 int next;//当前起点的下一条边的起始edge的序号 5 Edge() { next = -1; } 6 Edge(int vv, int ww) : v(vv), w(ww) { next = -1; } 7 }Edge; 8 9 const int maxn = 1111111;10 11 int n, m; //n个点标号为1-n，有m条边12 int vis[maxn]; //用于标记某边是否被遍历到，用于解决环的问题13 14 int cnt; //边的数量15 int dig[maxn];//有一种特殊情况：某点的入度为0，这样利用边与出度点的关系是便利不到的，因此我们特殊考虑。统计点的入度16 int head[maxn]; //每个顶点的边集数组的第一个存储位置17 Edge edge[maxn];//链式前向星存储边集18 19 void init() { //每次添加边的时候，head存储的都是起点添加的最后一条边20 memset(vis, 0, sizeof(vis));21 memset(edge, 0, sizeof(edge));22 memset(dig, 0, sizeof(dig));23 memset(head, -1, sizeof(head)); //因edge从0计数，用于区分24 cnt = 0;25 }
接下来考虑添加边的方式，每次更新cnt位置的结构体，并且更新head数组的对应值：
1 void adde(int uu, int vv, int ww) { //添加边2 dig[vv]++; //边指向点入度加一3 edge[cnt].v = vv;4 edge[cnt].w = ww;5 edge[cnt].next = head[uu]; //使要添加的边的指向下一条边的变量存下当前head中对应点的数6 head[uu] = cnt++; //记下当前边在edge数组的位置，并且作为头传递给head数组7 }
还有BFS和DFS，利用链式前向星的点和边的关系，很容易地得出遍历的方式。与邻接表非常相似：
1 //根据链式前向星的特性，每个边存的是同一个起点出发的下一条边， 2 //只需要遍历每一个点再从每一个点开始的头边向后扫描即可按照bfs的顺序遍历所有的边 3 void bfs_edge() { 4 int s = 1; 5 queue q; 6 while(!q.empty()) q.pop(); 7 for(int i = 1; i <= n; i++) { 8 if(head[i] != -1) { 9 s = i;10 break;11 }12 }13 for(int i = 1; i <= n; i++) { //特判入度为0的点，也遍历到。14 if(!dig[i] && i != s) {15 // printf("%d ", i);16 q.push(i);17 }18 }19 q.push(s); //找到第一个出度不为0的点后，作为起点并入栈。20 memset(vis, 0, sizeof(vis));//初始化vis数组21 while(!q.empty()) {22 int u = q.front(); q.pop();23 for(int i = head[u]; ~i; i=edge[i].next) { //遍历每一条以u为起点的边24 if(!vis[i]) { //如果当前边未遍历到25 vis[i] = 1; //设置为已遍历过26 printf("from %d to %d w %d\n", u, edge[i].v, edge[i].w);//输出遍历结果27 q.push(edge[i].v);//将此边的目标点放入队列28 }29 }30 }31 }32 33 //与bfs_edge同理，不过遍历到每一个边的时候，用vis数组对遍历到的边节点34 //所指向的下一个点进行标记就可以对点进行bfs了35 void bfs_vertex() {36 printf("BFS the vertex:\n");37 int s = 1;38 queue q;39 while(!q.empty()) q.pop();40 for(int i = 1; i <= n; i++) {41 if(head[i] != -1) {42 s = i;43 break;44 }45 }46 for(int i = 1; i <= n; i++) { //特判入度为0的点，也遍历到。47 if(!dig[i] && i != s) {48 printf("%d ", i);49 }50 }51 q.push(s); //找到第一个出度不为0的点后，作为起点并入栈。52 memset(vis, 0, sizeof(vis));//初始化vis数组53 printf("%d ", s);54 while(!q.empty()) {55 int u = q.front(); q.pop(); //取头队列头部的点，进行遍历56 vis[u] = 1; //记下当前点为遍历到57 for(int i = head[u]; ~i; i=edge[i].next) { //遍历此点的出边58 if(!vis[edge[i].v]) { //如果出边目标点未被遍历到59 vis[edge[i].v] = 1; //设置为已遍历 并输出遍历结果60 printf("%d ", edge[i].v);61 q.push(edge[i].v); //将此点放入队中62 }63 }64 }65 printf("\n");66 }67 68 void _dfs(int u) { //dfs的辅助函数，用于递归遍历最深处的点69 vis[u] = 1; //此点为遍历到，设置为已遍历70 for(int i = head[u]; ~i; i=edge[i].next) { //遍历所有此点的出边71 if(!vis[edge[i].v]) { //如果下一个点未被遍历到72 vis[edge[i].v] = 1; //设置为已遍历73 _dfs(edge[i].v); //递归地调用，以此点为起点向下寻找未被遍历到的点74 }75 }76 printf("%d ", u); //此处输出，因为dfs是先输出最深处的点77 }78 79 void dfs_vertex() {80 printf("DFS the vertex:\n");81 int s = 1;82 for(int i = 1; i <= n; i++) {83 if(head[i] != -1) {84 s = i;85 break;86 }87 } //查找第一个出度非零的点并执行dfs的辅助函数88 for(int i = 1; i <= n; i++) { //特判入度为0的点，也遍历到。89 if(!dig[i] && i != s) {90 printf("%d ", i);91 }92 }93 memset(vis, 0, sizeof(vis));94 _dfs(s);95 }
BFS DFS中关于非s的入度为0的顶点的遍历应该在遍历结束以后进行遍历比较合理，不改了QAQ
链式前向星对于最短路问题可以有很好的效果，尤其是稀疏图上。
给出链式前向星+dijkstra+堆优化的代码(poj1511)：
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include
转载请声明出处以及作者，谢谢！