1 条题解

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

    C :

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

    Java :

    
    
    import java.util.Scanner;
    
    public class Main {
       private static Scanner s = new Scanner(System.in) ;
       
       public static void main(String[] args) {
    	   int n = s.nextInt() ;
    	   int a[][] = new int[n][n] ;
    	   boolean visited[] = new boolean[n] ;
    	   for (int i = 0; i < a.length; i++) {
    		 for (int j = 0; j < a.length; j++) {
    			a[i][j] = s.nextInt() ;
    		 }
    	    }
    	   for (int i = 0; i < visited.length; i++) {
    		  a[i][i] = 1 ;
    	   }
    	   
    	   Graph g = init(a ,visited) ;
    	   deptSearch(g, 0) ;
    	   System.out.println() ;
       } 
       
       public static Graph init(int a[][] , boolean visited[]){
    	   Graph g = new Graph(a.length) ;
    	   g.visited = visited ;
    	   g.a = a ;
    	   return g ;
       }
       public static void deptSearch(Graph g,int x){
    	   for (int i = 0; i < g.n; i++) {
    		   if(g.a[x][i] ==1&&g.visited[i]==false){
    			   g.visited[i] = true ;
    			   visit(i) ;
    			   deptSearch(g, i) ;
    		   }
    	   }
       }
       public static void visit(int i){
    	   System.out.print(i+" ");
       }
    }
    
    class Graph{
    	int n  ;
    	int a[][] = new int [n][n] ;
    	boolean visited[] = new boolean[n] ;
    	public Graph(int n) {
           this.n = n ;
    	}
    }
    
    
    • 1

    算法7-4,7-5:图的遍历——深度优先搜索

    信息

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