1 条题解

  • 0
    @ 2024-12-24 10:06:05

    C :

    #include <stdio.h>
    #include <string.h>
    #define maxn 51
    int isvisited[maxn],mat[maxn][maxn],n;
    void bfs(int vo){
    	int i;
    	printf("%d ",vo);
    	isvisited[vo]=1;
    	for (i=0;i<n;i++)
    	{
    		if (isvisited[i]==0&&mat[vo][i]==1)
    		{
    			bfs(i);
    		}
    	}
    }
    int main(){
    	int i,j;
    //	freopen("1.txt","r",stdin);
    	while (scanf("%d",&n)!=EOF)
    	{
    		for (i=0;i<n;i++)
    		{
    			for (j=0;j<n;j++)
    			{
    				scanf("%d",&mat[i][j]);
    			}
    		}
    		memset(isvisited,0,sizeof(isvisited));
    		for (i=0;i<n;i++)
    		{
    			if (isvisited[i]==0)
    			{
    				bfs(i);
    				printf("\n");
    			}
    		}
    	}
    //	fclose(stdin);
    	return 0;
    }
    

    C++ :

    #include <cstdio>
    #include <cstdlib>
    const int MAXN = 50;	// 最大顶点数
    int mat[MAXN][MAXN];	// 无向图的邻接矩阵
    bool visited[MAXN];		// 标记顶点是否被访问过的数组
    int n;					// 顶点的个数
    void DFS(int node) {
    	visited[node] = true;
    	printf("%d ", node);
    	for (int i = 0;i < n;i++) {
    		if (!visited[i] && mat[node][i] == 1) {
    		// 找到了下一个可以访问的顶点
    			DFS(i);
    		}
    	}
    }
    int main() {
    	scanf("%d", &n);
    	for (int i = 0;i < n;i++) {
    	// 读入无向图的邻接矩阵
    		for (int j = 0;j < n;j++) {
    			scanf("%d", &mat[i][j]);
    		}
    	}
    	for (int i = 0;i < n;i++)
    		visited[i] = false;
    	for (int i = 0;i < n;i++) {
    		if (!visited[i]) {
    		// 找到了一个新的连通块
    			DFS(i);
    			puts("");
    		}
    	}
    	return 0;
    }
    
    • 1

    算法7-7,7-8:无向图的连通分量和生成树

    信息

    ID
    1885
    时间
    1000ms
    内存
    32MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者