Chinaunix首页 | 论坛 | 博客
  • 博客访问: 6586687
  • 博文数量: 227
  • 博客积分: 10047
  • 博客等级: 上将
  • 技术积分: 6678
  • 用 户 组: 普通用户
  • 注册时间: 2006-07-11 10:33
个人简介

网上的蜘蛛

文章分类

全部博文(227)

文章存档

2010年(19)

2009年(29)

2008年(179)

分类: Java

2008-10-27 13:24:09

depth-first search 是以某一節點為出發點,不斷地前進拜訪未曾被拜訪過的節點, 直到無路可走或是所有相鄰的節點都已經拜訪過為止,然後再退回前一個節點,尋找 沒有拜訪過的節點,直到所有相鄰的節點都已被拜訪過。 因此,進行 depth-first search 時,需要使用 stack ,以便記錄所走過的路徑。


  1. 起始。


  2. 假設從 a 開始拜訪,我們將 a 放進stack。

    STACK
    stack topa

    a 有三個節點可以拜訪 (b, c, d)。

  3. 假設我們選擇拜訪 b ,我們將 b 放進stack。

    STACK
    stack topb

    a

    b 有三個節點可以拜訪 (c, e, f)。

  4. 假設我們選擇拜訪 c ,我們將 c 放進stack。

    STACK
    stack topc

    b

    a

    c 只能拜訪 f。

  5. 我們選擇拜訪 f ,我們將 f 放進stack。

    STACK
    stack topf

    c

    b

    a

    由於 f 沒有節點可以拜訪,我們把 f 從stack取出。
    STACK
    stack topc

    b

    a

    由於 c 也沒有節點可以拜訪,我們也把 c 從stack取出。
    STACK
    stack topb

    a

    b 可以拜訪 e。

  6. 我們選擇拜訪 e ,我們將 e 放進stack。

    STACK
    stack tope

    b

    a

    由於 e 沒有節點可以拜訪,我們把 e 從stack取出。
    STACK
    stack topb

    a

    由於 b 也沒有節點可以拜訪,我們也把 b 從stack取出。
    STACK
    stack topa

    a 可以拜訪 d。

  7. 我們選擇拜訪 d ,我們將 d 放進stack。

    STACK
    stack topd

    a

    d 只能拜訪 g。

  8. 我們選擇拜訪 g ,我們將 g 放進stack。

    STACK
    stack topg

    d

    a

    由於 g 沒有節點可以拜訪,我們把 g 從stack取出。
    STACK
    stack topd

    a

    由於 d 也沒有節點可以拜訪,我們也把 d 從stack取出。
    STACK
    stack topa

    由於 a 也沒有節點可以拜訪,我們也把 a 從stack取出。
    此時 stack 已經全部清空,depth-first search完成。
阅读(2440) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~