图的深度优先搜索

图有两种最基本的搜索算法,一种是深度优先搜索,另一种是广度优先搜索。本节先介绍深度优先搜索。

一、基本思想

深度优先遍历图的方法是,从图中某顶点v出发: 1 访问顶点v; 2 依次从v的未被访问的邻接点出发,对图进行深度优先遍历;直至图中和v有路径相通的顶点都被访问; 3 若此时图中尚有顶点未被访问,则从一个未被访问的顶点出发,重新进行深度优先遍历,直到图中所有顶点均被访问过为止。

二、例子

有一个图如下,求深度优先搜索顺序。

分析:首先看看每个元素和哪些元素相邻

元素

相邻元素

1

2,3

2

1,4,5

3

1,6,7

4

2,8

5

2,8

6

3,7

7

3,6

8

4,5

(1)假设从节点1开始遍历(事实上可以从任何一个节点开始),与1相邻的是2和3 (2)遍历2之后,进入递归。2有三个相邻元素,1,4,5。因为1已经遍历过了,因此遍历4 (3)遍历4之后,进入递归。与4相邻的是2和8,因为2已经遍历过了,所以遍历8 (4)遍历8之后,进入递归。与8相邻的是4和5,因为4已经遍历过了,所以遍历5 (5)遍历5之后,进入递归。与5相邻的是2和8,因为2和8都已经遍历过了,所以递归终止。返回步骤(4) (6)因为步骤(4)中的4和5都已经遍历过了,返回步骤(3) (7)因为步骤(3)中的2和8都已经遍历过了,返回步骤(2) (8)因为步骤(2)中的1,4,5都已经遍历过了,返回步骤(1) (9)因为步骤(1)中的2已经遍历过了,这次遍历的是3 (10)遍历3之后,进入递归。与3相邻的是6和7,所以遍历6 (11)遍历6之后,进入递归。与6相邻的是3和7,因为3已经遍历过了,所以遍历7 (12)遍历7之后,进入递归。与7相邻的是3和6,因为3和6都已经遍历过了,递归结束。返回步骤(11) (13)在(11)中,3和7都遍历过了,返回步骤(10) (14)在(10)中,6和7都遍历过,返回步骤(1) (15)在步骤(1)中,没有未遍历过的元素。遍历结束。 由上面的15个步骤可知,深度搜索遍历的顺序为:1,2,4,8,5,3,6,7。

三、Python 3代码实现:

class Graph(object):
    def __init__(self):
        self.node_neighbors = {}
        self.visited = {}
    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 != v):
            self.node_neighbors[u].append(v)
            self.node_neighbors[v].append(u)
    def nodes(self):
        return self.node_neighbors.keys()
    def depth_first_search(self,root=None):
        order = []
        def dfs(node):
            self.visited[node] = True
            order.append(node)
            for n in self.node_neighbors[node]:
                if not n in self.visited:
                    dfs(n)
        if root in self.nodes():
            dfs(root)
        for node in self.nodes():
            if not node in self.visited:
                dfs(node)
        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 ("Original nodes: ", g.nodes())
order = g.depth_first_search(1)
print ("Depth-First-Search order: ", order)

运行结果:

Original nodes:  dict_keys([1, 2, 3, 4, 5, 6, 7, 8])
Depth-First-Search order: [1, 2, 4, 8, 5, 3, 6, 7]

原文发布于微信公众号 - 海天一树(gh_de7b45c40e8b)

原文发表时间:2018-04-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏尾尾部落

[剑指offer] 链表中倒数第k个结点 [剑指offer] 链表中倒数第k个结点

经典的双指针法。定义两个指针,第一个指针从链表的头指针开始遍历向前走k-1步,第二个指针保持不动,从第k步开始,第二个指针也开始从链表的头指针开始遍历,由于两个...

10620
来自专栏desperate633

Python爬虫之正则表达式入门正则表达式语法正则表达式实例ReMatch对象贪婪匹配和最小匹配

Re库是Python的标准库,主要用于字符串匹配 调用方式: import re

8710
来自专栏PHP在线

PHP面试题,PHP笔试题

题目一: <?php echo -10%3; ?> 答案:-1。 考查:优先级。 因为-的优先级比%求余的优先级低, 也就是-(10%3)。 题目二: prin...

1K150
来自专栏老司机的技术博客

人人都能学会的python编程教程6:列表(list)

当索引超出了范围时,Python会报一个IndexError错误,所以,要确保索引不要越界,记得最后一个元素的索引是len(classmates) - 1。如果...

434100
来自专栏小詹同学

Leetcode打卡 | No.20 有效的括号

给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。

11120
来自专栏大闲人柴毛毛

剑指offer——面试题10输入一个十进制整数,统计其中二进制1的个数

/** * 题目:输入一个十进制整数,统计其中二进制1的个数 * @author 大闲人柴毛毛 */ public class CountBitOne {...

39040
来自专栏Java爬坑系列

【JAVA零基础入门系列】Day10 Java中的数组

  什么是数组?顾名思义,就是数据的组合,把一些相同类型的数放到一组里去。   那为什么要用数组呢?比如需要统计全班同学的成绩的时候,如果给班上50个同学的成绩...

22760
来自专栏从零开始学 Web 前端

05 - JavaSE之数组

17040
来自专栏瓜大三哥

Matlab基本运算3

字符串指的是1xn的字符数组。单个字符是按照unicode编码存储的,每个字符占两个字节 ? 在matlab中,只要用(‘)将需要设定的字符串括起来。 disp...

22060
来自专栏智能算法

Python学习(四)---- 列表生成式、生成器、迭代器和内置函数

https://blog.csdn.net/fgf00/article/details/52061971

11620

扫码关注云+社区

领取腾讯云代金券