上一篇：广度优先搜索算法（bfs、广搜）java实现-数据结构和算法
如下图数据结构
则用邻接矩阵表示为：
private static int map[][]={
{0 ,3 ,6 ,-1 ,-1 ,-1 ,-1 ,-1,-1,-1,-1},
{3 ,0 ,-1 ,4 ,1 ,-1 ,-1 ,-1,3 ,-1,-1},
{6 ,-1 ,0 ,-1 ,-1 ,-1 ,-1 ,3 ,-1,-1,-1},
{-1 ,4 ,-1 ,0 ,3 ,-1 ,-1 ,6 ,-1,-1,-1},
{-1 ,1 ,-1 ,3 ,0 ,5 ,-1 ,-1,-1,-1,-1},
{-1 ,-1 ,-1 ,-1 ,5 ,0 ,2 ,-1,-1, 3, 3},
{-1 ,-1 ,-1 ,-1 ,-1 ,2 ,0 ,1 ,-1,-1,-1},
{-1 ,-1 ,3 ,6 ,-1 ,-1 ,1 ,0 ,-1,-1,-1},
{-1 ,3 ,-1 ,-1 ,-1 ,-1 ,-1 ,-1,0 ,-1,-1},
{-1 ,-1 ,-1 ,-1 ,-1 ,3 ,-1 ,-1,-1,0 ,3 },
{-1 ,-1 ,-1 ,-1 ,-1 ,-1 ,-1 ,-1,-1,3 ,0 }
};
横坐标和纵坐标代表第n个节点,值>0代表两个节点相连，并且值代表两个节点之间的权值（暂时没有用到），-1代表两个节点之间不相连。
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;
public class Test {
/**
* 邻接矩阵表示的图 的二维数组
* 横坐标和纵坐标代表第n个节点,值>0代表两个节点相连，并且值代表两个节点之间的权值（暂时没有用到），
* -1代表两个节点之间不相连
*/
private static int map[][]={
{0 ,3 ,6 ,-1 ,-1 ,-1 ,-1 ,-1,-1,-1,-1},
{3 ,0 ,-1 ,4 ,1 ,-1 ,-1 ,-1,3 ,-1,-1},
{6 ,-1 ,0 ,-1 ,-1 ,-1 ,-1 ,3 ,-1,-1,-1},
{-1 ,4 ,-1 ,0 ,3 ,-1 ,-1 ,6 ,-1,-1,-1},
{-1 ,1 ,-1 ,3 ,0 ,5 ,-1 ,-1,-1,-1,-1},
{-1 ,-1 ,-1 ,-1 ,5 ,0 ,2 ,-1,-1, 3, 3},
{-1 ,-1 ,-1 ,-1 ,-1 ,2 ,0 ,1 ,-1,-1,-1},
{-1 ,-1 ,3 ,6 ,-1 ,-1 ,1 ,0 ,-1,-1,-1},
{-1 ,3 ,-1 ,-1 ,-1 ,-1 ,-1 ,-1,0 ,-1,-1},
{-1 ,-1 ,-1 ,-1 ,-1 ,3 ,-1 ,-1,-1,0 ,3 },
{-1 ,-1 ,-1 ,-1 ,-1 ,-1 ,-1 ,-1,-1,3 ,0 }
};
public static void main(String[] args) {
dfs();
}
/**
* 深度优先搜索
* 思路：
* 1.从第一个节点开始当作当前节点
* 2.遍历当前节的所有没有被标记的子节点
* 3.如果有[没有被标记的子节点，则把当前节点入栈，把子节点赋值给当前节点，继续过程2。
* 否则，判断栈中是否含有元素，如果含有，则取出一个元素继续过程2，否则结束遍历
*/
public static void dfs() {
Set<Integer> set=new HashSet<Integer>();
/**
* 存储经过的节点路径
*/
LinkedList<Integer> path=new LinkedList<Integer>();
/**
* 储存待遍历节点的栈
*/
LinkedList<Node> stack=new LinkedList<Node>();
Node th=new Node(0, 0);//当前需要遍历的节点
map[th.i][th.p]=-1;
while(true) {
int p;
for(p=th.p;p<map.length;p++) {
/**
* 遍历当前节点的所有没有遍历过的子节点
*/
if(map[th.i][p]>0&&map[p][p]==0) {
th.p=p+1;
stack.addFirst(th);//当前节点入栈
if(!set.contains(th.i)) {
set.add(th.i);
path.addFirst(th.i);
}
th=new Node(p,0);
map[p][p]=-1;
p=0;
}
}
if(!set.contains(th.i)) {
set.add(th.i);
path.addFirst(th.i);
}
if(stack.size()>0) {
th=stack.removeFirst();
}else {
break;
}
}
while(path.size()>0){
System.out.print(path.removeLast()+"\t");
}
}
public static class Node{
public Integer i;//当前元素i
public Integer p;//当前遍历第p个元素
public Node(int i,int p) {
this.i=i;
this.p=p;
}
}
}
输出：
0 1 3 4 5 6 7 2 9 10 8