题目描述:求图从某个顶点出发的所有深度优先遍历序列
如上图表示的是从A出发的深度优先遍历的解空间树,对解空间树进行先根次序遍历,采用的是深度优先搜索策略,从根结点开始,到达树的一个叶子结点表示图的一条深度优先搜索路径,如(A,B,C,D,E};继续遍历,当搜索了图中所有顶点时,就完成了图的一次深度优先遍历,如(A,B,C,D,E,F},因此所有的深度优先序列应为:
ABCDEF
ABCEDF
ABECDF
ABEDCF
ACBEDF
ACDEBF
ACEBDF
ADCBEF
ADCEBF
ADEBCF
ADECBF
遇到的问题:目前只会把所有到叶子的序列输出,不知道该怎么继续遍历到完整的序列再输出,求大家帮助,想了很久都没成功,真的很难受。
下面是我的代码:
//返回顶点vi在vj后的后继邻接顶点序号 ;若j=-1,返回vi的第一个邻接顶点序号;若不存在后继邻接顶点,返回-1。用于7.3节图的遍历算法
protected int next(int i, int j)
{
int n=this.vertexCount();
if(i>=0 && i<n && j>=-1 && j<n && i!=j)
for(int k=j+1; k<n; k++) //当j=-1时,k从0开始寻找后继邻接顶点
if(this.matrix.get(i,k)>0 && this.matrix.get(i,k)<MAX_WEIGHT)//权值表示有边
return k;
return -1;
}
public boolean isover(int i,boolean []visited)
{
for (int j = 0; j < this.vertexCount(); j++) {
if (j == i) continue;
if (this.matrix.get(i, j) != MAX_WEIGHT && !visited[j])//只要存在一个与他相邻的结点不为空,就把temp标记为true
{
return false;
}
}
return true;
}
public void printPathAll(int i)
{
boolean[] visited = new boolean[matrix.columns];//false 表示该结点未被访问
String stack="";
fun(i,visited,stack);
}
public void fun(int i,boolean visited[],String stack) {
if(!visited[i])//如果该点未被访问,则访问它,并且递归访问他的下一条边
{
stack+=this.get(i);
visited[i]=true;
for(int j=next(i,-1); j!=-1; j=next(i,j)){
{
if(!visited[j])
fun(j,visited,stack);
}
}
if (isover(i,visited))
{
System.out.println(stack);
}
visited[i]=false;
}
}