Une analyse de l'algorithme de fermeture transitive : recherche en profondeur d'abord versus recherche en largeur d'abord

Analyse de l'algorithme de fermeture transitive : recherche en profondeur d'abord vs recherche en largeur d'abord

Introduction :
L'algorithme de fermeture transitive est un algorithme important dans la théorie des graphes, utilisé pour construire une fermeture transitive de graphes de relations. Lors de la mise en œuvre de l'algorithme de fermeture transitive, deux stratégies de recherche courantes sont la recherche en profondeur d'abord (DFS) et la recherche en largeur d'abord (BFS). Cet article présentera ces deux stratégies de recherche en détail et analysera leur application dans l'algorithme de fermeture transitive à travers des exemples de code spécifiques.

1. Recherche en profondeur (DFS) :
La recherche en profondeur est une stratégie de recherche qui explore d'abord les nœuds profonds, puis revient aux nœuds moins profonds. Dans l'algorithme de fermeture transitive, nous pouvons utiliser DFS pour construire la fermeture transitive du graphe de relations. Ci-dessous, nous utilisons l'exemple de code suivant pour illustrer l'application de DFS dans l'algorithme de fermeture transitive :

# 传递闭包算法-深度优先搜索
def dfs(graph, start, visited):
    visited[start] = True

    for neighbor in graph[start]:
        if not visited[neighbor]:
            dfs(graph, neighbor, visited)

def transitive_closure_dfs(graph):
    num_nodes = len(graph)
    closure_table = [[0] * num_nodes for _ in range(num_nodes)]

    for node in range(num_nodes):
        visited = [False] * num_nodes
        dfs(graph, node, visited)

        for i in range(num_nodes):
            if visited[i]:
                closure_table[node][i] = 1

    return closure_table

Dans le code ci-dessus, nous définissons d'abord la fonction DFS pour la recherche en profondeur d'abord. Ensuite, nous utilisons DFS dans la fonction transitive_closure_dfs pour créer une fermeture transitive. Plus précisément, nous utilisons une matrice bidimensionnelle close_table pour enregistrer la relation de fermeture transitive. Après chaque DFS, nous utilisons le nœud correspondant à True dans le tableau visité comme nœud successeur direct du nœud d'origine et marquons la position correspondante comme 1 dans Closure_table.

2. Recherche en largeur d'abord (BFS) :
La recherche en largeur d'abord est une stratégie de recherche qui explore d'abord les nœuds adjacents, puis s'étend vers l'extérieur couche par couche. Dans l'algorithme de fermeture transitive, nous pouvons également utiliser BFS pour construire la fermeture transitive du graphe de relations. Ci-dessous, nous utilisons l'exemple de code suivant pour illustrer l'application de BFS dans l'algorithme de fermeture transitive :

from collections import deque

# 传递闭包算法-广度优先搜索
def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True

    while queue:
        node = queue.popleft()

        for neighbor in graph[node]:
            if not visited[neighbor]:
                visited[neighbor] = True
                queue.append(neighbor)

def transitive_closure_bfs(graph):
    num_nodes = len(graph)
    closure_table = [[0] * num_nodes for _ in range(num_nodes)]

    for node in range(num_nodes):
        visited = [False] * num_nodes
        bfs(graph, node, visited)

        for i in range(num_nodes):
            if visited[i]:
                closure_table[node][i] = 1

    return closure_table

Dans le code ci-dessus, nous définissons d'abord la fonction BFS pour la recherche en largeur d'abord. Contrairement à DFS, nous utilisons une file d'attente pour enregistrer les nœuds à explorer, et chaque fois qu'un nœud est exploré, tous ses nœuds voisins qui n'ont pas encore été visités sont ajoutés à la file d'attente. De même, BFS est utilisé pour créer une fermeture transitive dans la fonction transitive_closure_bfs. Plus précisément, nous utilisons également Closure_table pour enregistrer la relation de fermeture transitive et marquons la position correspondante comme 1 en fonction de la valeur du tableau visité.

Conclusion : 
La recherche en profondeur d'abord et la recherche en largeur d'abord sont deux stratégies de recherche couramment utilisées dans les algorithmes de fermeture transitive. Bien qu’ils diffèrent dans leur mise en œuvre, ils jouent tous un rôle important dans la construction de fermetures transitives. Cet article présente en détail les méthodes et les étapes de mise en œuvre de l'algorithme de fermeture transitive via DFS et BFS à travers des exemples de code spécifiques. J'espère que cet article pourra aider les lecteurs à mieux comprendre l'application de la recherche en profondeur et de la recherche en largeur dans les algorithmes de fermeture transitive.

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!