DFS 및 스택

Question

여유 시간에 CS 알고리즘을 배우고 있고 꽤 잘 지내고 있지만 인접 매트릭스 및 DFS를 이해하는 데 문제가 있습니다. 6 개 정점 (A, F) (1 행 정점 등등이다) 그래프를 트래버스 DFS와 스택을 사용하는 경우와

010100 
101100 
010110 
111000 
001001 
000010 

위에서 무향 그래프이면

는하는 버텍스 시작.

버텍스를 삽입하거나 제거 할 때마다 큐의 내용은 어떻게됩니까? 두 개가 동시에 삽입되면 알파벳순으로 표시됩니다.

누군가 어떻게 해결할 수 있습니까?

Answer 1

당신은 에 있습니다. 행은 010100이고 이웃은 b, d입니다. 그래서 스택에 사람을 넣어 (당신은 a를 방문한) :

[d b]     {a} 

팝 d 방문 노드 세트에 추가, 거기 방문 - 111000 (a, b, c)을 (하지만 당신은 방문 a) :

[c b b]    {a d} 

팝 c 방문 노드 세트에 추가, 거기 방문 - 010110 (b, d, e()하지만 우리는) ​​d를 방문 : 방문 노드 세트에 추가하고, 거기에 방문

[e b b b]    {a d c} 

팝업 e -)) 001001 (c, f (하지만 우리는 c를 방문한 :

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

: 000010 ( e)을 (하지만 우리가 방문) -

팝 f는 방문 노드 세트에 추가, 거기 방문 ,

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

우리는 B를 방문한 : 101100 (a, c, d)을 (하지만 우리는 모든를 방문) - 533,210

팝 b는 방문 노드 세트에 추가, 거기 방문 그래서 두 번 버리고 버려.

[]      {a d c e f b} 

ps ps는 DFS이므로 스택이 아니며 대기열이 아닙니다 (두 질문에 모두 언급 됨). BFS 것이 유사하다 그러나 당신은 대기열에 추가, 그래서 처음 몇 단계는 다음과 같습니다 b 및 c는 "왼쪽"(그러나 우리는 여전히 걸릴 대신 "오른쪽"에 추가됩니다

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

왼쪽부터, 그래서 우리는 너비가 넓고 다음 노드는 b이 될 것입니다.

Answer 2

andrew cooke의 멋진 대답에 대한 추가 정보로 파이썬 라이브러리 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()