图的深度优先搜索和广度优先搜索模板

一、邻接矩阵实现：

package Template;//邻接矩阵实现图的广搜和深搜import java.util.*;public class Map1 {/** * @param args */static int[][] G;static int k;static boolean[] visited;static boolean isfirst = true;public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n;int m, t;n = sc.nextInt();while (n-->0) {isfirst = true;k = sc.nextInt();m = sc.nextInt();t = sc.nextInt();G = new int[k][k];visited = new boolean[k];for (int i = 0; i < m; i++) {int u = sc.nextInt();int v = sc.nextInt();G[u][v] = 1;G[v][u] = 1;}bfs(t);System.out.println();//visited = new boolean[k];//dfs(t);//System.out.println();}}//广搜public static void bfs(int v) {boolean isfirst = true;LinkedList<Integer> que = new LinkedList<Integer>();que.add(v);while (!que.isEmpty()) {v = que.poll();if (isfirst) {System.out.print(v);isfirst = false;} elseSystem.out.print(" " + v);visited[v] = true;for (int i = 0; i < k; i++) {if (G[v][i] == 1 && !visited[i]) {que.add(i);visited[i] = true;}}}}//深搜public static void dfs(int v) {visited[v] = true;if (isfirst) {System.out.print(v);isfirst = false;} elseSystem.out.print(" " + v);for (int i = 0; i < k; i++) {if (G[v][i] == 1 && !visited[i])dfs(i);}}}

二邻接表实现：

package Template;//邻接表实现图的广搜和深搜import java.util.*;public class Map2 {static class Edge implements Comparable<Edge> {int to;// 边的终点public Edge(int t) {to = t;}@Overridepublic int compareTo(Edge o) {return to - o.to;}}static class VNode {int from;// 边的起点PriorityQueue<Edge> pri = new PriorityQueue<Edge>();public VNode(int v) {from = v;}}static VNode[] V;static int k;// 图的顶点static boolean[] visited;static boolean isfirst;public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n;int m, t;n = sc.nextInt();while (n-- > 0) {k = sc.nextInt();m = sc.nextInt();t = sc.nextInt();visited = new boolean[k];isfirst = true;V = new VNode[k];for (int i = 0; i < k; i++)V[i] = new VNode(i);for (int i = 0; i < m; i++) {int u = sc.nextInt();// 起点int v = sc.nextInt();// 终点Edge e = new Edge(v);V[u].pri.add(e);// 无向图的对称e = new Edge(u);V[v].pri.add(e);}bfs(t);// dfs(t);System.out.println();}}// 广搜public static void bfs(int v0) {boolean isfirst = true;Queue<Integer> que = new LinkedList<Integer>();que.add(v0);while (!que.isEmpty()) {v0 = que.poll();if (!visited[v0]) {if (isfirst) {System.out.print(v0);isfirst = false;} elseSystem.out.print(" " + v0);visited[v0] = true;}while (!V[v0].pri.isEmpty()) {Edge e = V[v0].pri.poll();// 得到以v为起点的终点链表if (!visited[e.to])que.add(e.to);}}}// 深搜public static void dfs(int v0) {visited[v0] = true;if (isfirst) {System.out.print(v0);isfirst = false;} elseSystem.out.print(" " + v0);while (!V[v0].pri.isEmpty()) {Edge p = V[v0].pri.poll();if (!visited[p.to])dfs(p.to);}}}