啊哈算法——图

深度和广度优先究竟是啥

DFS深度优先

首先以一个未被访问过的顶点作为起始顶点，沿当前顶点的边走到未访问过的顶点；当没有未访问过的顶点时，则回到上一个顶点，继续试探访问别的顶点，直到所有的顶点都被访问

package ch5;

import javax.swing.plaf.synth.SynthEditorPaneUI;
import java.util.Scanner;

public class TUDFS {
    static int[] book = new int[100];
    static int[][] e= new int[100][100];
    static int sum = 0;
    static int n;
    public static void dfs(int cur){//cur代表当前顶点的编号
        System.out.println(cur);
        sum++;//访问每一个顶点，就+1
        if(sum == n) return;//所有的顶点都遍历完，直接退出
        for (int i = 1; i<= n; i++){
            //判断当前顶点cur到顶点i是否有边，判断顶点i是否呗访问过
            if (e[cur][i] ==1 && book[i]==0){
                book[i] = 1;
                dfs(i);//从顶点i继续出发遍历
            }
        }
    }

    public static void main(String[] args) {
        int m,a,b;
        //初始化二维矩阵
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        //初始化矩阵
        for (int i = 1; i<=n;i++){
            for (int j=1;j<=m;j++){
                if(i == j) e[i][j] = 0;
                else e[i][j] = Integer.MIN_VALUE;
            }
        }
        //读入顶点之间的边
        for (int i =1; i<=m ;i++){
            a =scanner.nextInt();
            b =scanner.nextInt();
            e[a][b] = 1;
            e[b][a] = 1;
        }
        //从一号顶点开始出发
        book[1] = 1;
        dfs(1);
        scanner.close();
    }

}

BFS广度优先

首先以一个未被访问过的顶点作为起点，访问其所有相邻的顶点，然后对每个相邻的顶点，再访问他们相邻的未被访问过的顶点，直到所有顶点都被访问过，遍历结束。

package ch5;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class TUBFS {
    static int[] book = new int[100];
    static int[][] e = new int[100][100];
    static int[] queue = new int[100];
    static int n;
    //双指针
    static int head = 1,tail = 1;//定义首部和尾部

    public static void main(String[] args) {
        int m,a,b;
        //初始化二维矩阵
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        //初始化矩阵
        for (int i = 1; i<=n;i++){
            for (int j=1;j<=m;j++){
                if(i == j) e[i][j] = 0;
                else e[i][j] = Integer.MIN_VALUE;
            }
        }
        //读入顶点之间的边
        for (int i =1; i<=m ;i++){
            a =scanner.nextInt();
            b =scanner.nextInt();
            e[a][b] = 1;
            e[b][a] = 1;
        }
        //从一号队列出发
        queue[1] = 1;
        tail ++;
        book[1] = 1;

        while(head < tail&& tail <= n){
            int cur = queue[head];
            for (int i=1;i<=n;i++){
                if (e[cur][i] == 1 && book[i] == 0){
                    queue[tail] = i;
                    tail ++;
                    book[i] = 1;
                }
                if(tail >n) break;
            }
            head++;
        }
        for (int i=1;i<=n;i++){
            System.out.println(queue[i]);
        }
    }

}

城市地图—图的深度优先遍历

package ch5;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class TUBFS {
    static int[] book = new int[100];
    static int[][] e = new int[100][100];
    static int[] queue = new int[100];
    static int n;
    //双指针
    static int head = 1,tail = 1;//定义首部和尾部

    public static void main(String[] args) {
        int m,a,b;
        //初始化二维矩阵
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        //初始化矩阵
        for (int i = 1; i<=n;i++){
            for (int j=1;j<=m;j++){
                if(i == j) e[i][j] = 0;
                else e[i][j] = Integer.MIN_VALUE;
            }
        }
        //读入顶点之间的边
        for (int i =1; i<=m ;i++){
            a =scanner.nextInt();
            b =scanner.nextInt();
            e[a][b] = 1;
            e[b][a] = 1;
        }
        //从一号队列出发
        queue[1] = 1;
        tail ++;
        book[1] = 1;

        while(head < tail&& tail <= n){
            int cur = queue[head];
            for (int i=1;i<=n;i++){
                if (e[cur][i] == 1 && book[i] == 0){
                    queue[tail] = i;
                    tail ++;
                    book[i] = 1;
                }
                if(tail >n) break;
            }
            head++;
        }
        for (int i=1;i<=n;i++){
            System.out.println(queue[i]);
        }
    }

}

小结

图的概念

图就是有N个顶点和M条边组成的集合

有向图和无向图

有向图：如果给图的每一条边规定一个方向，那么得到的图称为有向图，其边也称有向边。在有向图中，与一个点相关联的边有出边和入边支付，而与一个有向边关联的两个点也有始点和终点之分。

无向图：边没有方向的图称为无向图

无向图的代码

package ch5;

import java.util.Scanner;

public class CityMapDFS2 {
    static int min = Integer.MAX_VALUE;//设定一个最小值
    static int destination;
    static int[][] e = new int[100][100];
    static int[] book = new int[100];
    public static void DFS(int cur,int dis){
        if(dis > min)return;
        if (cur == destination) {
            if (dis < min) min = dis;
            return;
        }
        for (int j = 1; j<=destination;j++) {
            //判断当前城市cur到城市j是否有路，并判断当前城市是否已经在走过的路中
            if (e[cur][j] != Integer.MAX_VALUE && book[j] == 0){
                book[j] = 1;
                DFS(j,dis+e[cur][j]);//从j城市继续出发遍历
                book[j] = 0;//退回到前一步的探索，取消对j的标记
            }
        }
    }

    public static void main(String[] args) {
        int a,b,c;
        Scanner scanner = new Scanner(System.in);
        destination = scanner.nextInt();
        int m =scanner.nextInt();
        for (int i=1;i<=destination;i++){
            for (int j =1; j<=destination;j++){
                if (i==j) e[i][j] = 0;
                else e[i][j] = Integer.MAX_VALUE;
            }
        }
        for (int i=1; i<=m;i++){
            a = scanner.nextInt();
            b = scanner.nextInt();
            c = scanner.nextInt();
            e[a][b] = c;
            e[b][a] = c;//无向图
        }
        book[1]=1;
        DFS(1,0);
        System.out.println(min);
    }
}

最少转机—图的广度优先遍历

package ch5;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
/*
5 7 1 5
1 2
1 3
2 3
2 4
3 4
3 5
4 5
2

Process finished with exit code 0

 */
public class ZSZJBFS {
    static Queue<Node> queue = new LinkedList<>();
    static int[][] e  = new int[100][100];
    static int[] book = new int[100];
    static int start,end,n,m,a,b,cur,falg;
    static {
        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();
        m = scanner.nextInt();
        start = scanner.nextInt();
        end = scanner.nextInt();

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (i == j) e[i][j] = 0;
                else e[i][i] = Integer.MAX_VALUE;
            }
        }

        for (int i = 1; i <= m; i++) {
            a = scanner.nextInt();
            b = scanner.nextInt();
            e[a][b] = 1;
            e[b][a] = 1;
        }
    }

    public static void main(String[] args) {
        Node node = new Node(start,0);//初始化第一个城市
        queue.add(node);//把第一个城市加入队列
        book[start] = 1;//把第一个城市做标记

        //当队列不为空的时候循环
        while (!queue.isEmpty()){
            cur = queue.peek().x;
            for (int j =1;j<=n;j++){//一次每个城市循环遍历
                if (e[cur][j] == 1 && book[j] ==0){
                    //如果这个城市可以和cur当前城市连接并且没有在队列当中，那么把这个j加入到队列中
                    Node node1 = new Node(j,queue.peek().s+1);
                    queue.add(node1);
                    book[j] = 1;//标记这个队列
                }
                if (queue.peek().x == end){
                    falg = 1;
                    break;
                }
            }
            if (falg == 1)
                break;
            queue.remove();
        }
        System.out.println(queue.peek().s);
    }






}
class Node{
    int x;//城市编号
    int s;//转机次数
    public Node(){}
    public Node(int x, int s){
        this.x =x;
        this.s =s;
    }
}