这里的图的深度优先算法利用了栈来实现。
图的深度遍历原则:
1 如果有可能,访问一个领接的未访问的节点,标记它,并把它放入栈中。
2 当不能执行规则 1 时,如果栈不为空,则从栈中弹出一个元素。
3 如果不能执行规则 1 和规则 2 时,则完成了遍历。
代码中的图使用的是Graph 图-邻接矩阵法
来表示,其他的表示法请见:Graph 图-邻接表法
代码中的Stack为辅助结构,用来记载访问过的节点。栈的详细描述可以见:ArrayStack 栈
,LinkedStack 栈
。
Vertex表示图中的节点,其中包含访问,是否访问,清除访问标志的方法。
Graph.main:提供简单测试。代码可以以指定下标的节点开始作深度遍历。
代码比较简单,除了Graph.dsf(int i)深度优先遍历算法外没有过多注释。
代码如下:
class Stack {
private int[] values;
private int pos = -1;
Stack(int size) {
values = new int[size];
}
void push(int value) { values[++pos] = value; }
int pop() { return values[pos--]; }
int peek() { return values[pos]; }
boolean isEmpty() { return pos == -1; }
}
class Vertex {
private Object value;
private boolean isVisited;
Vertex(Object value) {
this.value = value;
}
void visit() { isVisited = true; print(); }
void clean() { isVisited = false; }
boolean isVisited() { return isVisited; }
void print() { System.out.println(value); }
}
class Graph {
private Vertex[] vertexs;
private int[][] adjMat;
private int pos = -1;
Graph(int size) {
vertexs = new Vertex[size];
adjMat = new int[size][size];
}
void add(Object value) {
assert pos < vertexs.length;
vertexs[++pos] = new Vertex(value);
}
void connect(int from, int to) {
adjMat[from][to] = 1;
adjMat[to][from] = 1;
}
void disConnect(int from, int to) {
adjMat[from][to] = 0;
adjMat[to][from] = 0;
}
int findNeighbor(int index) {
for(int i=0; i<=pos; i++) {
if(adjMat[index][i] == 1 && !vertexs[i].isVisited()) return i;
}
return -1;
}
void dsf(int index) { //从指定下标的节点开始深度优先遍历
if(vertexs[index] == null) return; //如果图中没有指定下标节点,则退出
Stack s = new Stack(vertexs.length); //创建栈记载访问过的节点的下标
vertexs[index].visit(); //访问0节点
s.push(index); //记录0节点
while(!s.isEmpty()) { //如果还有记录的节点则继续
index = findNeighbor(s.peek()); //寻找栈顶节点的未访问过的邻居
if(index != -1) { //如果找到
vertexs[index].visit(); //访问该节点
s.push(index); //记录该节点
} else s.pop(); //没有未访问过的节点,则出栈
} //如果栈未空则代表遍历完成
clean(); //清除所有访问标致
}
void clean() { for(Vertex v: vertexs) if(v != null)v.clean(); }
public static void main(String[] args) {
Graph g = new 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);
}
}
分享到:
相关推荐
c++-深度优先遍历的递归实现版本
迷宫问题-广度优先遍历 迷宫 代码 算法
环路检测和打印(基于DFS--深度优先遍历) 简单的swing界面
邻接矩阵存储图的深度优先遍历 邻接矩阵表示图_深度_广度优先遍历
邻接矩阵存储图的深度优先遍历
图的深度遍历和广度遍历是两个重要的算法,这也是我们理解并掌握图这一数据结构的基础。通过此程序算法可以进一步掌握图的构造以及遍历的相关知识。
充分利用kNN查询自身的特点,基于高效的主存索引Δ-tree设计了一种新的kNN查询算法NR_DF_knn_Search,该算法采用非递归方式深度优先搜索Δ-tree中距离查询点较近的叶子节点,能够快速找到较优的kNN候选,更新修剪...
图的相关操作,对图实现深度优先遍历,值得!!!!!!
该程序是我写的博客“一起talk C栗子吧(第四十四回:C语言实例--深度优先遍历一)”的配套程序,共享给大家使用
无向图的连接表存储结构的创建...从编号为v的顶点出发,深度优先遍历图的算法 对具有G.vexnum个顶点的图的深度优先遍历的算法 从图G的v顶点出发,广度优先遍历图的算法 对具有G.vexnum个顶点的图的广度优先遍历的算法
深度优先遍历和广度优先遍历 建立图的应用等等
Graph(邻接矩阵)-两种遍历。 (1)建立图的邻接矩阵; (2)对其进行深度优先及广度优先遍历。
无向图建立、深度优先遍历和广度优先遍历实现算法[借鉴].pdf
在邻接矩阵的存储结构下,实现图的深度优先遍历和广度优先遍历。
c语言的数据结构图的深度优先遍历和广度优先遍历
建立图的邻接矩阵或邻接表存储并在此基础上实现图的深度优先遍历和广度优先遍历.doc
c++实现图的邻接表深度优先遍历,广度优先遍历
c数据结构链表数组以及深度优先遍历,假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点),则深度优先遍历可定义如下:首先访问出发点v,并将其标记为已访问过;然后依次从v出发搜索v的...
《数据结构与算法(C++)》相关 邻接表表示的图的深度优先遍历的动画演示