<Day8- 圖 graph>

• G = (V,E) V:一組頂點, E: 一組邊,連接V中的頂點
• 分類
  • 有向vs無向
  • 加權vs未加權
• 圖形的表示：
  • 相鄰矩陣 用一個二維陣列表示頂點知街的連結 相鄰1 不相鄰0
    • 缺點
      • 彼此關係叫疏鬆的圖 會浪費很多電腦的儲存空間
      • 途中頂點的數量可能改變
  • 相鄰串列 每個點的相鄰頂點是串列所組成 可以用陣列,鏈結串列,字典或雜湊表表示
  • 關聯矩陣 常用於 邊的數量比頂點多的情況
• 圖形的遍歷 尋找特定頂點或尋找兩個頂點之間的路徑, 檢查是否連同, 是否有還
  • BFS 廣度優先搜尋- 佇列 最先入得頂點就先被探索
  • DFS 深度優先搜尋- 堆疊 存在新的相鄰頂點就去訪問

//尚未完成 期末考後補齊


function Graph(){

  let vertices = []
  let adjList = new Dictionary()

  this.addVertex = function(v){
    vertices.push(v)
    adjList.set(v, [])
  }
  this.addEdge = function(v, w){
    adjList.set(v).push(w)
    adjList.set(w).push(v)
  }
  //BFS

  let initializeColor = function(){
    let color = []
    for (var i = 0; i < vertices.length; i++) {
      color[vertices[i]] = 'white'
    }
    return color
  }
}

參考資料：