文档章节

深度优先搜索算法

朱方圆
 朱方圆
发布于 2016/08/12 00:59
字数 1467
阅读 61
收藏 2

1.深度优先搜索算法解决的问题

遍历图里面的每一个顶点且,每个顶点只访问一次

图相关的概念可以看上一篇文章“广度优先搜索”,思路差不多,深度优先在对待子结点时是不断访问其子结点直到全部访问完,而广度优先就是挨个访问子结点,子结点的访问是存在队列里面。深度优先的访问顺序是用递归模拟的栈,如果把广度优先里面的队列换成栈,那么就成了深度优先遍历。

2.代码(使用上一篇文章的代码)

import java.util.*;

public class Main{

    private int[] marked;
    private int[][] map;
    private int    num;
    private int[] path;

    private int target;
    private int leave;
    public static void main(String[] args){

        Main b=new Main(5,3,1);
        b.addEdg(0,1);
        b.addEdg(0,4);
        b.addEdg(4,3);
        b.addEdg(1,2);
        b.dfs(0);


    }
    public Main(int n,int a,int b){
        this.num=n;
        this.marked=new int[n];
        this.map=new int[n][n];
        this.target=b;
        this.leave=a;
        this.path=new int[n];

    }

    public void addEdg(int a,int b){
        map[a][b]=1;
        map[b][a]=1;

    }
    public int[] getNeighbor(int a){

        ArrayList list=new ArrayList();

        for(int i=0;i<num;i++){
            if(map[a][i]==1){
                list.add(i);
            }
        }

       int size=list.size();
        int[] result=new int[size];
        for(int i=0;i<size;i++){
            result[i]=(Integer)list.get(i);
        }

        return result;

    }
    public void dfs(int index){

        marked[index]=1;
        for(Integer tmp:getNeighbor(index)){
            if(marked[tmp]!=1) {
                System.out.println(tmp);
                dfs(tmp);//这里使用递归不断访问子结点,直到没有子结点然后回退
            }


        }
    }
    public void bfs(){
        Queue q=new PriorityQueue<>();//队列用来存储需要访问的点
        q.add(leave);
        marked[leave]=1;
        flag: while(!q.isEmpty()){
            int start=(Integer)q.poll();//用来取出相应的元素
            for(Integer tmp:getNeighbor(start)){

                if(marked[tmp]!=1){
                    path[tmp]=start;
                    if(tmp==target){
                        //到达目的地

                        break flag;
                    }
                    marked[tmp]=1;

                    q.add(tmp);
                }
            }

        }

        int index=target;

        while(index!=leave){
            System.out.println(index);
            index=path[index];

        }
        System.out.println(index);

    }

}

3.用深度优先搜索解决查找路径的问题

也就是给定一个图和两个点,问这两个点之间有没有路径

基本的思路是做一次深度优先搜索,看看那个点有没有被标记,如果被标记了就使用回溯的办法获取路径即可,需要注意的是回溯的方式。

import java.util.*;
public class Main{

    private int[][] map;
    private int num;
    private int[] marked;
    private int[] path;
    public static void main(String[] args){

        Main main=new Main(5);
        main.add(0, 1);
        main.add(0, 4);
        main.add(4, 3);
        main.add(1, 2);
        main.dfs(0);

        Iterator iterator=main.getPathTo(3).iterator();

        while(iterator.hasNext()){
            System.out.print(iterator.next()+" ");
        }



    }
    public boolean hasPath(int a){
        return marked[a]==1;
    }
    public Iterable getPathTo(int b){

        if(!hasPath(b))return null;
        //使用栈把整个路径变成反向
        Stack<Integer> p=new Stack<Integer>();
        for(int x=b;x!=0;x=path[x]){
            p.push(x);
        }
        p.push(0);

        return p;

    }
    public Main(int a){
        this.num=a;
        map=new int[a][a];
        marked=new int[a];
        path=new int[a];
    }
    public void add(int a,int b){

        map[a][b]=1;
        map[b][a]=1;

    }
    public void dfs(int index){

        marked[index]=1;
        for(int tmp:getNeighbor(index))
            if(marked[tmp]!=1) {
                marked[tmp]=1;
                path[tmp]=index;//记录可以到达的路径
                dfs(tmp);//递归查询
            }
    }
    public int[] getNeighbor(int index){
        ArrayList arrayList=new ArrayList();
        for(int i=0;i<num;i++){
            if(map[index][i]==1){
                arrayList.add(i);
            }
        }
        int size=arrayList.size();
        int[] result=new int[size];
        for(int i=0;i<size;i++){

            result[i]=(Integer)arrayList.get(i);
        }

        return result;

    }
}

4.使用深度优先搜索解决查找连通分量的问题

连通分量:可以互相到达的点组成的集合

那么算法就是,对每个点进行访问,直到所有的访问完了,每次完了之后递增连通分量数目

代码

import java.util.*;
public class Main{

    private int[][] map;
    private int num;
    public int[] marked;
    private int[] path;
    private int[] connect;
    public int count=0;
    public static void main(String[] args){

        Main main=new Main(13);
        main.add(0,1);
        main.add(0,2);
        main.add(0,5);
        main.add(0,6);

        main.add(3,4);
        main.add(3,5);
        main.add(5,4);
        main.add(4,6);

        main.add(7,8);

        main.add(9,10);
        main.add(9,11);
        main.add(9,12);

        main.add(11,12);


        for(int i=0;i<13;i++){
            if(main.marked[i]!=1){

                main.dfs(i);
                main.count++;
            }
        }

        System.out.println("连通分量数目:"+main.getCount());
        System.out.println("2和9是否相连: "+main.isConnected(2,9));
        
    }
    public int getCount(){
        return count;
    }
    public boolean isConnected(int a,int b){
        return connect[a]==connect[b];
    }
    public Main(int a){
        this.num=a;
        map=new int[a][a];
        marked=new int[a];
        path=new int[a];
        connect=new int[a];
    }
    public void add(int a,int b){

        map[a][b]=1;
        map[b][a]=1;

    }
    public void dfs(int index){

        connect[index]=count;
        marked[index]=1;
        for(int tmp:getNeighbor(index))
            if(marked[tmp]!=1) {
                marked[tmp]=1;
                path[tmp]=index;//记录可以到达的路径
                dfs(tmp);//递归查询
            }
    }
    public int[] getNeighbor(int index){
        ArrayList arrayList=new ArrayList();
        for(int i=0;i<num;i++){
            if(map[index][i]==1){
                arrayList.add(i);
            }
        }
        int size=arrayList.size();
        int[] result=new int[size];
        for(int i=0;i<size;i++){

            result[i]=(Integer)arrayList.get(i);
        }

        return result;

    }
}

运行的结果为

连通分量数目:3
2和9是否相连: false

需要注意的地方:

  • 保存是否为同一个连通分量的方式,记录点属于哪一个连通分量
  • 需要对连通分量计数

 

5.深度优先搜索解决环状图的问题

假设这里没有同一个结点上的环,也不存在平行边

思路,当一个图有环的时候,我们从某一个结点访问进去,那么一定会访问到已经访问到的点而且不是回退的那个点。另外一个需要注意的就是,可能有多个分量,因此需要分别查询。

代码,使用上题的图

import java.util.*;
public class Main{

    private int[][] map;
    private int num;
    public int[] marked;
    private int[] path;

    public int count=0;
    public boolean hasCircle;
    public static void main(String[] args){

        Main main=new Main(13);
        main.add(0,1);
        main.add(0,2);
        main.add(0,5);
        main.add(0,6);

        //main.add(3,4);
        main.add(3,5);
        //main.add(5,4);
        main.add(4,6);

        main.add(7,8);

        main.add(9,10);
        main.add(9,11);
        //main.add(9,12);

        main.add(11,12);


        for(int i=0;i<13;i++){
            if(main.marked[i]!=1){

                main.dfs(i,i);
                main.count++;
            }
        }

        System.out.println("是否有环:"+main.hasCircle);

        
    }


    public Main(int a){
        this.num=a;
        map=new int[a][a];
        marked=new int[a];
        path=new int[a];

    }
    public void add(int a,int b){

        map[a][b]=1;
        map[b][a]=1;

    }
    public void dfs(int index,int parent){


        marked[index]=1;
        for(int tmp:getNeighbor(index))
            if(marked[tmp]!=1) {
                marked[tmp]=1;
                path[tmp]=index;//记录可以到达的路径
                dfs(tmp,index);//递归查询
            }else if(tmp!=parent) hasCircle=true;//如果当前访问的点不是parent说明有环
    }
    public int[] getNeighbor(int index){
        ArrayList arrayList=new ArrayList();
        for(int i=0;i<num;i++){
            if(map[index][i]==1){
                arrayList.add(i);
            }
        }
        int size=arrayList.size();
        int[] result=new int[size];
        for(int i=0;i<size;i++){

            result[i]=(Integer)arrayList.get(i);
        }

        return result;

    }
}

 

© 著作权归作者所有

朱方圆
粉丝 2
博文 24
码字总数 20023
作品 0
南京
私信 提问

暂无文章

电子字典C语言链表版

#define _CRT_SECURE_NO_WARNINGS#include <stdio.h>#include <stdlib.h>#include <string.h>#include <time.h>struct dict{ char *key; char *content; struct dict *ne......

holdbody
27分钟前
4
0
windows 查看 端口使用情况

资料 https://jingyan.baidu.com/article/3c48dd34491d47e10be358b8.html 统计端口连接数 netstat -an|find "8080" /c...

zaolonglei
28分钟前
3
0
OSG 屏幕空间环境光遮蔽(SSAO)讲义3 算法的核心

先介绍SSAO 接着介绍SSAO的核心算法 延迟着色法的采样 颜色采样 把像机的几个参数传入Shader SSAO渲染 建立SSAO摄像机 SSAO摄像机显示漫反射采样 先用上下像素点的方案, 再次讲原理. 换用RGB...

洛克人杰洛
48分钟前
2
0
聊聊rocketmq的AccessChannel

序 本文主要研究一下rocketmq的AccessChannel AccessChannel rocketmq-client-4.5.2-sources.jar!/org/apache/rocketmq/client/AccessChannel.java public enum AccessChannel { /** ......

go4it
昨天
9
0
自己实现 aop 和 spring aop

上文 说到,我们可以在 BeanPostProcessor 中对 bean 的初始化前化做手脚,当时也说了,我完全可以生成一个代理类丢回去。 代理类肯定要为用户做一些事情,不可能像学设计模式的时候创建个代...

sanri1993
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部