DFS and the stack
I study CS algorithms in my spare time and get along well, but I'm having trouble understanding adjacency matrix and DFS.
010100 101100 010110 111000 001001 000010
If the above is an undirected graph, with 6 vertices (a, f) (the first line is vertex a, etc.) If the graph goes through DFS and stack starting from vertex a.
What will be the contents of the queue after each addition or removal of vertices from it? I am assuming that if 2 is inserted at this time, it will be in alphabetical order.
Can someone explain how to do this?
source to share
you are in a
, so your line 010100
, and your neighbors - b
, d
. so push them onto the stack (and you visited a
):
[d b] {a}
pop d
, add it to the set of visited sites and visit there - 111000
( a
, b
, c
) (but you've visited a
)
[c b b] {a d}
pop c
, add it to the set of visited sites and visit there - 010110
( b
, d
, e
) (but we visited d
)
[e b b b] {a d c}
pop e
, add it to the visited nodes set and visit there - 001001
( c
, f
) (but we visited c
):
[f b b b] {a d c e}
pop f
, add it to the visited nodes set and visit there - 000010
( e
) (but we got there):
[b b b] {a d c e f}
pop b
, add it to the set of visited sites and visit there - 101100
( a
, c
, d
) (but we visited all of these):
[b b] {a d c e f b}
and we visited b so pop and discard twice.
[] {a d c e f b}
ps this is DFS and so this is a stack, not a queue (you mention both in the question). for BFS it would be similar, but you add to the queue, so the first few steps are:
[d b] {a}
[b b c] {a d}
where b
u c
are added "to the right" and not to the "left" (but we still take them from the left, so we examine the width and the next node will be b
).
source to share
As an addition to andrew cooke's hello, you can use the python library networkx
to actually render DFS lookups! By default, DFS starts at node 0, but this can be changed. You can change the graph first to visualize more complex systems.
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()
source to share