图的搜索

一个使用邻接矩阵的dfs和bfs简单程序。
深搜原理

从一个节点开始,一直搜索一条路并将每个点压入栈中,直到搜索到最后一条路径;无法搜索为止。就进行回退,从栈中依次弹出,直到下一个能够访问的节点;便继续重复,直到栈底为空,结束循环。

广搜原理

从一个节点开始,访问它所有能访问的子节点,并将其放入队列。当找到所有子节点时,就让对头出队。反复循环,直到队列为空。结束循环。
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Graphical {

    public static void main(String[] args) {
        int[][] gra1 = {{0,1,1,1,0,0}
                        ,{1,0,0,0,1,0}
                        ,{1,0,0,0,1,0}
                        ,{1,0,0,0,0,1}
                        ,{0,1,1,0,0,0}
                        ,{0,0,0,0,0,0}};
        for(int[] i: gra1){
            for(int j: i){
                System.out.print(j+" ");
            }
            System.out.println();
        }
        
        dfs(gra1);
        bfs(gra1);

    }
    //广度优先搜索
    public static void bfs(int[][] gra) {
        System.out.println("广度优先搜索:");
        //定义辅助数组
        boolean[] visited = new boolean[gra.length];
        //初始化为未访问
        for(int i = 0;i < gra.length;i ++){
                visited[i] = false;
        }
        Queue<Integer> q = new LinkedList<>();
        q.offer(1);                //从2号开始搜索,并将2号放入栈中
        visited[1] = true;
        System.out.println(2);
        while(!q.isEmpty()){  //队列不为空,就继续搜索,直到搜索完
            for(int i = 0;i < gra.length;i ++){
                if(gra[q.peek()][i] == 1){       //当有连接点
                    if(!visited[i]){             //且未访问时
                        q.offer(i);                 //添加连接点
                        System.out.println(i+1); //并输出
                        visited[i] = true;       //将访问数组设为已访问
                    }
                }else{
                    continue;
                }
            }
            q.poll();                            //弹出队列中已访问完的元素
        }
    }
    //深度优先搜索
    public static void dfs(int[][] gra) {
        System.out.println("深度优先搜索:");
        //定义辅助数组
        boolean[] visited = new boolean[gra.length];
        //初始化为未访问
        for(int i = 0;i < gra.length;i ++){
            visited[i] = false;
        }
        //定义栈
        Stack<Integer> s = new Stack<>();
        //从2号开始搜索,并将2号压入栈
                visited[1] = true;
            s.push(1);
            System.out.println(2);
            /*for(boolean b: visited){
                System.out.print(b+" ");
            }*/
        //进行搜索
        while(!s.empty()){  //当栈为空时,我们就访问完所有节点了。
            //t为查找变量,当找到能联通的点时,赋值为真。
            boolean t = false;
            for(int i = 0;i < gra.length;i ++){
                if(gra[s.peek()][i] == 1){
                    //System.out.println();
                    //System.out.println("连接点:"+s.peek() + " " + i);
                    //System.out.println("值:" + gra[s.peek()][i]);
                    if(visited[i]){  //如果这个点已经访问过了,就不再访问。
                        continue;
                    }else{
                        s.push(i);                     //把没访问的点压入栈中  
                        visited[i] = true;            //并把visited设为已访问
                        t = true;                
                        System.out.println(i+1);    //输出访问的点
                        //查看哪些节点被访问
                        /*for(boolean b: visited){
                            System.out.print(b+" ");
                        }*/
                        break;
                    }
                }
            }
            if(!t){
                s.pop();  //没有联通点时,返回上一个节点。
            }
        }
    }
    
}
Last modification:March 23rd, 2019 at 03:03 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment