图的储存

5 7
1 2 2
1 3 4
1 4 7
2 3 1
2 5 2
3 4 1
3 5 6

1、邻接矩阵

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int n,m;
 4 int al[15][15];
 5 void printAL();
 6 void readData(){
 7     memset(al,0x7,sizeof(al));
 8     cin>>n>>m;
 9     for(int i=1;i<=n;i++) al[i][i]=0;
10     for(int i=1;i<=m;i++){
11         int a,b,w;
12         cin>>a>>b>>w;
13         al[a][b]=w;
14         al[b][a]=w;
15     }    
16     
17 }
18 
19 
20 
21 int main(){
22     freopen("shu_in.txt","r",stdin);
23     readData();
24     printAL();
25     return 0;
26 } 
27 
28 
29 
30 
31 
32 void printAL(){
33     for(int i=1;i<=n;i++){
34         for(int j=1;j<=n;j++){
35             cout<<setw(10)<<al[i][j]<<" ";
36         }
37         cout<<endl;
38     }
39     cout<<endl;
40 }

邻接矩阵

2、邻接链表

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int n,m;
 4 
 5 struct node{
 6     int val;
 7     int to;
 8     node* next;    
 9 }tree[15];  
10 
11 void addEdge(int a,int b,int w){
12     node* p=new node();
13     p->to=b;
14     p->val=w;
15     p->next=tree[a].next;
16     tree[a].next=p;
17 }
18 
19 void readData(){
20     cin>>n>>m;
21     for(int i=1;i<=m;i++){
22         int a,b,w;
23         cin>>a>>b>>w; 
24         addEdge(a,b,w);
25         addEdge(b,a,w);
26     } 
27     
28 }
29 
30 void printEdge(){
31     for(int i=1;i<=n;i++){
32         cout<<i<<" : ";
33         node* p=tree[i].next;
34         while(p){
35             cout<<p->to<<" ";
36             p=p->next;
37         }
38         cout<<endl;
39     }
40 }
41 
42 
43 int main(){
44     freopen("shu_in.txt","r",stdin);
45     readData();
46     printEdge();
47     return 0;
48 }

邻接链表

3、数组模拟邻接链表

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int n,m;
 4 int head[15];
 5 
 6 struct node{
 7     int to;
 8     int val;
 9     int next; 
10 }edge[50]; 
11 
12 void addEdge(int i,int a,int b,int w){
13     edge[i].to=b;
14     edge[i].val=w;
15     edge[i].next=head[a];
16     head[a]=i;
17 }
18 
19 void readData(){
20     cin>>n>>m;
21     for(int i=1;i<=m;i++){
22         int a,b,w;
23         cin>>a>>b>>w;
24         addEdge(i,a,b,w);
25         //双向图，所以这里是i+m 
26         //不然会导致第i条边被添加两次，数据被覆盖 
27         addEdge(i+m,b,a,w);
28     }    
29 }
30 
31 void printEdge(){
32     for(int i=1;i<=n;i++){
33         cout<<i<<" : ";
34         int p=head[i];
35         while(p){
36             cout<<edge[p].to<<" ";
37             p=edge[p].next;
38         }
39         cout<<endl;
40     }
41 }
42 
43 
44 //缩小数据量查错的方式蛮不错的 
45 int main(){
46     freopen("shu_in.txt","r",stdin);
47     readData();
48     printEdge();
49     return 0;
50 }

数组模拟邻接链表

　　双向图，所以加边时是i+m，不然会导致第i条边被添加两次，数据被覆盖

　　缩小数据量查错的方式蛮不错的

4、向量组

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int n,m;
 4 struct node{
 5     int to;
 6     int val;
 7 };
 8 
 9 vector<node> vec[15];
10 int edgeNum[15];
11 
12 void addEdge(int a,int b,int w){
13     edgeNum[a]++;
14     node* p=new node();
15     p->to=b;
16     p->val=w; 
17     vec[a].push_back(*p);
18 }
19 
20 void readData(){
21     cin>>n>>m;
22     for(int i=1;i<=m;i++){
23         int a,b,w;
24         cin>>a>>b>>w;
25         addEdge(a,b,w);
26         addEdge(b,a,w);
27     }    
28     
29 }
30 
31 void printEdge(){
32     for(int i=1;i<=n;i++){
33         cout<<i<<" : ";
34         for(int j=1;j<=edgeNum[i];j++){
35             node* p=new node();
36             *p=vec[i].back();
37             vec[i].pop_back();
38             cout<<p->to<<" ";
39         }
40         cout<<endl;
41     }
42 }
43 
44 
45 int main(){
46     freopen("shu_in.txt","r",stdin);
47     readData();
48     printEdge();
49     return 0;
50 }

向量组

1.push_back   在数组的最后添加一个数据
2.pop_back    去掉数组的最后一个数据
3.at                得到编号位置的数据
4.begin           得到数组头的指针
5.end             得到数组的最后一个单元+1的指针
6．front        得到数组头的引用
7.back            得到数组的最后一个单元的引用
8.max_size     得到vector最大可以是多大
9.capacity       当前vector分配的大小
10.size           当前使用数据的大小
11.resize         改变当前使用数据的大小，如果它比当前使用的大，者填充默认值
12.reserve      改变当前vecotr所分配空间的大小
13.erase         删除指针指向的数据项
14.clear          清空当前的vector
15.rbegin        将vector反转后的开始指针返回(其实就是原来的end-1)
16.rend          将vector反转构的结束指针返回(其实就是原来的begin-1)
17.empty        判断vector是否为空
18.swap         与另一个vector交换数据