之前在复习图论时看到俞勇老师主编的<ACM国际大学生程序设计竞赛-算法与实现>之前向星的设计与实现，由于原书是一个单纯的模板没有任何注释与输入输出实例，看了很久没有看明白代码的意义。参阅了不少资料后，终于理解了该代码的设计思路。
数据结构原理
前向星是存储有向图的一种数据结构。它不同于邻接矩阵和邻接表，利用图的端点进行边的扫描，而是一个基于边链表的数据结构，在给定入口顶点时可顺边链表顺序访问边，而无需关心顶点的信息（所有顶点可以借助边来访问，与邻接表和邻接矩阵相反）。因此只需要构建一个链表(next)，链表的每一个节点代表一条边；同时为每一个顶点设置一个入口(info)，指向该顶点的第一条出边；为每条边设置一个终点(to)，至此前向星数据结构就构建完成。
由前向星数据结构的设计思路可以看出，从某个顶点开始遍历边到遍历结束恰好走完一条完整的路径，很像DFS的情形。
C++实现方法
1 struct Graph{ 2 vector<int> info, to, next; //info为顶点0~n-1指向的第一条出边; to为边0~m-1的入度点; next为边0~m-1的下一条边 3 Graph(int n = 0, int m =0): to(0), next(0){ 4 info.resize(n, -1); //初始化所有顶点为孤立的点，没有出边(-1) 5 next.reserve(m); 6 to.reserve(m); 7 } 8 9 int edge_size(){ //边链表(静态链表)的长度 10 return to.size(); 11 } 12 13 int vertex_size(){ 14 return info.size(); 15 } 16 17 void expand(int i){ 18 if(info.size() < i + 1){ 19 info.resize(i + 1); 20 } 21 } 22 23 void add(int i, int j){//将以顶点为i, j的边i->j加入图中 24 expand(i), expand(j); // 确保保存顶点的数组空间足够 25 to.push_back(j); //为 当前 的边链表加入入度点j 26 next.push_back(info[i]); //为 当前 的边链表加入到以i为顶点的下一条出边 27 info[i] = to.size() - 1; //当前边链表的下标(节点) 28 } 29 30 void clear(){ 31 info.clear(); 32 next.resize(0); 33 to.resize(0); 34 } 35 36 };
NOTE：原书中在初始化info[]数组时，并没有初始化为-1，这样做遍历会出错。因为静态链表到访问终点需要用一个标志来结束。在add()函数中，每次加入的顶点i必然有入度为0的情况，所以必须提前进行初始化。
原文链接: https://www.cnblogs.com/moonwalker-hank/p/12633080.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/339822
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
