数据结构实验图论一：基于邻接矩阵的广度优先搜索遍历

ゝ一世哀愁。 2022-07-15 06:25 162阅读 0赞

数据结构实验图论一：基于邻接矩阵的广度优先搜索遍历 
     
      
      
       Time Limit: 1000MS 
      
       Memory Limit: 65536KB
     
      
     
      
      
       Submit 
      
       Statistic
     
      Problem Description 
     
      
       
      给定一个无向连通图，顶点编号从0到n-1，用广度优先搜索(BFS)遍历，输出从某个顶点出发的遍历序列。(同一个结点的同层邻接点，节点编号小的优先遍历）
     
      Input 
     
      
       
      输入第一行为整数n（0< n <100），表示数据的组数。
      
       
    对于每组数据，第一行是三个整数k，m，t（0＜k＜100，0＜m＜(k-1)*k/2，0＜ t＜k），表示有m条边，k个顶点，t为遍历的起始顶点。
      
       
    下面的m行，每行是空格隔开的两个整数u，v，表示一条连接u，v顶点的无向边。
     
      Output 
     
      
       
      输出有n行，对应n组输出，每行为用空格隔开的k个整数，对应一组数据，表示BFS的遍历结果。
     
      Example Input 
     
      
      
       1
    6 7 0
    0 3
    0 4
    1 4
    1 5
    2 3
    2 4
    3 5
     
     
      Example Output 
     
      
      
       0 3 4 2 5 1 
     
      Hint 
     
      
       
      以邻接矩阵作为存储结构。
     
      Author

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <queue>
    
    using namespace std;
    int map[105][105];
    int vis[105];
    int m,mark=1;
    void bfs(int k)
    {
    	queue<int> q;
    	q.push(k);
    	memset(vis,0,sizeof(vis));
    	while(!q.empty())
    	{
    		int t = q.front();
    		q.pop();
            if(mark)
    		{
    			printf("%d",t);
    			mark=0;
    		}
    		else
    		{
    			printf(" %d",t);
    		}
    
    		vis[k] = 1;
    		for(int i=0;i<m;i++)
    		{
    			if(!vis[i]&&map[t][i])
    			{
    				q.push(i);
    				vis[i] = 1;
    			}
    		}
    	}
    }
    int main()
    {
    	int v,u;
    	int T,n,k;
    	scanf("%d",&T);
    	while(T--)
    	{
    		scanf("%d%d%d",&m,&n,&k);
    		for(int i=0;i<n;i++)
    		{
    			scanf("%d%d",&u,&v);
    			map[u][v] = map[v][u] = 1;
    		}
    		bfs(k);
    		printf("\n");
    	}
    	return 0;
    }