vector实现邻接表的两种方式

std::vector实现邻接表的两种方式


概述

方式一:vector<edge> G[Max_V];

方式二:vector<vector<edge> > G(Max_V);

代码

方式一

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
#include<vector>
#define Max_V 100
using namespace std;
struct edge
{
int next,weight;
edge(int a,int b):next(a),weight(b) {}
};
vector<edge> G[Max_V]; //!!!
void init(int V)
{
for(int i=0;i<V;i++)
G[i].clear();
return;
}
void create_graph(int E)
{
int t1,t2,t3;
for(int i=0;i<E;i++)
{
cin>>t1>>t2>>t3;
G[t2-1].push_back(edge(t1-1,t3));
G[t1-1].push_back(edge(t2-1,t3));
}
return;
}
void print(int V)
{
for(int i=0;i<V;i++)
{
cout << i << ": ";
for(auto j : G[i])
cout << j.next << " ";
cout << endl;
}
return;
}
int main(void)
{
int V,E;
cin>>V>>E;
init(V);
create_graph(E);
print(V);
return 0;
}

方式二

把方式一中的注释为!!!句子vector<edge> G[Max_V];

更改为vector<vector<edge> > G(Max_V);即可。

完整代码

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
#include<vector>
#define Max_V 100
using namespace std;
struct edge
{
int next,weight;
edge(int a,int b):next(a),weight(b) {}
};
vector<vector<edge> > G(Max_V);
void init(int V)
{
for(int i=0;i<V;i++)
G[i].clear();
return;
}
void create_graph(int E)
{
int t1,t2,t3;
for(int i=0;i<E;i++)
{
cin>>t1>>t2>>t3;
G[t2-1].push_back(edge(t1-1,t3));
G[t1-1].push_back(edge(t2-1,t3));
}
return;
}
void print(int V)
{
for(int i=0;i<V;i++)
{
cout << i << ": ";
for(auto j : G[i])
cout << j.next << " ";
cout << endl;
}
return;
}
int main(void)
{
int V,E;
cin>>V>>E;
init(V);
create_graph(E);
print(V);
return 0;
}

样例输入

6 9
1 2 1
1 3 12
2 3 9
2 4 3
3 5 5
4 3 4
4 5 13
4 6 15
5 6 4

样例输出

0: 1 2
1: 0 2 3
2: 0 1 4 3
3: 1 2 4 5
4: 2 3 5
5: 3 4

参考文档