[算法]图(邻接矩阵)的深度遍历

package com.FeeLang;
import java.util.Scanner;
class ArcNode{
  int adjvex;
  ArcNode next;
}
class VertexNode{
  char vertex;
  ArcNode firstedge;
}
public class Graph {
  public static void main(String[] args){
    int n = 3;
    int e = 3;
    char[] vertexs = new char[n];
    vertexs[0] = 'A';
    vertexs[1] = 'B';
    vertexs[2] = 'C';
    
    Graph ALGraph = new Graph(vertexs, n, e);
    ALGraph.DFS();
  }
  
  public Graph(char[] vertexs, int node, int edge){
    this.node = node;
    this.edge = edge;
    
    adjlist = new VertexNode[this.node];
    visited = new boolean[this.node];
    for (int i = 0; i < this.node; i++){
      adjlist[i] = new VertexNode();
      adjlist[i].vertex = vertexs[i];
      adjlist[i].firstedge = null;
    }
    
    Scanner sc = new Scanner(System.in);
    for (int i = 0; i < this.edge; i++){
      int v, u;
      v = sc.nextInt();
      u = sc.nextInt();
      
      if (v >= this.node || u >= this.node){
        System.out.println("Wrong input");
        i--;
        continue;
      }
      //为节省内存采用前插法
      ArcNode s = new ArcNode();
      s.adjvex = u;
      s.next = adjlist[v].firstedge;
      adjlist[v].firstedge = s;
    }
  }
  
  //output: visited[u] is set to true for all nodes u reachable from v
  public void explore(int v){
    visited[v] = true;
    System.out.println(v);
    ArcNode an = adjlist[v].firstedge;
    while (an != null){
      if (!visited[v]){
        explore(an.adjvex);
      }
      an = an.next;
    }
  }
  
  
  public void DFS(){
    
    for (int i = 0; i < this.node; i++){
      if (!visited[i]){
        explore(i);
      }
    }
  }
  
  private VertexNode[] adjlist;
  private boolean[] visited;
  private int node;
  private int edge;
}

注意：Line28 and Line31，java数组的空间分配问题。

算法参考：《算法分析与设计》