首页 > > 程序设计 > C/C++ >

邻接表模板

2018-06-17 22:52:26来源：未知阅读 ()

l邻接表的处理方法是这样：

l图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便。

l图中每个顶点Vi的所有邻接点构成一个线性表，由于邻接点的个数不确定，所以我们选择用单链表来存储。

 1 #include<iostream>
 2 using namespace std;
 3 struct node
 4 {
 5     int u;
 6     int v;
 7     int w;
 8     int next;
 9 }a[10001];
10 int head[1001];
11 int num=1;
12 void f(int p,int b,int c)
13 {
14     a[num].u=p;
15     a[num].v=b;
16     a[num].w=c;
17     a[num].next=head[p];
18     head[p]=num++;
19 }
20 int main()
21 {
22     int n,m;
23     cin>>n>>m;
24     for(int i=1;i<=n;i++)
25     head[i]=-1;
26     for(int i=1;i<=m;i++)
27     {
28         int p,b,c;
29         cin>>p>>b>>c;
30         f(p,b,c);
31     }
32     
33     cout<<"****************************"<<endl;
34     for(int k=1;k<=n;k++)
35     {
36         int i=head[k];    
37         cout<<"k:";
38         while(i!=-1)
39         {
40             cout<<"-->"<<a[i].v;
41             i=a[i].next;
42         }
43         cout<<"-->"<<-1<<" ";
44         cout<<endl;
45     }
46 
47     return 0;
48 }