这里用深度优先遍历存在矩阵里面的图。
深度优先利用的是栈的FIFO特性。为此遍历到底后，可以找到最相邻的节点继续遍历。实现深度优先，还需要在节点加上一个访问标识，来确定该节点是否已经被访问过了。
源码：
package mygraph;
import java.util.Stack;
public class DFS_Vertex {
//创建一个我们需要的节点类
class Vertex {
private char lable;
private int val;
private boolean wasvisited;
Vertex(char lable) {
this.lable = lable;
}
Vertex() {
}
}
private char lable; // 矩阵元素
private Vertex[][] list = new Vertex[20][20];
private Vertex[] vertexList = new Vertex[20];
private int nVerts; // 当前顶点下标
DFS_Vertex() {
this.nVerts = 0;
for(int i = 0; i < 20; i ++) {
for(int j = 0; j < 20; j ++) {
list[i][j] = new Vertex();
}
}
}
// 增加一个顶点
public void addVertex(char lable) {
vertexList[nVerts++] = new Vertex(lable);
}
// 增加一条边
public void addEdge(int start, int end) {
list[start][end].val = 1;
list[end][start].val = 1;
}
// 打印矩阵
public void printMatrix() {
for (int i = 0; i < nVerts; i++) {
for (int j = 0; j < nVerts; j++) {
System.out.print(list[i][j].val);
}
System.out.println();
}
}
//显示字符
public void showVertex(int v) {
System.out.print(vertexList[v].lable + "\t");
}
//获得邻接未访问节点
public int getAdjUnvisitedVertex(int v) {
for(int j = 0; j < nVerts; j ++) {
if((list[v][j].val == 1) && (vertexList[j].wasvisited == false)) {
return j;
}
}
return -1;
}
//DFS
public void DFS() {
Stack<Integer> s = new Stack();
vertexList[0].wasvisited = true;
showVertex(0);
s.push(0);
int v;
while(s.size() > 0) {
v = getAdjUnvisitedVertex(s.peek());
if(v == -1) {
s.pop();
}else {
vertexList[v].wasvisited = true;
showVertex(v);
s.push(v);
}
}
for(int j = 0; j < nVerts; j ++) {
vertexList[j].wasvisited = false;
}
}
}测试程序：
public static void main(String[] args) {
DFS_Vertex ds = new DFS_Vertex();
ds.addVertex('A'); //
ds.addVertex('B'); //
ds.addVertex('C'); //2
ds.addVertex('D'); //
ds.addVertex('E'); //
ds.addEdge(0, 1); //A-B
ds.addEdge(0, 3); //A-D
ds.addEdge(1, 4); //B-E
ds.addEdge(3, 4); //D-E
ds.addEdge(4, 2); //E-C
ds.printMatrix();
ds.DFS();
}测试结果：
10001
00001
10001
01110
A B E C D