Depth FirstSucheDFS ist Depth First Search. Kurz gesagt besteht der Prozess darin, einen Drilldown in jeden möglichen Verzweigungspfad durchzuführen, bis er nicht mehr tiefer gehen kann und jeder Knoten nur einmal besucht werden kann. Breitensuche BFS ist Breitensuche. Alle durch Erweitern des Knotens erhaltenen untergeordneten Knoten werden einer First-In-First-Out-Warteschlange hinzugefügt.

DFS/BFS-Suchalgorithmus-Analyse

Theorem 1: Die Tiefensuche markiert die Zeit, die für alle mit dem Startpunkt verbundenen Eckpunkte und benötigt wird die Zeit der Scheitelpunkte Die Summe der Grade ist direkt proportional.

Angenommen, wir haben zwei Punkte v und w. Wenn v zuerst w besucht, ändert sich die Kante v-w vom ungeprüften -Status , diese Kante wurde einmal besucht. Wenn w v besucht, wird die Kante w-v erneut überprüft, es wird jedoch festgestellt, dass sie bereits überprüft wurde. Zu diesem Zeitpunkt wurde diese Kante zweimal besucht. Abgesehen davon gibt es keine andere Möglichkeit, die dazu führt, dass die Kante v-w (w-v) besucht wird. Daher ist ersichtlich, dass jede Kante im Diagramm zweimal besucht wird, Kante × 2 = Grad des Scheitelpunkts Σ (die Summe der Grade jedes Scheitelpunkts). Also direkt proportional.

Theorem 2: Im Allgemeinen können Probleme, die mithilfe der Tiefensuche gelöst werden können, in eine Breitensuche umgewandelt werden.

Die Vorteile der Tiefensuche sind: RekursionLeicht verständlich und einfach. Die Tiefensuche hat jedoch keinen klaren Zweck, während die Breitensuche von nah nach fern sucht und in vielen Fällen die optimale Lösung finden kann. Schleifen sind effizienter als Rekursion und dort Es besteht keine Gefahr eines Stapelüberlaufs. Die Effizienz der Breitensuche in dünn besetzten Diagrammen ist viel schneller als die Tiefensuche und in dichten Diagrammen nahezu gleich. Wenn eine Breitensuche nicht unbedingt erforderlich ist, können wir versuchen, eine Tiefensuche zu verwenden.

Satz 3: Bei Verwendung von Adjazenzlisten als Diagrammaufzeichnungsmethode beträgt die zeitliche Komplexität sowohl der Tiefensuche als auch der Breitensuche O(V+E).

Die für den Zugriff auf Elemente erforderliche Zeit hängt hauptsächlich von der Aufzeichnungsmethode der Diagrammdaten ab. Unabhängig davon, ob es sich um eine Tiefensuche oder eine Breitensuche handelt, muss das gesamte Diagramm überprüft werden, bevor die Berechnung durchgeführt werden kann Der Hauptzeitaufwand hängt teilweise von der Aufzeichnungsmethode ab. Bei Verwendung der Adjazenzmatrix als Methode zum Aufzeichnen von Daten beträgt die Komplexität O(n²) und die Adjazenzliste hat nur (. Scheitelpunkt + Kantenanzahl × 2) Wir müssen nur die Hälfte der Kantenanzahl ausführen, und die andere Hälfte kann durch Inspektion ausgenommen werden. Daher beträgt die zeitliche Komplexität von DFS und BFS bei Verwendung von Adjazenzlisten als Diagrammaufzeichnungsmethode O(V+E).

Grundlegende Datenstruktur – Graphenklasse

Tiefen-First-Algorithmus und Breiten-First-Algorithmus sind Algorithmen, die auf der Graphentheorie basieren. Bevor Sie die Anwendung implementieren, implementieren Sie zunächst die grundlegende Klassendatenstruktur ungerichteter Graph. Die Klasse
Graph verwendet V zum Definieren von Festpunkten, E zum Definieren von Kanten und LinkedList<Integer>[ ] zum Definieren von Adjazenzlisten.

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;
    }

}

Nach dem Login kopieren

Generika in der Graph-KlasseArray

Es ist zu beachten, dass hier zwar nur generische Arrays deklariert werden, jedoch eine gewöhnliche Array-Typkonvertierung erfolgt implementiert ist, aber es gibt auch Sicherheit versteckte Gefahren.
Ein Programm, das dem folgenden ähnelt, wird erfolgreich kompiliert, enthält jedoch Fehler, da Generika während der Laufzeit gelöscht werden. ObjektZuweisung zwischen Array-Klassen meldet keinen Fehler.

  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]);
    }

Nach dem Login kopieren

Diese Situation muss verstanden werden, aber in diesem Artikel wird hauptsächlich der Algorithmus vorgestellt, und dieser Teil wird nicht zu ausführlich besprochen. Ich möchte hier die Fehlermöglichkeiten auflisten.

Verbindungsproblem

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];
    }

}

Nach dem Login kopieren

Es liegt ein Problem mit dem Einzelpunktpfad vor

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;
    }
}

Nach dem Login kopieren

Einpunktiger kürzester Weg

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() + " ");
    }
}

Nach dem Login kopieren

Berechnung verbundener Komponenten

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];

    }

}

Nach dem Login kopieren

Azyklisches Diagrammproblem

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;
    }

}

Nach dem Login kopieren

Bipart-Graph-Zweifarbenproblem

package Graph;

public class TwoColor {

    private Graph g;
    private boolean[] color;
    private boolean[] marked;
    private boolean isTwoColor;

    public TwoColor(Graph g) {
        this.g = g;
        marked = new boolean[g.V()];
        color = new boolean[g.V()];
        isTwoColor = true;
        for(int s=0;s<g.V();s++)
            if(!marked[s])
                DFS(s);
    }

    /**
     * DFS算法计算二分图问题
     * 
     * @param s
     *            起点
     */
    public void DFS(int s) {
        marked[s] = true;
        for (int w : g.adj(s))
            if (!marked[w]) {
                color[w] = !color[s];
                DFS(w);
            } else if (color[w] == color[s])
                isTwoColor = false;
    }

    /**
     * 初始化marked标记数组状态
     */
    public void cleanMarked() {
        for (boolean b : marked)
            b = false;
    }

    /**
     * 判断是否为二分图
     * 
     * @return 判断结果
     */
    public boolean isTwoColor() {
        return isTwoColor;
    }
}

Nach dem Login kopieren

Das obige ist der detaillierte Inhalt vonPraktische Anwendung der Java-Prioritätssuche (DFS/BFS). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!