Python Implementation
BFS traverse:
|
1 2 3 4 5 |
Root='a' g.nodes[Root]['visited']=True print Root Q=[Root] BFS_travrse(Q,g) |
DFS traverse:
|
1 2 3 4 5 |
Root='a' print Root g.nodes[Root]['visited']=True coloring_tree(g) DFS_travrse(Root,g) |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
import networkx as nx import matplotlib.pyplot as plt from networkx.drawing.nx_agraph import write_dot, graphviz_layout def coloring_tree(G): visited_list=[] for i in G.nodes(): visited_list.append( g.nodes[i]['visited'] ) graph_color_map=[] for i in visited_list: if i: color='blue' else: color='red' graph_color_map.append(color) pos =graphviz_layout(G, prog='dot') nx.draw(G, pos, with_labels=True, arrows=True,node_color = graph_color_map) #plt.savefig('nx_test.png') plt.show() return def DFS_travrse(N,G): neighbors =G.neighbors(N) size=len( list(neighbors)) if size==0: return neighbors =G.neighbors(N) for neighbor in neighbors: G.nodes[neighbor]['visited']=True coloring_tree(G) DFS_travrse(neighbor,G) return def BFS_travrse(Q,G): if len(Q)==0: return Root=Q[0] Q=Q[1:len(Q)] neighbors =G.neighbors(Root) for neighbor in neighbors: print neighbor coloring_tree(G) G.nodes[neighbor]['visited']=True Q.append(neighbor) BFS_travrse(Q,G) return g=nx.DiGraph() g.add_node('a',visited=False) g.add_node('b',visited=False) g.add_node('c',visited=False) g.add_node('d',visited=False) g.add_node('e',visited=False) g.add_node('f',visited=False) g.add_node('g',visited=False) g.add_node('h',visited=False) g.add_edge('a','b') g.add_edge('a','c') g.add_edge('b','e') g.add_edge('b','d') g.add_edge('e','h') g.add_edge('c','f') g.add_edge('c','g') |
C++ Implementation
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#include <algorithm> #include <iostream> #include <memory> class node { public: std::vector<std::shared_ptr<node> > leaves; double data; }; void populateTree(std::shared_ptr<node> rootNodePtr) { /* -1 / \ 3 7 / \ / 4 1 5 */ rootNodePtr->data=-1; std::shared_ptr<node> leftNodePtr,rightNodePtr; std::shared_ptr<node> leftNode1stKidPtr,leftNode2ndtKidPtr, rightNode1stKidPtr; leftNodePtr.reset(new node) ; rightNodePtr.reset(new node); rootNodePtr->leaves.push_back(leftNodePtr); rootNodePtr->leaves.push_back(rightNodePtr); leftNodePtr->data=3; rightNodePtr->data=7; leftNode1stKidPtr.reset(new node); leftNode2ndtKidPtr.reset(new node); rightNode1stKidPtr.reset(new node); leftNode1stKidPtr->data=4; leftNode2ndtKidPtr->data=1; rightNode1stKidPtr->data=5; leftNodePtr->leaves.push_back(leftNode1stKidPtr); leftNodePtr->leaves.push_back(leftNode2ndtKidPtr); rightNodePtr->leaves.push_back(rightNode1stKidPtr); } void DFS(std::shared_ptr<node> rootNode) { std::cout<<rootNode->data <<std::endl; for(auto n:rootNode->leaves) DFS(n); } void BFS(std::shared_ptr<node> rootNode) { for(auto n:rootNode->leaves) std::cout<<n->data <<std::endl; for(auto n:rootNode->leaves) BFS(n); } int main() { std::shared_ptr<node> tree(new node); populateTree(tree); DFS(tree); BFS(tree); } |
