[[426520]]

本文轉(zhuǎn)載自微信公眾號(hào)「JS每日一題」，作者灰灰 。轉(zhuǎn)載本文請(qǐng)聯(lián)系JS每日一題公眾號(hào)。

一、是什么

在計(jì)算機(jī)科學(xué)中，圖是一種抽象的數(shù)據(jù)類型，在圖中的數(shù)據(jù)元素通常稱為結(jié)點(diǎn)，V是所有頂點(diǎn)的集合，E是所有邊的集合

如果兩個(gè)頂點(diǎn)v,w，只能由v向w，而不能由w向v，那么我們就把這種情況叫做一個(gè)從 v 到 w 的有向邊。v也被稱做初始點(diǎn)，w也被稱為終點(diǎn)。這種圖就被稱做有向圖

如果v和w是沒有順序的，從v到達(dá)w和從w到達(dá)v是完全相同的，這種圖就被稱為無向圖

圖的結(jié)構(gòu)比較復(fù)雜，任意兩個(gè)頂點(diǎn)之間都可能存在聯(lián)系，因此無法以數(shù)據(jù)元素在存儲(chǔ)區(qū)中的物理位置來表示元素之間的關(guān)系

常見表達(dá)圖的方式有如下：

• 鄰接矩陣
• 鄰接表

鄰接矩陣

通過使用一個(gè)二維數(shù)組G[N][N]進(jìn)行表示N個(gè)點(diǎn)到N-1編號(hào)，通過鄰接矩陣可以立刻看出兩頂點(diǎn)之間是否存在一條邊，只需要檢查鄰接矩陣行i和列j是否是非零值，對(duì)于無向圖，鄰接矩陣是對(duì)稱的

鄰接表

存儲(chǔ)方式如下圖所示：

在javascript中，可以使用Object進(jìn)行表示，如下：

const graph = { 
  A: [2, 3, 5], 
  B: [2], 
  C: [0, 1, 3], 
  D: [0, 2], 
  E: [6], 
  F: [0, 6], 
  G: [4, 5] 
} 

圖的數(shù)據(jù)結(jié)構(gòu)還可能包含和每條邊相關(guān)聯(lián)的數(shù)值(edge value)，例如一個(gè)標(biāo)號(hào)或一個(gè)數(shù)值(即權(quán)重，weight;表示花費(fèi)、容量、長度等)

二、操作

關(guān)于圖的操作常見的有：

• 深度優(yōu)先遍歷
• 廣度優(yōu)先遍歷

首先構(gòu)建一個(gè)圖的鄰接矩陣表示，如下面的圖：

用代碼表示則如下：

const graph = { 
  0: [1, 4], 
  1: [2, 4], 
  2: [2, 3], 
  3: [], 
  4: [3], 
} 

深度優(yōu)先遍歷

也就是盡可能的往深處的搜索圖的分支

實(shí)現(xiàn)思路是，首先應(yīng)該確定一個(gè)根節(jié)點(diǎn)，然后對(duì)根節(jié)點(diǎn)的沒訪問過的相鄰節(jié)點(diǎn)進(jìn)行深度優(yōu)先遍歷

確定以 0 為根節(jié)點(diǎn)，然后進(jìn)行深度遍歷，然后遍歷1，接著遍歷 2，然后3，此時(shí)完成一條分支0 - 1- 2- 3的遍歷，換一條分支，也就是4，4后面因?yàn)?已經(jīng)遍歷過了，所以就不訪問了

用代碼表示則如下：

const visited = new Set() 
const dfs = (n) => { 
  console.log(n) 
  visited.add(n) // 訪問過添加記錄 
  graph[n].forEach(c => { 
    if(!visited.has(c)){ // 判斷是否訪問呢過 
      dfs(c) 
    } 
  }) 
} 

廣度優(yōu)先遍歷

先訪問離根節(jié)點(diǎn)最近的節(jié)點(diǎn)，然后進(jìn)行入隊(duì)操作，解決思路如下：

• 新建一個(gè)隊(duì)列，把根節(jié)點(diǎn)入隊(duì)
• 把隊(duì)頭出隊(duì)并訪問
• 把隊(duì)頭的沒訪問過的相鄰節(jié)點(diǎn)入隊(duì)
• 重復(fù)二、三步驟，知道隊(duì)列為空

用代碼標(biāo)識(shí)則如下：

const visited = new Set() 
const dfs = (n) => { 
  visited.add(n) 
  const q = [n] 
  while(q.length){ 
    const n = q.shift() 
    console.log(n) 
    graph[n].forEach(c => { 
      if(!visited.has(c)){ 
        q.push(c)   
        visited.add(c) 
      } 
    }) 
  } 
} 

三、總結(jié)

通過上面的初步了解，可以看到圖就是由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間的邊組成的集合，分成了無向圖與有向圖

圖的表達(dá)形式可以分成鄰接矩陣和鄰接表兩種形式，在javascript中，則可以通過二維數(shù)組和對(duì)象的形式進(jìn)行表達(dá)

圖實(shí)際是很復(fù)雜的，后續(xù)還可以延伸出無向圖和帶權(quán)圖，對(duì)應(yīng)如下圖所示：

參考文獻(xiàn)

https://zh.wikipedia.org/wiki/%E5%9B%BE_(%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84)

https://www.kancloud.cn/imnotdown1019/java_core_full/2159607