啊哈算法——图
深度和广度优先究竟是啥
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;
}
}