这里
图深度优先算法利用了栈来实现
图
深度遍历原则: 1 如果有可能
访问
个领接未访问节点标记它并把它放入栈中 2 当不能执行规则 1 时
如果栈不为空则从栈中弹出个元素 3 如果不能执行规则 1 和规则 2 时
则完成了遍历 代码中
图使用是Graph 图－邻接矩阵法 来表示其他表示法请见:Graph 图－邻接表法 代码中
Stack为辅助结构用来记载访问过节点栈详细描述可以见:ArrayStack 栈 LinkedStack 栈 Vertex表示图中
节点其中包含访问是否访问清除访问标志思路方法 Graph.
:提供简单测试代码可以以指定下标节点开始作深度遍历 代码比较简单
除了Graph.dsf(
i)深度优先遍历算法外没有过多注释 代码如下:
Java代码
Stack { private
values; private
pos = -1; Stack(
size) { values =
[size]; }
void push(
value) { values[
pos] = value; } pop
{ 
values[pos--]; } peek { values[pos]; } boolean isEmpty
{ pos 
-1; } }
Vertex { private Object value;
private boolean isVisited;
Vertex(Object value) {
this.value = value;
}
void visit
{ isVisited = true; pr; } void clean
{ isVisited = false; } boolean isVisited
{ isVisited; } void pr
{ 
.out.prln(value); } }
Graph { private Vertex
vertexs; private
adjMat; private
pos = -1; Graph(
size) { vertexs =
Vertex[size]; adjMat =
[size][size]; }
void add(Object value) {
assert pos < vertexs.length;
vertexs[
pos] = Vertex(value); }
void connect(
from, to) { adjMat[from][to] = 1;
adjMat[to][from] = 1;
}
void disConnect(
from, to) { adjMat[from][to] = 0;
adjMat[to][from] = 0;
}
findNeighbor( index) { for(
i=0; i<=pos; i) { 
(adjMat[index][i] 1 && !vertexs[i].isVisited) i; }
-1; }
void dsf(
index) { //从指定下标节点开始深度优先遍历 (vertexs[index] null) ; //如果图中没有指定下标节点则退出 Stack s =
Stack(vertexs.length); //创建栈记载访问过节点下标 vertexs[index].visit
; //访问0节点 s.push(index); //记录0节点
while(!s.isEmpty
) { //如果还有记录节点则继续 index = findNeighbor(s.peek
); //寻找栈顶节点未访问过邻居 (index != -1) { //如果找到 vertexs[index].visit
; //访问该节点 s.push(index); //记录该节点
}
s.pop; //没有未访问过节点则出栈 } //如果栈未空则代表遍历完成
clean
; //清除所有访问标致 }
void clean
{ for(Vertex v: vertexs) (v != null)v.clean; } public
void (String args) { Graph g =
Graph(20); g.add('a');
g.add('b');
g.add('c');
g.add('d');
g.add('e');
g.connect(0,1);
g.connect(1,2);
g.connect(0,3);
g.connect(3,4);
g.dsf(4);
}
}
最新评论