前向星是一种通过存储边信息的方式存储图的数据结构。它的构造方式非常简单,读入每条边的信息,将边存放在数组中,把数组中的边按照起点顺序排序,前向星就构造完成了

但是为了查询方便,会有一个数组存储起点为Vi的第一条边的位置

  1. #include<iostream.h>
  2. #include<stdlib.h>
  3. #include<algorithm>
  4. const int maxn=100;
  5. const int maxm=100;
  6. int head[maxn];
  7. struct NODE
  8. {
  9. int from;
  10. int to;
  11. int w;
  12. };
  13. NODE edge[maxm];
  14. //利用c++的STL排序函数 qsort()
  15. int cmp(const void *a,const void * b)
  16. {
  17. if(((NODE *)a)->from==((NODE *)b)->from&&((NODE *)a)->to==((NODE *)b)->to)return ((NODE *)a)->w < ((NODE *)b)->w;
  18. if(((NODE *)a)->from==((NODE *)b)->from) return ((NODE *)a)->to < ((NODE *)b)->to;
  19. return ((NODE *)a)->from < ((NODE *)b)->from;
  20. }
  21. int main()
  22. {
  23. int n,m;
  24. //读入数据
  25. //********************************************
  26. cin>>n>>m;
  27. for(int i=0;i<m;i++)
  28. cin>>edge[i].from>>edge[i].to>>edge[i].w;
  29. qsort(edge,m,sizeof(NODE),cmp); //排序
  30. memset(head,-1,sizeof(head));
  31. head[edge[0].from]=0; //初始化
  32. for(i=1;i<m;i++)
  33. if(edge[i].from!=edge[i-1].from)
  34. head[edge[i].from]=i; //确定起点为Vi的第一条边的位置
  35. //********************************************
  36. //遍历代码
  37. for(i=1;i<=n;i++)
  38. {
  39. for(int k=head[i];edge[k].from==i&&k<m;k++) //若找到起点则输出
  40. {
  41. cout<<edge[k].from<<' '<<edge[k].to<<' '<<edge[k].w<<endl;
  42. }
  43. }
  44. //********************************************
  45. return 0;
  46. }