Application pratique de la recherche prioritaire Java (DFS/BFS)

Profondeur d'abordRechercheDFS est la recherche en profondeur d'abord. En bref, le processus consiste à explorer chaque chemin de branchement possible jusqu'à ce qu'il ne puisse pas aller plus profondément, et chaque nœud ne peut être visité qu'une seule fois. Recherche en largeur d'abord BFS est une recherche en largeur d'abord. Tous les nœuds enfants obtenus en développant le nœud seront ajoutés à une file d'attente premier entré, premier sorti.

Analyse de l'algorithme de recherche DFS/BFS

Théorème 1 : La recherche en profondeur marque le temps requis pour tous les sommets connectés au point de départ et le temps des sommets La somme des degrés est directement proportionnelle.

Supposons que nous ayons deux points v et w. Dans un graphique, lorsque v visite w en premier, l'arête v-w passe de l'état non coché à coché , cette arête a été vérifiée. visité une fois. Lorsque w visite v, le bord w-v est à nouveau vérifié, mais on constate qu'il a déjà été vérifié. À ce moment, ce bord a été visité deux fois. De plus, il n’existe aucune autre situation qui entraîne la visite du bord v-w (w-v). Par conséquent, on peut voir que chaque arête du graphe sera visitée deux fois, arête × 2 = sommet Σ degré (somme des degrés de chaque sommet). Donc directement proportionnel.

Théorème 2 : Généralement, les problèmes qui peuvent être résolus en utilisant la recherche en profondeur d'abord peuvent être convertis en recherche en largeur d'abord.

Les avantages de la recherche en profondeur sont : RécursionFacile à comprendre et simple. Cependant, la recherche en profondeur n'a pas d'objectif clair, tandis que la recherche en largeur recherche de près à loin et peut trouver la solution optimale dans de nombreux cas, et les boucles sont plus efficaces que la récursivité, et là il n'y a aucun risque de débordement de pile. L'efficacité de la recherche en largeur dans les graphes clairsemés est beaucoup plus rapide que la recherche en profondeur et est presque la même dans les graphes denses. Lorsque la recherche en largeur n’est pas nécessairement nécessaire, nous pouvons essayer d’utiliser la recherche en profondeur.

Théorème 3 : Lors de l'utilisation de listes de contiguïté comme méthode d'enregistrement graphique, la complexité temporelle de la recherche en profondeur d'abord et de la recherche en largeur d'abord est O(V+E).

Le temps nécessaire pour accéder aux éléments dépend principalement de la méthode d'enregistrement des données graphiques. Qu'il s'agisse d'une recherche en profondeur d'abord ou d'une recherche en largeur, l'ensemble du graphique doit être vérifié avant que le calcul puisse être effectué. terminé. Le principal facteur de perte de temps dépend en partie de la méthode d'enregistrement. Lorsque vous utilisez la matrice de contiguïté comme méthode d'enregistrement des données, la complexité est O(n²), et la liste de contiguïté n'a que (. sommet + nombre d'arêtes × 2) données. Nous ne devons effectuer que la moitié du nombre d'arêtes et l'autre moitié peut être exemptée par inspection. Par conséquent, lorsque vous utilisez des listes de contiguïté comme méthode d’enregistrement graphique, la complexité temporelle de DFS et de BFS est O(V+E).

Structure de base des données - classe de graphes

L'algorithme de profondeur d'abord et l'algorithme de largeur d'abord sont des algorithmes basés sur la théorie des graphes. Avant d'implémenter l'application, implémentez d'abord la structure de données de base de la classe graphe non orienté. La classe
Graph utilise V pour définir des points fixes, E pour définir des bords et LinkedList<Integer>[ ] pour définir des listes de contiguïté.

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

}

Génériques dans la classe GraphArray

Il convient de noter que bien que seuls les tableaux génériques soient déclarés ici, la conversion de type Array ordinaire est mis en œuvre, mais il existe également des dangers de sécurité cachés.
Un programme similaire à celui ci-dessous se compile avec succès mais contient des erreurs car les génériques sont effacés lors de l'exécution ObjectL'affectation entre les classes de tableau ne signale pas d'erreur.

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

Cette situation doit être comprise, mais cet article présente principalement l'algorithme, et cette partie ne sera pas trop discutée. Je voudrais énumérer ici les possibilités d'erreur.

Problème de connectivité

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

}

Il y a un problème avec le chemin à point unique

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

Chemin le plus court en un seul point

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

Calcul des composants connectés

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

    }

}

Problème de graphe acyclique

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

}

Problème de graphe biparti bicolore

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!