一：定義鄰接表結構儲存圖
package 圖的遍歷;//鄰接表實現圖的建立//儲存邊
class EdgeNode {int index; // 習慣了用index，其實標準寫法是(adjVertex)int value; // 權值EdgeNode nextArc; // 指向下一條弧
}// 鄰接表節點的類型
class VertexNode {String name;EdgeNode firstArc = new EdgeNode(); // 指向第一條弧
}public class Graph {VertexNode[] adjList; // 保存鄰接表的頭節點int e; // 圖的邊數int v; // 圖的頂點數boolean[] visit;public Graph(int v, int e) {this.v = v;this.e = e;adjList = new VertexNode[e + 1]; // 學習Java養成的好習慣，動態分配空間,創建頂點表數組visit = new boolean[e + 1]; //標記for (int i = 0; i < e; i++) {visit[i] = false;}}
}
二：DFS過程
package 圖的遍歷;public class DFSGraph {public static void DFS(Graph G, int k) {System.out.println(G.adjList[k].name);G.visit[k] = true;EdgeNode p = new EdgeNode();p = G.adjList[k].firstArc;while(p!=null){if(G.visit[p.index]!=true){DFS(G,p.index);}p=p.nextArc;}}}
三：建立圖
package 圖的遍歷;import java.util.Scanner;public class CreateGraph {private static Graph G;public static Graph getGraph(){return G;}public static void createGraph() {Scanner sc = new Scanner(System.in);System.out.println("請輸入頂點數v和邊數e:");int v = sc.nextInt();int e = sc.nextInt();G = new Graph(v, e);System.out.println("請輸入各頂點信息:");for (int i = 0; i < G.v; i++) {G.adjList[i] = new VertexNode();G.adjList[i].name = sc.next();G.adjList[i].firstArc = null; // 不可或缺}System.out.println("請輸入各邊信息(用空格隔開):");for (int i = 0; i < G.e; i++) {EdgeNode en1 = new EdgeNode();// 保證e1,e2都是合法輸入String e1 = sc.next();String e2 = sc.next();int v1 = Index(e1);int v2 = Index(e2);en1.index = v1; // en1的下標是v1en1.nextArc = G.adjList[v2].firstArc;G.adjList[v2].firstArc = en1;EdgeNode en2 = new EdgeNode();en2.index = v2; // en2的下標是v2en2.nextArc = G.adjList[v1].firstArc;G.adjList[v1].firstArc = en2;}}public static void outputGraph() { //不知道為何空指針異常try {System.out.println("輸出鄰接表存儲情況：");EdgeNode en = new EdgeNode();for (int i = 0; i < G.e; i++) {System.out.print(G.adjList[i].name);en = G.adjList[i].firstArc;while (en != null) {System.out.print("->" + G.adjList[en.index].name);en = en.nextArc;}System.out.println();}} catch (NullPointerException e) {}}private static int Index(String e1) {for (int i = 0; i < G.v; i++) {if (G.adjList[i].name.equals(e1)){return i;}}return -1;}
}
四：測試
package 圖的遍歷;public class GraphDemo {public static void main(String[] args) {CreateGraph.createGraph();CreateGraph.outputGraph();System.out.println("DFS圖的過程如下：");DFSGraph.DFS(CreateGraph.getGraph() , 0);}
}
/** 請輸入頂點數v和邊數e: 4 5 * 請輸入各頂點信息: a b c d * 請輸入各邊信息(用空格隔開): * a b* a c* a d * b c * b d*/
五，測試結果
java實現評論功能、
