forked from zfman/AlgorithmCode
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathGraphTest.java
More file actions
71 lines (65 loc) · 1.89 KB
/
Copy pathGraphTest.java
File metadata and controls
71 lines (65 loc) · 1.89 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
package other;
import leetcode.common.AMGraph;
import leetcode.common.GraphUtils;
import utils.ArrayUtils;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
/**
* @author 刘壮飞
* https://github.com/zfman.
* https://blog.csdn.net/lzhuangfei.
*/
public class GraphTest {
public static void main(String[] args) {
AMGraph graph=GraphUtils.cin();
boolean[] visited=new boolean[graph.vexNum+1];
// dfs(graph,1,visited);
// GraphUtils.print(graph);
Queue<Integer> queue=new LinkedList<>();
bfs(graph,5,visited,queue);
}
/**
* 连通图的深度优先遍历，对于非连通图，
* 应该依次将顶点作为遍历的起始点
*
* @param graph 图
* @param v 访问的顶点
* @param visited 访问标志数组
*/
public static void dfs(AMGraph graph, int v, boolean[] visited){
System.out.println("visited::"+v);
visited[v]=true;
for(int i=1;i<=graph.vexNum;i++){
if(graph.arcs[v][i]!=0&&!visited[i]) dfs(graph,i,visited);
}
}
/**
* 图的广度优先遍历
*
* @param graph 图
* @param v 起始顶点
* @param visited 访问标志数组
* @param queue 队列
*/
public static void bfs(AMGraph graph, int v, boolean[] visited,Queue<Integer> queue){
if(!visited[v]){
visited[v]=true;
System.out.println("visited::"+v);
queue.offer(v);
}
while (!queue.isEmpty()){
Integer pop=queue.poll();
if(!visited[pop]){
visited[pop]=true;
System.out.println("visited::"+pop);
}
for(int i=1;i<=graph.vexNum;i++){
if(graph.arcs[pop][i]!=0&&!visited[i]){
queue.offer(i);
}
}
}
}
}