邻接表建图的三种方式的时空比较(解析+图示)

1 #include<iostream>
2  #define Maxn 200
3  usingnamespace std;
4  struct edge{int from,to,weight,next;}e[Maxn];//存储边信息的结构体 
5 int first[Maxn];//起点为下标存储(e中边的位置) 
6 int main()
7 {
8 int edges;//边数 
9 memset(first,-1,sizeof(first));
10 //因为刚开始first不指向任何一条边的下标,所以first都为-1 
11 cin>>edges;//边数 
12 for(int i=0;i<edges;i++)
13 {
14 cin>>e[i].from>>e[i].to>>e[i].weight;//起点 终点 权重 
15 e[i].next=first[e[i].from];first[e[i].from]=i;//不容易理解的地方
16 /*
17 利用first数组存储的是最新的(以数组下标为起点的)边的下标 
18 并且该条边的next指向的是同样以数组下标为起点的下一条边的下标 
19 直到下一条边的next=-1(即将所有以数组下标为起点的边都遍历了一遍) 
20 */
21 }
22 for(int u=1;u<10;u++)//输出图 
23 {
24 cout<<"以"<<u<<"为起点的所有边的信息："<<endl; 
25 for(int v=first[u];v!=-1;v=e[v].next)//遍历以u为起点的所有边的信息 
26 cout<<e[v].from<<""<<e[v].to<<""<<e[v].weight<<endl;
27 }
28 return0;
29 }
30 /*
31 5
32 3 4 6
33 3 7 8
34 1 3 6
35 2 4 7
36 3 5 1
37 */