圖形(Graph)

Da-Wei Chiang

大綱

• 圖形基本概念
  • 圖形應用
  • 加權圖形
• 有向與無向圖形
  • 有向圖形應用
• 廣度優先搜尋法
• 深度優先搜尋法

圖形基本概念

圖形應用 - 1

圖形應用 - 2

• 台北捷運部分地圖

加權圖形

• 加權的數字意義可以自行定義. 如圖中的數字可以表示兩個人關係的距離或住家的距離...等等

有向與無向圖形

• 上述圖形中節點與節點之間沒有方向性我們稱為無向圖形.
• 有向圖形如下圖所示

有向圖形應用

廣度優先搜尋法(Breadth First Search)

• 電腦圖形理論的搜尋演算法
• 概念：一層一層的搜尋, 當搜尋第一層沒有答案在搜尋第二層, 第二層搜尋沒有答案在搜尋第三層...依此類推

圖例 - 廣度優先搜尋法(Breadth First Search)

• 假設有個圖形如下, 試圖搜尋Ｇ節點

圖例 - 廣度優先搜尋法(Breadth First Search)

• 首先我們宣告一個佇列, 放入預備搜尋的節點. 並從頂點Ａ開始搜尋

圖例 - 廣度優先搜尋法(Breadth First Search)

• 發現Ａ不是目標節點, 並將Ａ加入已搜尋過串列. 並將Ａ的子節點Ｂ、Ｃ加入預搜尋佇列中

圖例 - 廣度優先搜尋法(Breadth First Search)

• 接著搜尋Ｂ. 發現Ｂ不是目標節點, 並將Ｂ加入已搜尋過串列.且將Ｂ的子節點Ｄ、Ｅ、Ｆ加入預搜尋佇列中

圖例 - 廣度優先搜尋法(Breadth First Search)

• 接著搜尋Ｃ. 發現Ｃ不是目標節點, 並將Ｃ加入已搜尋過串列.且將Ｃ的子節點Ｇ、Ｈ加入預搜尋佇列中

圖例 - 廣度優先搜尋法(Breadth First Search)

• 接著搜尋Ｄ. 發現Ｄ不是目標節點, 並將Ｄ加入已搜尋過串列.因為Ｄ為葉節點, 沒有其它子節點故無節點加入預搜尋佇列.

圖例 - 廣度優先搜尋法(Breadth First Search)

• 接著搜尋Ｅ. 發現Ｅ不是目標節點, 並將Ｅ加入已搜尋過串列.且將Ｅ的子節點Ｉ加入預搜尋佇列中

圖例 - 廣度優先搜尋法(Breadth First Search)

• 接著搜尋Ｆ. 發現Ｆ不是目標節點, 並將Ｆ加入已搜尋過串列.且將Ｆ的子節點Ｊ加入預搜尋佇列中

圖例 - 廣度優先搜尋法(Breadth First Search)

• 接著搜尋Ｇ. 發現Ｇ是目標節點.完成搜尋

實作上我們怎麼描繪一個圖形？可用字典或鏈結串列表示.

• 如上述圖示範例字典可表示為

  {
    A:[B, C],
    B:[D, E, F],
    C:[G, H],
    D:[],
    E:[I],
    F:[J],
    G:[],
    H:[K],
    I:[],
    J:[],
    K:[]
  }
  

練習

• 使用上述字典範例作為圖形, 讓使用者輸入要搜尋的節點.
• 撰寫廣度搜尋法搜尋此節點, 並輸出搜尋到節點時所搜尋過的所有節點.

深度優先搜尋法(Depth First Search)

• 電腦圖形理論的搜尋演算法
• 概念：先深入一個路徑搜尋, 當深入這個路徑的末端都沒搜尋到時. 則回到前一層找尋可搜尋的路徑深入搜尋...依此類推.

圖例 - 深度優先搜尋法(Depth First Search)

• 假設有個圖形如下, 試圖搜尋Ｇ節點

圖例 - 深度優先搜尋法(Depth First Search)

• 首先我們宣告一個堆疊, 放入預備搜尋的節點. 並從頂點Ａ開始搜尋

圖例 - 深度優先搜尋法(Depth First Search)

• 從堆疊中取出Ａ放入已搜尋的串列, 並檢查Ａ是否為目標節點. 由於Ａ不是目標節點, 故將其子節點Ｂ、Ｃ存入堆疊中.

圖例 - 深度優先搜尋法(Depth First Search)

• 從堆疊中取出Ｂ放入已搜尋的串列, 並檢查Ｂ是否為目標節點. 由於Ｂ不是目標節點, 故將其子節點Ｄ、Ｅ、Ｆ存入堆疊中.

圖例 - 深度優先搜尋法(Depth First Search)

• 從堆疊中取出Ｄ放入已搜尋的串列, 並檢查Ｄ是否為目標節點. 由於Ｄ不是目標節點, 且其為葉節點.故無其他節點存入堆疊中.

圖例 - 深度優先搜尋法(Depth First Search)

• 從堆疊中取出Ｅ放入已搜尋的串列, 並檢查Ｅ是否為目標節點. 由於Ｅ不是目標節點, 故將其子節點Ｉ存入堆疊中.

圖例 - 深度優先搜尋法(Depth First Search)

• 從堆疊中取出Ｉ放入已搜尋的串列, 並檢查Ｉ是否為目標節點. 由於Ｉ不是目標節點, 且其為葉節點.故無其他節點存入堆疊中.

圖例 - 深度優先搜尋法(Depth First Search)

• 從堆疊中取出Ｆ放入已搜尋的串列, 並檢查Ｆ是否為目標節點. 由於Ｆ不是目標節點, 故將其子節點Ｊ存入堆疊中.

圖例 - 深度優先搜尋法(Depth First Search)

• 從堆疊中取出Ｊ放入已搜尋的串列, 並檢查Ｊ是否為目標節點. 由於Ｊ不是目標節點, 且其為葉節點.故無其他節點存入堆疊中.

圖例 - 深度優先搜尋法(Depth First Search)

• 從堆疊中取出Ｃ放入已搜尋的串列, 並檢查Ｃ是否為目標節點. 由於Ｃ不是目標節點, 故將其子節點Ｇ、Ｈ存入堆疊中.

圖例 - 深度優先搜尋法(Depth First Search)

• 從堆疊中取出Ｇ放入已搜尋的串列, 並檢查Ｇ是否為目標節點. 由於Ｇ為目標節點.故完成搜尋

練習

• 使用上述字典範例作為圖形, 讓使用者輸入要搜尋的節點.
• 撰寫深度搜尋法搜尋此節點, 並輸出搜尋到節點時所搜尋過的所有節點.