Java优质实现

解题思路:

注意事项:

参考代码:

import java.util.Scanner;

class Vertex{
   //用来存储顶点中的数据
   int val;
}
class MyGraph{
   Vertex [] vertex;//存储顶点内的值
   int arc[][];//邻接矩阵
   int numVertex;//顶点个数
   int numEdge;//边的个数

   public MyGraph(int numVertex, int numEdge) {
       this.numVertex = numVertex;
       this.numEdge = numEdge;
       this.vertex=new Vertex[numVertex];
       this.arc=new int [numVertex][numVertex];
       for (int i = 0; i < arc.length; i++) {
           arc[i]=new int[numVertex];
       }
   }
   public MyGraph(int numVertex){
       this.numVertex = numVertex;
       this.vertex=new Vertex[numVertex];
       this.arc=new int [numVertex][numVertex];
       for (int i = 0; i < arc.length; i++) {
           arc[i]=new int[numVertex];
       }
   }
}

public class Main{
   public static void main(String[] args) {
       Scanner scanner = new Scanner(System.in);
       int vertexNum=scanner.nextInt();
       MyGraph myGraph = new MyGraph(vertexNum);
       for (int i = 0; i < myGraph.numVertex; i++) {
           for (int j = 0; j < myGraph.numVertex; j++) {
               myGraph.arc[i][j]=scanner.nextInt();
           }
       }
       DFS(myGraph);

   }
   public static boolean [] isVisited;//标记已经访问过的节点
   public static void DFS(MyGraph g){
       //对这个图进行深度优先遍历
       isVisited=new boolean[g.numVertex];
       for (int i = 0; i < g.numVertex; i++) {
           isVisited[i]=false;
       }
       for (int i = 0; i < g.numVertex; i++) {
           if(!isVisited[i]){
               DFS(g,i);//
           }
       }
   }
   public static void DFS(MyGraph g,int i){
       System.out.print(i+" ");//访问第i个顶点，这里是打印
       isVisited[i]=true;
       for (int j = 0; j < g.numVertex; j++) {
           if(g.arc[i][j]>0&&g.arc[i][j]<Integer.MAX_VALUE&&!isVisited[j]){
               DFS(g,j);
           }
       }
   }
}