数据结构?图的深度优先遍历
对于图这种数据结构,一般有两种遍历即深度优先(dfs),和广度优先(bfs),假设我们有如下这张图:
访问过程
现在假设计算0到其它点的路径,根据深度优先遍历:
1、获取0的所有邻边 1、2、5、6(默认此顺序)
2、再获取1的邻边(无),获取2的邻边(无),获取5的邻边(0,3,4)
3、0访问过,不再获取邻边;然后获取3的邻边(5,4)
4、5访问过,不再获取邻边;然后获取4的邻边(5,6)
5、5访问过,不再获取邻边;然后获取6的邻边(0,4)
6、0访问过,4被访问过,此时退到步骤2,即将获取4的邻边,但4已经被访问过。退到步骤1,准备获取6的邻边,但6已经被访问过。所以根据深度优先遍历:顺序是0,1,2,5,3,4,6
注意:访问某一个顶点时,要进行标记是否被访问过
计算路径
那如何找到顶点到某一点的路径?
在上述获取邻边的过程中,我们其实已经知道了到达某一点的上一个点是谁,因此我们只需要建立一个数组记录一下,在寻找路径的时候,再进行一次查找即可
上述步骤我们可以这样记录(默认数组的值为-1):arr[0]=-1,arr[1]=0,arr[2]=0,arr[3]=5,arr[4]=3,arr[5]=0,arr[6]=4,假设要获取0~6的路径,那么会先找到arr[6]=4,接着arr[4]=3,接着arr[3]=5,接着arr[5]=0接着arr[0]=-1,结束。因此路径是0->5->3->4->6。同时我们也可以发现一个问题,0-6本来就有一条路,我们却绕了一个大圈子。因此,深度优先遍历不能保证最短路径
代码实现
public class Path { /**图的引用*/ private Graph G; /**起始点*/ private int s; /**记录dfs的过程中节点是否被访问*/ private boolean[] visited; /**记录路径, from[i]表示查找的路径上i的上一个节点*/ private int[] from; /**构造函数, 寻路算法, 寻找图graph从s点到其他点的路径*/ public Path(Graph graph, int s) { this.G = graph; visited = new boolean[graph.n()]; from = new int[G.n()]; for(int i=0;i<G.n();i++){ visited[i]=false; from[i] = -1; } this.s = s; dfs(s); } /***图的深度优先遍历*/ private void dfs(int v) { System.out.println("访问:"+v); visited[v]=true; for(int i:G.adj(v)){ if(!visited[i]){ from[i]=v; dfs(i); } } } /**查询从s点到w点的路径, 存放在vec中**/ public Vector path(int w){ Stack<Integer> s = new Stack<Integer>(); int p=w; while(p!=-1){ s.push(p); p=from[p]; } Vector<Integer> vector = new Vector<>(); while (!s.empty()){ vector.add(s.pop()); } return vector; } /**打印路径*/ public void showPath(int w){ Vector vector = this.path(w); for(int i=0;i<vector.size();i++){ System.out.print(vector.elementAt(i)); if(i==vector.size()-1){ System.out.print(""); } else{ System.out.print("->"); } } } public static void main(String[] args) { Graph sparseGraph= new SparseGraph(7,false); ReadGraph read = new ReadGraph(); read.readGraph(sparseGraph,"demo/testG.txt"); Path path = new Path(sparseGraph,0); path.showPath(6); } }
相关推荐
waitwolf 2020-07-30
roseying 2020-07-04
koushr 2020-11-12
zhangxiafll 2020-11-13
kikaylee 2020-10-31
范范 2020-10-28
MILemon 2020-10-22
hugebawu 2020-10-12
LauraRan 2020-09-28
shenwenjie 2020-09-24
omyrobin 2020-09-23
guangcheng 2020-09-22
qiangde 2020-09-13
hanyujianke 2020-08-18
晨曦之星 2020-08-14
xiesheng 2020-08-06
KAIrving 2020-08-02
xiesheng 2020-08-02