DFS и стек

Question

В свободное время я изучаю алгоритмы CS, и у меня все хорошо, но у меня проблемы с пониманием матрицы смежности и DFS.

010100
101100
010110
111000
001001
000010

Если приведенный выше график не является ориентированным,вершины (a, f) (1-я строка - это вершина a и т. д.) Если график пересекается с использованием DFS и стека, начиная с вершины a.

Что будет с содержимым очереди после каждого добавления вершинили его убрали?Я предполагаю, что если одновременно вставлено 2, это будет в алфавитном порядке.

Может кто-нибудь объяснить, как это решить?

Answer 1

вы на a, поэтому ваш ряд равен 010100, а ваши соседи - b, d. поэтому поместите их в стек (и вы посетили a):

[d b]                  {a}

pop d, добавьте его к набору посещенных узлов и зайдите туда - 111000 (a, b, c) (но вы посетили a):

[c b b]                {a d}

pop c, добавьте его в набор посещенных узлов и зайдите туда - 010110 (b, d, e) (но мы посетили d):

[e b b b]              {a d c}

pop e, добавьте его в набор посещенных узлов и зайдите туда - 001001 (c, f) (но мы посетили c):

[f b b b]              {a d c e}

pop f, добавьте его в набор посещенных узлов и зайдите туда - 000010 (e) (но мы уже побывали там):

[b b b]                {a d c e f}

pop b, добавьте его к набору посещенных узлов и зайдите туда - 101100 (a, c, d) (но мы посетили все это):

[b b]                  {a d c e f b}

и мы посетили b, так что поп и выбросить дважды.

[]                     {a d c e f b}

ps это DFS и поэтому это стек, а не очередь (вы упомянули оба в вопросе). для BFS это было бы похоже, но вы добавляете в очередь, поэтому первые несколько шагов будут:

[d b]                  {a}
[b b c]                {a d}

, где b и c добавляются справа "вместо" слева "(но мы все равно выбираем слева, поэтому мы исследуем в ширину, и следующий узел будет b) .

Answer 2

В качестве дополнения к хорошему ответу Эндрю Кука, вы можете использовать библиотеку python networkx для визуализации поиска в DFS! По умолчанию DFS начинается с узла 0, но это можно изменить. Вы можете изменить график в начале, чтобы визуализировать более сложные системы.

import numpy as np
import networkx as netx
import pylab as plt

# Reshape the input string into a numpy array then a graph
A = np.array(map(int,"010100101100010110111000001001000010")).reshape(6,6)
G = netx.Graph(A)

# Compute the DFS tree
T = netx.dfs_tree(G)

# Show the edges traversed
print list(netx.dfs_edges(G))

# Plot the original graph
plt.subplot(121)
pos = netx.circular_layout(G)
netx.draw(G,pos,node_color='w',node_size=800)
netx.draw_networkx_nodes(G,pos,nodelist=[0],node_color='r',node_size=800)

# Plot the result of the DFS
plt.subplot(122)
pos = netx.circular_layout(T)
netx.draw(T,pos,node_color='w',node_size=800)
netx.draw_networkx_nodes(T,pos,nodelist=[0],node_color='r',node_size=800)

plt.show()