NetworkX — популярная библиотека Python для анализа и визуализации сетей и графиков. В этой статье мы сосредоточимся на изучении различных методов создания дерева поиска в глубину (DFS) с использованием NetworkX. DFS — это алгоритм обхода графа, который исследует как можно дальше каждую ветвь перед возвратом. Полученное дерево DFS дает полезную информацию о структуре и связности графа.

Метод 1: встроенная функция dfs_tree() NetworkX

import networkx as nx
# Create a graph
G = nx.Graph()
G.add_edges_from([(1, 2), (1, 3), (2, 4), (3, 4), (4, 5)])
# Generate DFS tree using the built-in dfs_tree() function
dfs_tree = nx.dfs_tree(G)
# Print the edges of the DFS tree
print(list(dfs_tree.edges()))

Метод 2. Использование обхода DFS и фильтрации границ

import networkx as nx
# Create a graph
G = nx.Graph()
G.add_edges_from([(1, 2), (1, 3), (2, 4), (3, 4), (4, 5)])
# Perform DFS traversal
dfs_edges = nx.dfs_edges(G)
# Create a new graph and add DFS edges as edges
dfs_tree = nx.Graph(dfs_edges)
# Print the edges of the DFS tree
print(list(dfs_tree.edges()))

Метод 3. Ручной обход DFS с помощью рекурсии

import networkx as nx
# Create a graph
G = nx.Graph()
G.add_edges_from([(1, 2), (1, 3), (2, 4), (3, 4), (4, 5)])
# Initialize a set to track visited nodes
visited = set()
# Initialize an empty graph for DFS tree
dfs_tree = nx.Graph()
# Recursive DFS function
def dfs(node):
    visited.add(node)
    for neighbor in G.neighbors(node):
        if neighbor not in visited:
            dfs_tree.add_edge(node, neighbor)
            dfs(neighbor)
# Start DFS traversal from a specific node
start_node = 1
dfs(start_node)
# Print the edges of the DFS tree
print(list(dfs_tree.edges()))

В этой статье мы рассмотрели различные методы создания дерева DFS с помощью NetworkX. Встроенная функция dfs_tree() предоставляет удобный способ напрямую получить дерево DFS. В качестве альтернативы мы можем выполнить обход DFS на графе и отфильтровать ребра, чтобы построить дерево DFS. Мы также продемонстрировали реализацию DFS вручную с использованием рекурсии. Эти методы обеспечивают гибкость в анализе и визуализации структуры и связности графов. Используя возможности NetworkX, исследователи и ученые, работающие с данными, могут получить ценную информацию из своих графических данных.