前向星是以存储边的方式来存储图，先将边读入并存储在连续的数组中，然后按照边的起点进行排序，这样数组中起点相等的边就能够在数组中进行连续访问了。它的优点是实现简单，容易理解，缺点是需要在所有边都读入完毕的情况下对所有边进行一次排序，带来了时间开销，实用性也较差，只适合离线算法。图一-2-4展示了图一-2-1的前向星表示法。
前向星是一种用来存储图的数据结构。它的构造方式很简单，读入每条边的信息，然后存到数组中，然后将数组排序，排序方法是按照起点顺序排序，若起点相同则按终点顺序排序，如果终点相同则按权重排序（如果有权重）。另外，为了方便查询，会用一个数组head[]存储起点为v的第一条边的位置。
const int maxn=100+10;
const int maxm=1000+10;
int head[maxn]; //存储起点为i的第一条边的位置
int n,m;
struct NODE
{
int from; //起点
int to; //终点
bool operator < (const NODE & a) const
{
return (from==a.from&&to<a.to)||from<a.from;
}
};
NODE edge[maxm];
void Init()
{
for(int i=0;i<m;++i) //读入数据
cin>>edge[i].from>>edge[i].to;
sort(edge,edge+m); //排序
memset(head,-1,sizeof(head));
head[edge[0].from]=0;
for(int i=1;i<m;++i)
if(edge[i].from!=edge[i-1].from) head[edge[i].from]=i;
}
void solve() //遍历整个图
{
for(int i=1;i<=n;++i)
{
for(k=head[i];edge[k].from==i&&k<m;++k)
{
cout<<edge[k].from<<" "<<edge[k].to<<endl;
}
}
}
前向星的优点是可以应对点非常多的情况，并且可以存储重边，缺点是效率相对来说不是非常高，因为它不能直接找到两点之间是否有边，而且还要排序，比较浪费时间。
链式前向星的结构也很简单，需要存储的信息有终点和与此边拥有相同起点的前一条边所在的位置next。构造方法使用类似于链表一样的方法将所有起点相同边连起来，head数组中存储最开始的一条边的位置，这样就能通过它找到所有的边。
链式前向星的构成由一个结构体（包括目标点、边权值和下一个同起点的边）和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<int> 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<int> 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 }
