1. 二叉树图

2. 宽度/广度优先搜索算法(Breadth First Search，BSF)

工作原理:

• 从图中某顶点v出发，首先访问定点v
• 在访问了v之后依次访问v的各个未曾访问过的邻接点；
• 然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问;
• 直至图中所有已被访问的顶点的邻接点都被访问到;
• 如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。

换句话说，广度优先搜索遍历图的过程是以v为起点，由近至远，依次访问和v有路径相通且路 径长度为1,2…的顶点。

如上图的BFS访问顺序为：A->B->C->D->E->F

3. 深度优先搜索算法

工作原理:

• 从顶点v出发，首先访问该顶点;
• 然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图;
• 直至图中所有和v有路径相通的顶点都被访问到。
• 若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止

如上图的BFS访问顺序为：A->B->D->E->C->F

4. 宽度/广度优先搜索算法实现

# 宽度优先算法的实现
def BFS(self, root):
	#首先判断根节点是否为空节点
	if root != None:
		search_queue = deque()
		search_queue.append(root)
		visited = []
	else:
		print('root is None')
		return -1
	while search_queue:
		person = search_queue.popleft()
		self.order.append(person)
		if (not person in visited) and (person in self.neighbor.keys()):
			search_queue += self.neighbor[person]
			visited.append(person)
			

5. 深度优先搜索算法实现

# 深度优先算法的实现
def DFS(self, root):
	# 首先判断根节点是否为空节点
	if root != None:
		search_queue = deque()
		search_queue.append(root)
		visited = []
	else:
		print('root is None')
		return -1
	while search_queue:
		person = search_queue.popleft()
		self.order.append(person)
	if (not person in visited) and (person in self.neighbor.keys()):
		tmp = self.neighbor[person]
		tmp.reverse()
		for index in tmp:
			search_queue.appendleft(index)
			visited.append(person)
			

6. 完整代码实现

# -*- coding: utf-8 -*-
from collections import deque    # 线性表的模块
 
# 首先定义一个创建图的类，使用邻接矩阵
class Graph(object):
    def __init__(self, *args, **kwargs):
        self.order = []  # visited order
        self.neighbor = {}
 
    def add_node(self, node):
        key, val = node
        if not isinstance(val, list):
            print('节点输入时应该为一个线性表')    # 避免不正确的输入
        self.neighbor[key] = val
 
    # 宽度优先算法的实现
    def BFS(self, root):
        #首先判断根节点是否为空节点
        if root != None:
            search_queue = deque()
            search_queue.append(root)
            visited = []
        else:
            print('root is None')
            return -1
 
        while search_queue:
            person = search_queue.popleft()
            self.order.append(person)
 
            if (not person in visited) and (person in self.neighbor.keys()):
                search_queue += self.neighbor[person]
                visited.append(person)
 
    # 深度优先算法的实现
    def DFS(self, root):
        # 首先判断根节点是否为空节点
        if root != None:
            search_queue = deque()
            search_queue.append(root)
 
            visited = []
        else:
            print('root is None')
            return -1
 
        while search_queue:
            person = search_queue.popleft()
            self.order.append(person)
 
            if (not person in visited) and (person in self.neighbor.keys()):
                tmp = self.neighbor[person]
                tmp.reverse()
 
                for index in tmp:
                    search_queue.appendleft(index)
 
                visited.append(person)
 
    def clear(self):
        self.order = []
 
    def node_print(self):
        for index in self.order:
            print(index, end=' ')
 
 
if __name__ == '__main__':
    # 创建一个二叉树图
    g = Graph()
    g.add_node(('A', ['B', 'C']))
    g.add_node(('B', ['D', 'E']))
    g.add_node(('C', ['F']))
 
    # 进行宽度优先搜索
    g.BFS('A')
    print('宽度优先搜索:')
    print('  ', end='  ')
    g.node_print()  # A B C D E F
    g.clear()
 
    # 进行深度优先搜索
    print('\n\n深度优先搜索:')
    print('  ', end='  ')
    g.DFS('A')
    g.node_print()  # A B D E C F
    print()

# 首先定义一个创建图的类，使用邻接矩阵
class Graph(object):
    def __init__(self, *args, **kwargs):
        self.order = []  # visited order
        self.neighbor = {}

    def add_node(self, node):
        key, val = node
        if not isinstance(val, list):
            print('节点输入时应该为一个线性表')    # 避免不正确的输入
        self.neighbor[key] = val

 

# 宽度优先算法的实现
def BFS(self, root):
    #首先判断根节点是否为空节点
    if root != None:
        search_queue = deque()
        search_queue.append(root)
        visited = []
    else:
        print('root is None')
        return -1

    while search_queue:
        person = search_queue.popleft()
        self.order.append(person)

        if (not person in visited) and (person in self.neighbor.keys()):
            search_queue += self.neighbor[person]
            visited.append(person)

 

# 深度优先算法的实现
def DFS(self, root):
    # 首先判断根节点是否为空节点
    if root != None:
        search_queue = deque()
        search_queue.append(root)

        visited = []
    else:
        print('root is None')
        return -1

    while search_queue:
        person = search_queue.popleft()
        self.order.append(person)

        if (not person in visited) and (person in self.neighbor.keys()):
            tmp = self.neighbor[person]
            tmp.reverse()

            for index in tmp:
                search_queue.appendleft(index)

            visited.append(person)

 

附录：

完整的代码：

# -*- coding: utf-8 -*-
# /usr/bin/python
# 作者：郭畅
# 实验日期：20180612
# Python版本：3.6.4
# 主题：基于深度优先和宽度优先的搜索算法的简单实现
# 参考书籍：数据结构C语言版（清华大学出版社严蔚敏版）

from collections import deque    # 线性表的模块

# 首先定义一个创建图的类，使用邻接矩阵
class Graph(object):
    def __init__(self, *args, **kwargs):
        self.order = []  # visited order
        self.neighbor = {}

    def add_node(self, node):
        key, val = node
        if not isinstance(val, list):
            print('节点输入时应该为一个线性表')    # 避免不正确的输入
        self.neighbor[key] = val

    # 宽度优先算法的实现
    def BFS(self, root):
        #首先判断根节点是否为空节点
        if root != None:
            search_queue = deque()
            search_queue.append(root)
            visited = []
        else:
            print('root is None')
            return -1

        while search_queue:
            person = search_queue.popleft()
            self.order.append(person)

            if (not person in visited) and (person in self.neighbor.keys()):
                search_queue += self.neighbor[person]
                visited.append(person)

    # 深度优先算法的实现
    def DFS(self, root):
        # 首先判断根节点是否为空节点
        if root != None:
            search_queue = deque()
            search_queue.append(root)

            visited = []
        else:
            print('root is None')
            return -1

        while search_queue:
            person = search_queue.popleft()
            self.order.append(person)

            if (not person in visited) and (person in self.neighbor.keys()):
                tmp = self.neighbor[person]
                tmp.reverse()

                for index in tmp:
                    search_queue.appendleft(index)

                visited.append(person)

    def clear(self):
        self.order = []

    def node_print(self):
        for index in self.order:
            print(index, end='  ')


if __name__ == '__main__':
    # 创建一个二叉树图
    g = Graph()
    g.add_node(('A', ['B', 'C']))
    g.add_node(('B', ['D', 'E']))
    g.add_node(('C', ['F']))

    # 进行宽度优先搜索
    g.BFS('A')
    print('宽度优先搜索:')
    print('  ', end='  ')
    g.node_print()
    g.clear()

    # 进行深度优先搜索
    print('\n\n深度优先搜索:')
    print('  ', end='  ')
    g.DFS('A')
    g.node_print()
    print()

'''
by Jun
'''
import copy
import numpy as np
from datetime import datetime


# 字符串列表化
def string_to_ls(str):
    return [i.split(' ') for i in str.split(',')]


# 获取位置
def get_loacl(arr, target):
    # r, c = np.where(arr == target)
    # return r, c
    for i in arr:
        for j in i:
            if j == target:
                return arr.index(i), i.index(j)


# 获取可以和0交换位置的元素
def get_elements(arr):
    r, c = get_loacl(arr, '0')
    elements = []
    if r > 0:
        elements.append(arr[r - 1][c])  # 上面的元素
    if r < 2:
        elements.append(arr[r + 1][c])  # 下边的元素
    if c > 0:
        elements.append(arr[r][c - 1])  # 左面的元素
    if c < 2:
        elements.append(arr[r][c + 1])  # 右面的元素
    return elements


def get_child(arr, e):
    # 深拷贝与浅拷贝！!
    arr_new = copy.deepcopy(arr)
    r, c = get_loacl(arr_new, '0')
    r1, c1 = get_loacl(arr_new, e)
    arr_new[r][c], arr_new[r1][c1] = arr_new[r1][c1], arr_new[r][c]
    return arr_new


def is_goal(arr, goal):
    return arr == goal


class state:
    def __init__(self, state, parent):
        # state是一个3x3的ls矩阵
        self.state = state
        self.parent = parent

    def chidren(self):
        chidren = []
        for i in get_elements(self.state):
            child = state(state=get_child(self.state, i), parent=self)
            chidren.append(child)
        return chidren


# 打印求解路径
def print_path(n):
    if n.parent == None:
        return
    else:
        print('↑')
        print(np.array(n.parent.state))
        print_path(n.parent)


if __name__ == '__main__':
    initial = '0 1 3,4 2 5,7 8 6'
    goal = '4 1 3,7 0 5,8 2 6'
    # initial = '0 7 8,2 5 4,3 6 1'
    # goal = '7 5 8,2 4 1,3 6 0'
    # initial = '4 0 1,6 8 5,7 3 2'
    # goal = '5 8 2,1 0 4,6 3 7'
    initial_arr = state(string_to_ls(initial), parent=None)
    goal_arr = string_to_ls(goal)
    start = datetime.now()
    open = [initial_arr]
    close = []
    while len(open) > 0:
        open_tb = [i.state for i in open]
        close_tb = [i.state for i in close]
        n = open.pop(0)
        close.append(n)
        if is_goal(n.state, goal_arr):
            print(np.array(n.state))
            print_path(n)
            print('最优求解过程如上')
            break
        else:
            for i in n.chidren():
                if i.state not in open_tb:
                    if i.state not in close_tb:
                        open.append(i)
    end = datetime.now()
    print('--' * 20)
    print('--' * 20)
    print('--' * 20)
    print('搜索路径如下：')
    for i in close[:-1]:
        print(np.array(i.state))
        print('↓')
    print(np.array(close[-1].state))
    print('共耗时:', end - start)
    print('搜索步骤为{}'.format(len(close) - 1))