深度优先搜索和广度优先搜索

#!/usr/bin/python
# -*- coding: utf-8 -*-

class Graph(object):

    def __init__(self,*args,**kwargs):
        self.node_neighbors = {}

    def add_nodes(self,nodelist):
        for node in nodelist:
            self.add_node(node)

    def add_node(self,node):
        if not node in self.nodes():
            self.node_neighbors[node] = []

    def add_edge(self,edge):
        u,v = edge
        if(v not in self.node_neighbors[u]) and ( u not in self.node_neighbors[v]):
            self.node_neighbors[u].append(v)

            if(u!=v):
                self.node_neighbors[v].append(u)

    def nodes(self):
        return self.node_neighbors.keys()

    """深度优先搜索非递归实现"""
    def depth_first_search_Non_Recursive(self,root=None):
        if root == None:
            return []
        order = [root]
        visited = {}
        queue = [root]
        while len(queue) > 0:
            node = queue[-1]
            visited[node] = True
            for n in self.node_neighbors[node]:
                if not n in visited:
                    queue.append(n)
                    order.append(n)
                    break
            if queue[-1] == node:
                queue.pop()
        print order
        return order

    def depth_first_search(self,root=None):
        order = []
        visited = {}
        def dfs(node):
            visited[node] = True
            order.append(node)
            for n in self.node_neighbors[node]:
                if not n in visited:
                    dfs(n)


        if root:
            dfs(root)

        for node in self.nodes():
            if not node in visited:
                dfs(node)

        print order
        return order

    def breadth_first_search(self,root=None):
        queue = []
        order = []
        visited = {}
        def bfs():
            while len(queue)> 0:
                node  = queue.pop(0)

                visited[node] = True
                for n in self.node_neighbors[node]:
                    if (not n in visited) and (not n in queue):
                        queue.append(n)
                        order.append(n)

        if root:
            queue.append(root)
            order.append(root)
            bfs()

        for node in self.nodes():
            if not node in visited:
                queue.append(node)
                order.append(node)
                bfs()
        print order

        return order


if __name__ == '__main__':
    g = Graph()
    g.add_nodes([i+1 for i in range(8)])
    g.add_edge((1, 2))
    g.add_edge((1, 3))
    g.add_edge((2, 4))
    g.add_edge((2, 5))
    g.add_edge((4, 8))
    g.add_edge((5, 8))
    g.add_edge((3, 6))
    g.add_edge((3, 7))
    g.add_edge((6, 7))
    print "nodes:", g.nodes()

    order = g.breadth_first_search(1)
    order = g.depth_first_search(1)
    order = g.depth_first_search_Non_Recursive(1)

树的深度优先遍历非递归和递归实现方法 

//深度优先遍历:非递归,使用栈模拟
void depthFirstSearch(Tree root){
    stack<Node *> nodeStack;  //使用C++的STL标准模板库
    nodeStack.push(root);
    Node *node;
    while(!nodeStack.empty()){
        node = nodeStack.top();
        printf(format, node->data);  //遍历根结点
        nodeStack.pop();
        if(node->rchild){
            nodeStack.push(node->rchild);  //先将右子树压栈
        }
        if(node->lchild){
            nodeStack.push(node->lchild);  //再将左子树压栈
        }
    }
}

//深度优先遍历:递归,中序遍历
void MidOrder(TreeNode node)         
{            
    if (node != null)            
    {                
        MidOrder(node->lchild);                
        printf(format, node->data);  //遍历根结点             
        MidOrder(node->lchild);            
    }            
    else            
    {                
        //done            
    }        
}