1 solutions

  • 0
    @ 2024-12-10 23:09:25

    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;
    }
    

    C++ :

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <limits.h>
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    #define OVERFLOW -1
    typedef int Status; /* 函数结果状态代码,如OK等 */
    #define INFINITY INT_MAX /* 用整型最大值代替∞ */
    #define MAX_VERTEX_NUM 50 /* 最大顶点个数 */
    typedef int VRType;
    typedef char InfoType;
    typedef int VertexType;
    typedef enum{DG,DN,AG,AN}GraphKind; /* {有向图,有向网,无向图,无向网} */
    typedef struct {
    	VRType adj; /* 顶点关系类型。对无权图,用1(是)或0(否)表示相邻否; */
    	/* 对带权图,c则为权值类型 */
    	InfoType *info; /* 该弧相关信息的指针(可无) */
    }ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
    typedef struct {
    	VertexType vexs[MAX_VERTEX_NUM]; /* 顶点向量 */
    	AdjMatrix arcs; /* 邻接矩阵 */
    	int vexnum,arcnum; /* 图的当前顶点数和弧数 */
    	GraphKind kind; /* 图的种类标志 */
    }MGraph;
    
    Status CreateUDG(MGraph *G)
    { /* 采用数组(邻接矩阵)表示法,由文件构造没有相关信息的无向图G */
    	int i,j;
    	scanf("%d",&(*G).vexnum);
    	for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量 */
    		(*G).vexs[i] = i;
    	for(i=0;i<(*G).vexnum;++i) /* 初始化邻接矩阵 */
    		for(j=0;j<(*G).vexnum;++j)
    		{
    			scanf("%d",&(*G).arcs[i][j].adj); /* 图 */
    			(*G).arcs[i][j].info=NULL; /* 没有相关信息 */
    		}
    	(*G).kind=AG;
    	return OK;
    }
    
    int LocateVex(MGraph G,VertexType u)
    { /* 初始条件:图G存在,u和G中顶点有相同特征 */
    	/* 操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */
    	int i;
    	for(i=0;i<G.vexnum;++i)
    		if(u == G.vexs[i])
    			return i;
    	return -1;
    }
    
    VertexType* GetVex(MGraph G,int v)
    { /* 初始条件: 图G存在,v是G中某个顶点的序号。操作结果: 返回v的值 */
    	if(v>=G.vexnum||v<0)
    		exit(ERROR);
    	return &G.vexs[v];
    }
    
    int FirstAdjVex(MGraph G,VertexType v)
    { /* 初始条件: 图G存在,v是G中某个顶点 */
    	/* 操作结果: 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1 */
    	int i,j=0,k;
    	k=LocateVex(G,v); /* k为顶点v在图G中的序号 */
    	if(G.kind==DN||G.kind==AN) /* 网 */
    	j=INFINITY;
    	for(i=0;i<G.vexnum;i++)
    	if(G.arcs[k][i].adj!=j)
    	return i;
    	return -1;
    }
    
    int NextAdjVex(MGraph G,VertexType v,VertexType w)
    { /* 初始条件: 图G存在,v是G中某个顶点,w是v的邻接顶点 */
    	/* 操作结果: 返回v的(相对于w的)下一个邻接顶点的序号, */
    	/*           若w是v的最后一个邻接顶点,则返回-1 */
    	int i,j=0,k1,k2;
    	k1=LocateVex(G,v); /* k1为顶点v在图G中的序号 */
    	k2=LocateVex(G,w); /* k2为顶点w在图G中的序号 */
    	if(G.kind==DN||G.kind==AN) /* 网 */
    	j=INFINITY;
    	for(i=k2+1;i<G.vexnum;i++)
    	if(G.arcs[k1][i].adj!=j)
    	return i;
    	return -1;
    }
    
    bool visited[MAX_VERTEX_NUM]; /* 访问标志数组(全局量) */
    Status(*VisitFunc)(VertexType); /* 函数变量 */
    void DFS(MGraph G,int v)
    { /* 从第v个顶点出发递归地深度优先遍历图G。算法7.5 */
    	VertexType w1,v1;
    	int w;
    	visited[v]=TRUE; /* 设置访问标志为TRUE(已访问) */
    	VisitFunc(G.vexs[v]); /* 访问第v个顶点 */
    	v1 = *GetVex(G,v);
    	for(w=FirstAdjVex(G,v1);w>=0;w=NextAdjVex(G,v1,w1 = *GetVex(G,w)))
    	if(!visited[w]) DFS(G,w); /* 对v的尚未访问的序号为w的邻接顶点递归调用DFS */
    }
    
    void DFSTraverse(MGraph G,Status(*Visit)(VertexType))
    { /* 初始条件: 图G存在,Visit是顶点的应用函数。算法7.4 */
    	/* 操作结果: 从第1个顶点起,深度优先遍历图G,并对每个顶点调用函数Visit */
    	/*           一次且仅一次。一旦Visit()失败,则操作失败 */
    	int v;
    	VisitFunc=Visit; /* 使用全局变量VisitFunc,使DFS不必设函数指针参数 */
    	for(v=0;v<G.vexnum;v++)
    		visited[v]=FALSE; /* 访问标志数组初始化(未被访问) */
    	for(v=0;v<G.vexnum;v++)
    		if(!visited[v])
    			DFS(G,v); /* 对尚未访问的顶点调用DFS */
    	printf("\n");
    }
    
    Status visit(VertexType i)
    {
    	printf("%d ",i);
    	return OK;
    }
    
    int main() {
    	int i,j,k,n;
    	MGraph g;
    	CreateUDG(&g);
    	DFSTraverse(g,visit);
    	return 0;
    }
    
    

    Pascal :

    program DFS;
    var v:array[0..100]of boolean;
        a:array[0..100,0..100]of integer;
        b:array[0..100]of integer;
        i,r,j,k,n:integer;
    procedure dfs(i:integer);
    var j:integer;
    begin
      v[i]:=true;
      b[k]:=i;inc(k);
      for j:=1 to n-1 do
        begin
          if (not v[j])and(a[i,j]=1)then dfs(j);
        end;
    end;
    {*******main*********}
    begin
      readln(n);
      fillchar(v,sizeof(v),false);
      for i:=0 to n-1 do
        for j:=0 to n-1 do
          begin
            read(a[i,j]);
          end;
      k:=0;
      for i:=0 to n-1 do
        if not v[i] then dfs(i);
      for i:=0 to n-1 do
        begin
          write(b[i],' ');
        end;
      writeln;
    end.
    
    
    

    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

    Information

    ID
    571
    Time
    1000ms
    Memory
    32MiB
    Difficulty
    (None)
    Tags
    # Submissions
    0
    Accepted
    0
    Uploaded By