1 条题解

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

    C :

    #include<stdio.h>
    #include<stdlib.h>
    #define MAXVEX 60
    typedef int WeightType;
    typedef int Elemtype;
    typedef struct EdgeNode
    {
        int adjvex;
    	int data;
        WeightType weight;
        struct EdgeNode *next;
    }EdgeNode;
    
    typedef struct VexNode
    {
        EdgeNode *firstarc;
    }VexNode, AdjList[MAXVEX];
    
    typedef struct GraphADJ{
        AdjList adjlist;
        int numvex, numedge;
    }GraphADJ;
    
    void InitGraph(GraphADJ *G,int n)
    {
        int i;
        G->numvex = n;
        for(i=0; i<n; i++)
    	{
    		G->adjlist[i].firstarc= NULL;
    	}
    }
    void InsertEdge(GraphADJ *G,int s,int t,int w)
    {
        EdgeNode *newn = (EdgeNode *)malloc(sizeof(EdgeNode));
        newn->adjvex = t;
        newn->weight = w;
        newn->next=G->adjlist[s].firstarc;
        G->adjlist[s].firstarc=newn;
    	
    }
    int LocateEdge(GraphADJ G,int s,int t)
    {
        EdgeNode *p = G.adjlist[s].firstarc;
        while(p!=NULL)
    	{
            if(p->adjvex == t)
                return 0;
            p = p->next;
        }
        return 1;
    }
    void Create(GraphADJ *G,int n)
    {
    	int i,j,x,k=0,t;
    	int a[60][60],visit[60],b[60];
    	InitGraph(G,n);
    	for(i=0;i<n;i++)
    		visit[i]=0;
    	for(i=0;i<n;i++)
    		for(j=0;j<n;j++)
    	        scanf("%d",&a[i][j]);
    	for(i=0;i<n;i++)
    		for(j=n-1;j>=0;j--)
    		{
                if(a[i][j]==1)
                   InsertEdge(G,i,j,1);
    		}
    	EdgeNode *p;
    	i=0;
        while(k==0)
    	{
    		j=0,t=0;
    		printf("%d ",i);
    	   do
    	   {
    	     p=G->adjlist[i].firstarc;
    	     visit[i]=1;
    	     while(p!=NULL)
    		 {
    	       i=p->adjvex;
    		   if(visit[i]!=1)
    		   {
    	          b[j++]=i;
                  visit[i]=1;
    		      printf("%d ",i);
    		   }
    	       p=p->next;
    		 }
    	     i=b[t];
    		 b[t]=-1;
    		 t++;
    	   }while(t<=j);
    	for(i=0;i<n;i++)
    	{
    		if(visit[i]==1)
    			k=1;
    		else
    		{
    			k=0;
    			break;
    		}
    	}
    	}
    }
    void main()
    {
    	int n;
    	scanf("%d",&n);
    	GraphADJ G;
        Create(&G,n);
    	printf("\n");
    }
    
    

    Java :

    
    
    import java.util.LinkedList;
    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] ;
    	  for (int i = 0; i < n; i++) {
    		for (int j = 0; j < n; j++) {
    			a[i][j] = s.nextInt() ;
    		}
    	  }
    	  
    	  for (int i = 0; i < a.length; i++) {
    		 a[i][i] = 1 ;
    	  }
    	  
    	  boolean visited[] = new boolean[a.length] ;
    	  
    	  LinkedList<Integer> queue = new LinkedList<Integer>() ;
    	  
    	  queue.add(0) ;
    	  System.out.print(0+ " ") ;
    	  visited[0] = true ;
    	  
    	  while(queue.size()!=0){
    		  int k = queue.pollFirst() ;
    		  
    		  for (int i = 0; i < visited.length; i++) {
    			if(visited[i]==false&&a[k][i]==1){
    				visited[i] = true ;
    				queue.add(i) ;
    				System.out.print(i+" ") ;
    			}
    		  }
    	  }
    	  System.out.println();
       }
       
       
    }
    
    
    
    
    • 1

    算法7-6:图的遍历——广度优先搜索

    信息

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