图的储存

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 
      
        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<
       
        <
        
         <<" ";36         }37         cout<
        
       
      

2、邻接链表

1 #include 
      
        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<
       <<" : ";33         node* p=tree[i].next;34         while(p){35             cout<
        
         to<<" ";36             p=p->next;37         }38         cout<
        
      

3、数组模拟邻接链表

1 #include 
      
        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<
       <<" : ";34         int p=head[i];35         while(p){36             cout<
        
         <<" ";37             p=edge[p].next;38         }39         cout<
        
      

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

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

4、向量组

1 #include 
      
        2 using namespace std; 3 int n,m; 4 struct node{ 5     int to; 6     int val; 7 }; 8  9 vector
       
         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<
        <<" : ";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<
         
          to<<" ";39         }40         cout<
         
       
      

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交换数据