Analisis algoritma penutupan transitif: Carian pertama mendalam berbanding carian pertama luas

Analisis algoritma penutupan transitif: carian mendalam-dahulu vs carian luas-dahulu

Pengenalan:
Algoritma penutupan transitif ialah algoritma penting dalam teori graf, digunakan untuk membina penutupan transitif graf perhubungan. Apabila melaksanakan algoritma penutupan transitif, dua strategi carian biasa ialah carian mendalam-dahulu (DFS) dan carian luas-dahulu (BFS). Artikel ini akan memperkenalkan kedua-dua strategi carian ini secara terperinci dan menganalisis aplikasinya dalam algoritma penutupan transitif melalui contoh kod tertentu.

1. Carian pertama mendalam (DFS):
Carian pertama mendalam ialah strategi carian yang mula-mula meneroka nod dalam dan kemudian berundur ke nod yang lebih cetek. Dalam algoritma penutupan transitif, kita boleh menggunakan DFS untuk membina penutupan transitif graf perhubungan. Di bawah kami menggunakan contoh kod berikut untuk menggambarkan aplikasi DFS dalam algoritma penutupan transitif:

# 传递闭包算法-深度优先搜索
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

Dalam kod di atas, kami mula-mula mentakrifkan fungsi DFS untuk carian mendalam-dahulu. Seterusnya, kami menggunakan DFS dalam fungsi transitive_closure_dfs untuk membina penutupan transitif. Khususnya, kami menggunakan jadual_tutup matriks dua dimensi untuk merekodkan hubungan penutupan transitif. Selepas setiap DFS, kami menggunakan nod yang sepadan dengan True dalam tatasusunan yang dilawati sebagai nod pengganti langsung nod asal, dan menandakan kedudukan yang sepadan sebagai 1 dalam closure_table.

2. Carian pertama keluasan (BFS):
Carian pertama keluasan ialah strategi carian yang mula-mula meneroka nod bersebelahan dan kemudian mengembangkan ke luar lapisan demi lapisan. Dalam algoritma penutupan transitif, kita juga boleh menggunakan BFS untuk membina penutupan transitif graf perhubungan. Di bawah ini kami menggunakan contoh kod berikut untuk menggambarkan aplikasi BFS dalam algoritma penutupan transitif:

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

Dalam kod di atas, kami mula-mula mentakrifkan fungsi BFS untuk carian luas-dahulu. Berbeza daripada DFS, kami menggunakan baris gilir untuk menyimpan nod untuk diterokai, dan setiap kali nod diterokai, semua nod jirannya yang belum dilawati ditambahkan pada baris gilir. Begitu juga, BFS digunakan untuk membina penutupan transitif dalam fungsi transitive_closure_bfs. Khususnya, kami juga menggunakan closure_table untuk merekodkan perhubungan penutupan transitif dan menandakan kedudukan yang sepadan sebagai 1 berdasarkan nilai tatasusunan yang dilawati.

Kesimpulan:
Carian mendalam-dahulu dan carian luas-dahulu ialah dua strategi carian yang biasa digunakan dalam algoritma penutupan transitif. Walaupun mereka berbeza dalam pelaksanaan, semuanya memainkan peranan penting dalam membina penutupan transitif. Artikel ini memperkenalkan secara terperinci kaedah dan langkah melaksanakan algoritma penutupan transitif melalui DFS dan BFS melalui contoh kod tertentu. Saya harap artikel ini dapat membantu pembaca lebih memahami aplikasi carian mendalam-dahulu dan carian luas-dahulu dalam algoritma penutupan transitif.

Atas ialah kandungan terperinci Analisis algoritma penutupan transitif: Carian pertama mendalam berbanding carian pertama luas. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!