类似于邻接表
有一个数组head,它是用来表示以i为起点的索引的第一条边存储的位置,实际上你会发现这里的第一条边存储的位置其实在以i为起点的所有边的最后输入的那个编号.如果按照索引顺序，next表示下一条边的存储位置，如果按照添加顺序，next即为上一条添加的边的位置。所以我们可以得到，输入顺序和存图顺序或者说是遍历顺序是相反的。还是上面的图，我们定义全局变量int cnt=0;并将head初始化为-1；1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39#include<iostream>
#include<cstring>
#define MAX 1000
using namespace std;
int cnt=0;
int head[MAX];//head[i] 表示以 i为起点的第一条边
struct edge{
int to;
int next;
edge(int tt,int nn):to(tt),next(nn){
}
edge(){
}
};
edge e[MAX];
void addEdge(int u,int v){
e[cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt++;
}
int main(){
int n;
//n条边
cin>>n;
memset(head,-1,sizeof(head));
for(int i=0;i<n;i++){
int a,b;
cin>>a>>b;
addEdge(a,b);
}
cout<<"遍历图的各个顶点"<<endl;
for(int i=1;i<=n;i++){
for(int j=head[i];j!=-1;j=e[j].next){
cout<<i<<" "<<e[j].to<<endl;
}
}
}
参考链接