자바 우선순위 검색(DFS/BFS) 활용
- 黄舟원래의
- 2017-05-07 09:34:242554검색
깊이 우선검색DFS는 깊이 우선 검색입니다. 간단히 말하면, 이 프로세스는 더 이상 들어갈 수 없고 각 노드를 한 번만 방문할 수 있을 때까지 가능한 모든 분기 경로를 드릴다운하는 것입니다. 너비 우선 검색 BFS는 너비 우선 검색입니다. 노드를 확장하여 얻은 모든 하위 노드는 선입선출 대기열에 추가됩니다.
DFS/BFS 검색 알고리즘 분석
정리 1: 깊이 우선 검색은 시작점에 연결된 모든 정점에 소요되는 시간을 표시하고 정점의 시간 각도의 합은 정비례합니다.
그래프에서 v가 w를 처음 방문하면 가장자리 v-w가 선택되지 않은 상태 로 변경되며 이 가장자리는 변경되었습니다. 한 번 방문했습니다. w가 v를 방문할 때 간선 w-v를 다시 확인하는데, 이때 이미 이 간선을 두 번 방문한 것으로 확인됩니다. 또한, 에지 v-w(w-v)를 방문하게 만드는 다른 상황은 없습니다. 따라서 그래프의 각 모서리는 두 번 방문하게 됨을 알 수 있으며, 모서리 × 2 = 정점 Σ 차수(각 정점의 차수의 합)입니다. 그래서 정비례합니다.
정리 2: 일반적으로 깊이 우선 탐색으로 풀 수 있는 문제는 너비 우선 탐색으로 변환될 수 있습니다.
깊이 우선 검색의 장점은 재귀이해하기 쉽고 간단합니다. 그러나 깊이 우선 탐색은 명확한 목적이 없는 반면, 너비 우선 탐색은 근거리부터 원거리까지 탐색하며 많은 경우 최적의 해를 찾을 수 있으며 루프가 재귀보다 효율적이며, 스택 오버플로의 위험이 없습니다. 희소 그래프에서 너비 우선 검색의 효율성은 깊이 우선 검색보다 훨씬 빠르며 밀집 그래프에서도 거의 동일합니다. 너비 우선 검색이 반드시 필요하지 않은 경우 깊이 우선 검색을 사용해 볼 수 있습니다.
정리 3: 그래프 기록 방법으로 인접 목록을 사용할 때 깊이 우선 탐색과 너비 우선 탐색의 시간 복잡도는 모두 O(V+E)입니다.
요소에 액세스하는 데 필요한 시간은 주로 그래프 데이터의 기록 방법에 따라 다릅니다. 깊이 우선 탐색이든 너비 우선 탐색이든 전체 그래프를 확인해야 계산이 가능합니다. 시간이 많이 걸리는 주요 요인은 부분적으로 기록 방법에 따라 다릅니다. 데이터를 기록하는 방법으로 인접 행렬을 사용할 경우 복잡도는 O(n2)이며, 인접 목록은 ( 정점 + 모서리 수 × 2) 데이터입니다. 모서리 수의 절반만 수행하면 되고 나머지 절반은 검사를 통해 제외할 수 있습니다. 따라서 그래프 기록 방법으로 인접 목록을 사용하는 경우 DFS와 BFS 모두 시간 복잡도는 O(V+E)입니다.
기본 데이터 구조 - 그래프 클래스
깊이 우선 알고리즘과 너비 우선 알고리즘은 그래프 이론을 기반으로 한 알고리즘입니다. 애플리케이션을 구현하기 전에 먼저 기본 무방향 그래프 클래스 데이터 구조를 구현합니다.
Graph 클래스는 V를 사용하여 고정점을 정의하고, E를 사용하여 가장자리를 정의하며, LinkedListcb2ea6ec594694ef40e2e39d0d6b88f7[ ]를 사용하여 인접 목록을 정의합니다.
package Graph;
import java.util.LinkedList;
public class Graph {
private final int V;
private int E;
private LinkedList<Integer>[] adj;
public Graph(int V) {
this.V = V;
this.E = 0;
adj = (LinkedList<Integer>[]) new LinkedList[V];
for (int v = 0; v < V; v++)
adj[v] = new LinkedList<>();
}
public int V() {
return V;
}
public int E() {
return E;
}
public void addEdge(int v, int w) {
adj[v].add(w);
adj[w].add(v);
E++;
}
public LinkedList<Integer> adj(int v) {
return adj[v];
}
public int degree(int v,Graph g){
int count = 0;
for(int s : adj(v))
count++;
return count;
}
}Graph 클래스의 제네릭Array
여기서는 일반 배열만 선언했지만 일반 배열 유형이 사용된다는 점에 유의해야 합니다. 달성되었지만 보안숨겨진 위험도 있습니다.
아래 프로그램과 유사한 프로그램은 성공적으로 컴파일되지만 런타임 중에 제네릭이 지워지기 때문에 오류가 발생합니다. 객체배열 클래스 간 할당에서는 오류가 보고되지 않습니다.
public static void main(String[] args) {
LinkedList<Integer>[] adj;
adj = (LinkedList<Integer>[]) new LinkedList[5];
Object o = adj;
Object[] oa = (Object[]) o;
List<String> li = new LinkedList<>();
li.add("s");
oa[0] = li;
System.out.println(adj[0]);
}이러한 상황을 이해해야 하지만, 이 글에서는 주로 알고리즘을 소개하므로 이 부분에 대해서는 크게 다루지 않겠습니다. 여기에 오류 가능성을 나열하고 싶습니다.
연결 문제
package Graph;
import java.util.ArrayDeque;
import java.util.Queue;
public class Connected {
private Graph g;
private boolean[] marked;
private int count;
public Connected(Graph g) {
this.g = g;
marked = new boolean[g.V()];
}
/**
* DFS算法计算连通结点
*
* @param s
* 起点
*/
public void DFS(int s) {
marked[s] = true;
count++;
for (int w : g.adj(s))
if (!marked[w])
DFS(w);
}
/**
* BFS算法计算连通结点
*
* @param s
* 起点
*/
public void BFS(int s) {
Queue<Integer> q = new ArrayDeque<>();
q.add(s);
marked[s] = true;
count++;
while (!q.isEmpty()) {
for (int w : g.adj(q.poll()))
if (!marked[w]) {
marked[w] = true;
count++;
q.add(w);
}
}
}
/**
* 初始化marked标记数组状态
*/
public void cleanMarked() {
for (boolean b : marked)
b = false;
}
/**
* 返回该起点总连通结点数
*
* @return 连通结点数
*/
public int count() {
return count;
}
/**
* 判断一个结点是否被连通
*
* @param v
* 判断结点
* @return 连通状态
*/
public boolean isMarked(int v) {
return marked[v];
}
}단일 포인트 경로에 문제가 있습니다
package Graph;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;
public class Paths {
private Graph g;
private boolean[] marked;
private int[] edgeTo;
public Paths(Graph g) {
this.g = g;
marked = new boolean[g.V()];
edgeTo = new int[g.V()];
}
/**
* DFS算法计算单点路径问题
*
* @param s
* 起点
*/
public void DFS(int s) {
marked[s] = true;
for (int w : g.adj(s))
if (!marked[w]) {
edgeTo[w] = s;
DFS(w);
}
}
/**
* 初始化marked标记数组状态
*/
public void cleanMarked() {
for (boolean b : marked)
b = false;
}
/**
* 判断一个结点是否被连通
*
* @param v
* 判断结点
* @return 连通状态
*/
public boolean isMarked(int v) {
return marked[v];
}
/**
* 是否存在从s到v的路径，默认调用深度优先，可以选择广度优先
*
* @param s
* 起点
* @param v
* 终点
* @return 存在状态
*/
public boolean hasPathTo(int s, int v) {
DFS(s);
if (isMarked(v))
return true;
return false;
}
}단일 포인트 최단 경로
package Graph;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;
public class Paths {
private Graph g;
private boolean[] marked;
private int[] edgeTo;
public Paths(Graph g) {
this.g = g;
marked = new boolean[g.V()];
edgeTo = new int[g.V()];
}
/**
* DFS算法计算单点路径问题
*
* @param s
* 起点
*/
public void DFS(int s) {
marked[s] = true;
for (int w : g.adj(s))
if (!marked[w]) {
edgeTo[w] = s;
DFS(w);
}
}
/**
* BFS算法计算单点最短路径问题
*
* @param s
* 起点
*/
public void BFS(int s) {
Queue<Integer> q = new ArrayDeque<>();
q.add(s);
marked[s] = true;
while (!q.isEmpty()) {
for (int w : g.adj(q.poll()))
if (!marked[w]) {
marked[w] = true;
edgeTo[w] = s;
q.add(w);
}
}
}
/**
* 初始化marked标记数组状态
*/
public void cleanMarked() {
for (boolean b : marked)
b = false;
}
/**
* 判断一个结点是否被连通
*
* @param v
* 判断结点
* @return 连通状态
*/
public boolean isMarked(int v) {
return marked[v];
}
/**
* 是否存在从s到v的路径，默认调用深度优先，可以选择广度优先
*
* @param s
* 起点
* @param v
* 终点
* @return 存在状态
*/
public boolean hasPathTo(int s, int v) {
DFS(s);
// BFS(v);
if (isMarked(v))
return true;
return false;
}
/**
* 输出最短路径
*
* @param s
* 起点
* @param v
* 终点
*/
public void pathTo(int s, int v) {
if (!hasPathTo(s, v))
return;
BFS(s);
// DFS(s); 但深度优先可能不是最短路径
Stack<Integer> sta = new Stack<>();
sta.push(v);
for (int i = v; i != s; i = edgeTo[i])
sta.push(edgeTo[i]);
while (!sta.isEmpty())
System.out.println(sta.pop() + " ");
}
}연결 구성 요소 계산
package Graph;
public class ConnectedComp {
private Graph g;
private boolean[] marked;
private int count;
private int[] id;
public ConnectedComp(Graph g) {
this.g = g;
id = new int[g.V()];
marked = new boolean[g.V()];
}
/**
* 调用方法，便利全部结点判断分量数
*/
public void DFS() {
for (int s = 0; s < g.V(); s++) {
if (!marked[s]) {
DFS(s);
count++;
}
}
}
/**
* DFS算法计算连通结点
*
* @param s
* 起点
*/
private void DFS(int s) {
marked[s] = true;
id[s] = count;
for (int w : g.adj(s))
if (!marked[w])
DFS(w);
}
/**
* 初始化marked标记数组状态
*/
public void cleanMarked() {
for (boolean b : marked)
b = false;
}
/**
* 返回该图总分量数目
*
* @return 分量数
*/
public int count() {
return count;
}
/**
* 返回该节点属于第几个分量
*
* @param s
* 判断结点
* @return 分量组数
*/
public int id(int s) {
return id[s];
}
}비순환 그래프 문제
package Graph;
public class Cycle {
private Graph g;
private boolean[] marked;
private boolean hasCycle;
public Cycle(Graph g) {
this.g = g;
marked = new boolean[g.V()];
for(int s=0;s<g.V();s++)
if(!marked[s])
DFS(s,s);
}
/**
* DFS算法计算无环图问题
*
* @param s
* 起点
*/
public void DFS(int s, int v) {
marked[s] = true;
for (int w : g.adj(s))
if (!marked[w])
DFS(w, s);
else if (w != v)
hasCycle = true;
}
/**
* 初始化marked标记数组状态
*/
public void cleanMarked() {
for (boolean b : marked)
b = false;
}
/**
* 判断是否有环
*
* @return 判断结果
*/
public boolean hasCycle() {
return hasCycle;
}
}Bipart 그래프 2 -색상 문제
아아아아위 내용은 자바 우선순위 검색(DFS/BFS) 활용의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!