摘要：單鏈表與雙向鏈表單鏈表是表示一系列節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，其中每個(gè)節(jié)點(diǎn)指向列表中的下一個(gè)節(jié)點(diǎn)。且分別稱為該結(jié)點(diǎn)的左子樹與右子樹。由于二叉樹是非線性結(jié)構(gòu)，因此，樹的遍歷實(shí)質(zhì)上是將二叉樹的各個(gè)結(jié)點(diǎn)轉(zhuǎn)換成為一個(gè)線性序列來表示。

1. 什么是數(shù)據(jù)結(jié)構(gòu)？

數(shù)據(jù)結(jié)構(gòu)是在計(jì)算機(jī)中組織和存儲(chǔ)數(shù)據(jù)的一種特殊方式，使得數(shù)據(jù)可以高效地被訪問和修改。更確切地說，數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)值的集合，表示數(shù)據(jù)之間的關(guān)系，也包括了作用在數(shù)據(jù)上的函數(shù)或操作。

1.1 為什么我們需要數(shù)據(jù)結(jié)構(gòu)？

數(shù)據(jù)是計(jì)算機(jī)科學(xué)當(dāng)中最關(guān)鍵的實(shí)體，而數(shù)據(jù)結(jié)構(gòu)則可以將數(shù)據(jù)以某種組織形式存儲(chǔ)，因此，數(shù)據(jù)結(jié)構(gòu)的價(jià)值不言而喻。

無論你以何種方式解決何種問題，你都需要處理數(shù)據(jù)——無論是涉及員工薪水、股票價(jià)格、購物清單，還是只是簡單的電話簿問題。

數(shù)據(jù)需要根據(jù)不同的場景，按照特定的格式進(jìn)行存儲(chǔ)。有很多數(shù)據(jù)結(jié)構(gòu)能夠滿足以不同格式存儲(chǔ)數(shù)據(jù)的需求。

1.2 八大常見的數(shù)據(jù)結(jié)構(gòu)

數(shù)組：Array

堆棧：Stack

隊(duì)列：Queue

鏈表：Linked Lists

樹：Trees

圖：Graphs

字典樹：Trie

散列表（哈希表）：Hash Tables

在較高的層次上，基本上有三種類型的數(shù)據(jù)結(jié)構(gòu):

堆棧和隊(duì)列是類似于數(shù)組的結(jié)構(gòu)，僅在項(xiàng)目的插入和刪除方式上有所不同。

鏈表，樹，和圖 結(jié)構(gòu)的節(jié)點(diǎn)是引用到其他節(jié)點(diǎn)。

散列表依賴于散列函數(shù)來保存和定位數(shù)據(jù)。

在復(fù)雜性方面：

堆棧和隊(duì)列是最簡單的，并且可以從中構(gòu)建鏈表。

樹和圖 是最復(fù)雜的，因?yàn)樗鼈償U(kuò)展了鏈表的概念。

散列表和字典樹 需要利用這些數(shù)據(jù)結(jié)構(gòu)來可靠地執(zhí)行。

就效率而已：

鏈表是記錄和存儲(chǔ)數(shù)據(jù)的最佳選擇

而哈希表和字典樹 在搜索和檢索數(shù)據(jù)方面效果最佳。

2. 數(shù)組 - 知識(shí)補(bǔ)充

數(shù)組是最簡單的數(shù)據(jù)結(jié)構(gòu)，這里就不講過多了。 貼一張每個(gè)函數(shù)都運(yùn)行10,000次迭代：

10,000個(gè)隨機(jī)密鑰在10,000個(gè)對(duì)象的數(shù)組中查找的執(zhí)行效率對(duì)比圖：

[
  {
    id: "key0",
    content: "I ate pizza 0 times"
  },
  {
    id: "key1",
    content: "I ate pizza 1 times"
  },
  {
    id: "key2",
    content: "I ate pizza 2 times"
  },
  ...
]

["key284", "key958", "key23", "key625", "key83", "key9", ... ]

2.1 for... in為何這么慢？

for... in語法令人難以置信的緩慢。在測(cè)試中就已經(jīng)比正常情況下慢近9倍的循環(huán)。

這是因?yàn)?b>for ... in語法是第一個(gè)能夠迭代對(duì)象鍵的JavaScript語句。

循環(huán)對(duì)象鍵（{}）與在數(shù)組（[]）上進(jìn)行循環(huán)不同，

因?yàn)橐鏁?huì)執(zhí)行一些額外的工作來跟蹤已經(jīng)迭代的屬性。

3. 堆棧：Stack

瀏覽器歷史記錄

撤消操作

遞歸以及其它。

三句話解釋堆棧：

兩個(gè)原則操作：push和pop。Push 將元素添加到數(shù)組的頂部，而Pop將它們從同一位置刪除。

遵循"Last In，F(xiàn)irst Out"，即：LIFO，后進(jìn)先出。

沒了。

3.1 堆棧的實(shí)現(xiàn)。

請(qǐng)注意，下方例子中，我們可以顛倒堆棧的順序：底部變?yōu)轫敳浚敳孔優(yōu)榈撞俊?/p>

因此，我們可以分別使用數(shù)組unshift和shift方法代替push和pop。

class Stack {
    constructor(...items) {
        this.reverse = false;
        this.stack = [...items];
    }

    push(...items) {
        return this.reverse
            ");
4. 隊(duì)列：Queue
在計(jì)算機(jī)科學(xué)中，一個(gè)隊(duì)列(queue)是一種特殊類型的抽象數(shù)據(jù)類型或集合。集合中的實(shí)體按順序保存。

而在前端開發(fā)中，最著名的隊(duì)列使用當(dāng)屬瀏覽器/NodeJs中 關(guān)于宏任務(wù)與微任務(wù)，任務(wù)隊(duì)列的知識(shí)。這里就不再贅述了。

在后端領(lǐng)域，用得最廣泛的就是消息隊(duì)列：Message queue：如RabbitMQ、ActiveMQ等。
以編程思想而言，Queue可以用兩句話描述：

只是具有兩個(gè)主要操作的數(shù)組：unshift和pop。
遵循"Fist In，first out"即：FIFO，先進(jìn)先出。


4.1 隊(duì)列的實(shí)現(xiàn)
請(qǐng)注意，下方例子中，我們可以顛倒堆隊(duì)列的順序。
因此，我們可以分別使用數(shù)組unshift和shift方法代替push和pop。
class Queue {
    constructor(...items) {
        this.reverse = false;
        this.queue = [...items];
    }

    enqueue(...items) {
        return this.reverse
            ");
5. 鏈表：Linked Lists
與數(shù)組一樣，鏈表是按順序存儲(chǔ)數(shù)據(jù)元素。
鏈表不是保留索引，而是指向其他元素。

第一個(gè)節(jié)點(diǎn)稱為頭部(head)，而最后一個(gè)節(jié)點(diǎn)稱為尾部(tail)。

單鏈表與雙向鏈表：

單鏈表是表示一系列節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，其中每個(gè)節(jié)點(diǎn)指向列表中的下一個(gè)節(jié)點(diǎn)。
鏈表通常需要遍歷整個(gè)操作列表，因此性能較差。
提高鏈表性能的一種方法是在每個(gè)節(jié)點(diǎn)上添加指向列表中上一個(gè)節(jié)點(diǎn)的第二個(gè)指針。
雙向鏈表具有指向其前后元素的節(jié)點(diǎn)。

鏈表的優(yōu)點(diǎn)：

鏈接具有常量時(shí)間 插入和刪除，因?yàn)槲覀兛梢灾桓闹羔槨?/p>
與數(shù)組一樣，鏈表可以作為堆棧運(yùn)行。

鏈表的應(yīng)用場景：
鏈接列表在客戶端和服務(wù)器上都很有用。

在客戶端上，像Redux就以鏈表方式構(gòu)建其中的邏輯。
React 核心算法 React Fiber的實(shí)現(xiàn)就是鏈表。





React Fiber之前的Stack Reconciler，是自頂向下的遞歸mount/update，無法中斷(持續(xù)占用主線程)，這樣主線程上的布局、動(dòng)畫等周期性任務(wù)以及交互響應(yīng)就無法立即得到處理，影響體驗(yàn)。




React Fiber解決過去Reconciler存在的問題的思路是把渲染/更新過程(遞歸diff)拆分成一系列小任務(wù)，每次檢查樹上的一小部分，做完看是否還有時(shí)間繼續(xù)下一個(gè)任務(wù)，有的話繼續(xù)，沒有的話把自己掛起，主線程不忙的時(shí)候再繼續(xù)。


在服務(wù)器上，像Express這樣的Web框架也以類似的方式構(gòu)建其中間件邏輯。當(dāng)請(qǐng)求被接收時(shí)，它從一個(gè)中間件管道輸送到下一個(gè)，直到響應(yīng)被發(fā)出。

5.1 單鏈表實(shí)現(xiàn)
單鏈表的操作核心有：

push（value） - 在鏈表的末尾/頭部添加一個(gè)節(jié)點(diǎn)
pop（） - 從鏈表的末尾/頭部刪除一個(gè)節(jié)點(diǎn)
get（index） - 返回指定索引處的節(jié)點(diǎn)
delete（index） - 刪除指定索引處的節(jié)點(diǎn)
isEmpty（） - 根據(jù)列表長度返回true或false
print（） - 返回鏈表的可見表示

class Node {
  constructor(data) {
    this.data = data
    this.next = null
  }
}

class LinkedList {
  constructor() {
    this.head = null
    this.tail = null
    // 長度非必要
    this.length = 0
  }
  push(data) {
    // 創(chuàng)建一個(gè)新節(jié)點(diǎn)
    const node = new Node(data)
    // 檢查頭部是否為空
    if (this.head === null) {
      this.head = node
      this.tail = node
    } 
    this.tail.next = node
    this.tail = node
    this.length++
  }
  pop(){
    // 先檢查鏈表是否為空
    if(this.isEmpty()) {
      return null
    } 
    // 如果長度為1
    if (this.head === this.tail) {
      this.head = null
      this.tail = null
      this.length--
      return this.tail
    }
    let node = this.tail
    let currentNode = this.head
    let penultimate
    
    while (currentNode) {
      if (currentNode.next === this.tail) {
        penultimate = currentNode
        break
      }
      currentNode = currentNode.next
    }
    
    penultimate.next = null
    this.tail = penultimate
    this.length --
    return node
  }
  
  get(index){
    // 處理邊界條件
    if (index === 0) {
      return this.head
    }
    if (index < 0 || index > this.length) {
      return null
    }
    
    let currentNode = this.head
    let i = 0
    while(i < index) {
      i++
      currentNode = currentNode.next
    }
    return currentNode
    
  }
  delete(index){
    let currentNode = this.head
    
    if (index === 0) {
      let deletedNode
      currentNode.next = this.head
      deletedNode = currentNode
      this.length--
      
      return deletedNode
    }
    
    if (index < 0 || index > this.length) {
      return null
    }
    
    let i = 0
    let previous
    
    while(i < index) {
      i++
      previous = currentNode
      currentNode = currentNode.next
    }
    previous.next = currentNode.next
    this.length--
    return currentNode
  }
  
  isEmpty() {
    return this.length === 0
  }
  print() {
    const list = []
    let currentNode = this.head
    while(currentNode){
      list.push(currentNode.data)
      currentNode = currentNode.next
    }
    return list.join(" => ")
  }
}
測(cè)試一下：
const l = new LinkedList()

// 添加節(jié)點(diǎn)
const values = ["A", "B", "C"]
values.forEach(value => l.push(value))

console.log(l)
console.log(l.pop())
console.log(l.get(1))
console.log(l.isEmpty())
console.log(l.print())

5.2 雙向鏈表實(shí)現(xiàn)
1. 雙向鏈表的設(shè)計(jì)
類似于單鏈表，雙向鏈表由一系列節(jié)點(diǎn)組成。每個(gè)節(jié)點(diǎn)包含一些數(shù)據(jù)以及指向列表中下一個(gè)節(jié)點(diǎn)的指針和指向前一個(gè)節(jié)點(diǎn)的指針。這是JavaScript中的簡單表示：
class Node {
    constructor(data) {
        // data 包含鏈表項(xiàng)應(yīng)存儲(chǔ)的值
        this.data = data;
        // next 是指向列表中下一項(xiàng)的指針
        this.next = null;
        // prev 是指向列表中上一項(xiàng)的指針
        this.prev = null;
    }
}

還是敲一遍吧：

class DoublyLinkedList {
    constructor() {
    	this.head = null;
        this.tail = null;
    }
    // 各種操作方法
    // ...
}
2. 雙向鏈表的操作方法


Append & AppendAt: 在鏈表的尾部/ 指定位置添加節(jié)點(diǎn)

append( item ) {
  let node = new Node( item );
  if(!this.head) {
    this.head = node;
    this.tail = node;
  } else {
    node.prev = this.tail;
    this.tail.next = node;
    this.tail = node
  }
}

appendAt( pos, item ) {
   let current = this.head;
   let counter = 1;
   let node = new Node( item );
   if( pos == 0 ) {
     this.head.prev = node
     node.next = this.head
     this.head = node
   } else {
     while(current) {
      current = current.next;
      if( counter == pos ) {
        node.prev = current.prev
        current.prev.next = node
        node.next = current
        current.prev = node
      }
      counter++
    }
  }
}


Remove & RemoveAt: 在鏈表的尾部/ 指定位置刪除節(jié)點(diǎn)

remove( item ) {
  let current = this.head;
  while( current ) {
    if( current.data === item ) {
      if( current == this.head && current == this.tail ) {
        this.head = null;
        this.tail = null;
      } else if ( current == this.head ) {
        this.head = this.head.next
        this.head.prev = null
      } else if ( current == this.tail ) {
        this.tail = this.tail.prev;
        this.tail.next = null;
      } else {
        current.prev.next = current.next;
        current.next.prev = current.prev;
      }
   }
   current = current.next
  }
}

removeAt( pos ) {
  let current = this.head;
  let counter = 1;
  if( pos == 0 ) {
   this.head = this.head.next;
   this.head.prev = null;
  } else {
   while( current ) {
    current = current.next
    if ( current == this.tail ) {
     this.tail = this.tail.prev;
     this.tail.next = null;
    } else if( counter == pos ) {
     current.prev.next = current.next;
     current.next.prev = current.prev;
     break;
    }
    counter++;
   }
  }
}


Reverse: 翻轉(zhuǎn)雙向鏈表

reverse(){
  let current = this.head;
  let prev = null;
  while( current ){
   let next = current.next
   current.next = prev
   current.prev = next
   prev = current
   current = next
  }
  this.tail = this.head
  this.head = prev
}



Swap：兩節(jié)點(diǎn)間交換。

swap( nodeOne, nodeTwo ) {
   let current = this.head;
   let counter = 0;
   let firstNode;
   while( current !== null ) {
     if( counter == nodeOne ){
       firstNode = current;
     } else if( counter == nodeTwo ) {
       let temp = current.data;
       current.data = firstNode.data;
       firstNode.data = temp;
     }
     current = current.next;
     counter++;
   }
   return true
}


IsEmpty & Length：查詢是否為空或長度。

length() {
  let current = this.head;
  let counter = 0;
  while( current !== null ) {
   counter++
   current = current.next
  }
  return counter;
}
isEmpty() {
  return this.length() < 1
}


Traverse: 遍歷鏈表

traverse( fn ) {
   let current = this.head;
   while( current !== null ) {
    fn(current)
    current = current.next;
   }
   return true;
}

每一項(xiàng)都加10

Search：查找節(jié)點(diǎn)的索引。

search( item ) {
  let current = this.head;
  let counter = 0;
  while( current ) {
    if( current.data == item ) {
     return counter
    }
    current = current.next
    counter++
  }
  return false;
}

6. 樹：Tree
計(jì)算機(jī)中經(jīng)常用到的一種非線性的數(shù)據(jù)結(jié)構(gòu)——樹（Tree），由于其存儲(chǔ)的所有元素之間具有明顯的層次特性，因此常被用來存儲(chǔ)具有層級(jí)關(guān)系的數(shù)據(jù)，比如文件系統(tǒng)中的文件；也會(huì)被用來存儲(chǔ)有序列表等。

在樹結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)只有一個(gè)父結(jié)點(diǎn)，若一個(gè)結(jié)點(diǎn)無父節(jié)點(diǎn)，則稱為樹的根結(jié)點(diǎn)，簡稱樹的根（root）。
每一個(gè)結(jié)點(diǎn)可以有多個(gè)子結(jié)點(diǎn)。
沒有子結(jié)點(diǎn)的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。
一個(gè)結(jié)點(diǎn)所擁有的子結(jié)點(diǎn)的個(gè)數(shù)稱為該結(jié)點(diǎn)的度。
所有結(jié)點(diǎn)中最大的度稱為樹的度。樹的最大層次稱為樹的深度。

6.1 樹的分類
常見的樹分類如下，其中我們掌握二叉搜索樹即可。

二叉樹：Binary Search Tree
AVL樹：AVL Tree
紅黑樹：Red-Black Tree
線段樹： Segment Tree - with min/max/sum range queries examples
芬威克樹：Fenwick Tree (Binary Indexed Tree)

6.2 樹的應(yīng)用

DOM樹。每個(gè)網(wǎng)頁都有一個(gè)樹數(shù)據(jù)結(jié)構(gòu)。


2. Vue和React的Virtual DOM也是樹。

6.3 二叉樹：Binary Search Tree

二叉樹是一種特殊的樹，它的子節(jié)點(diǎn)個(gè)數(shù)不超過兩個(gè)。
且分別稱為該結(jié)點(diǎn)的左子樹（left subtree）與右子樹（right subtree）。
二叉樹常被用作二叉查找樹和二叉搜索樹、或是二叉排序樹（BST）。


6.4 二叉樹的遍歷
按一定的規(guī)則和順序走遍二叉樹的所有結(jié)點(diǎn)，使每一個(gè)結(jié)點(diǎn)都被訪問一次，而且只被訪問一次，這個(gè)操作被稱為樹的遍歷，是對(duì)樹的一種最基本的運(yùn)算。
由于二叉樹是非線性結(jié)構(gòu)，因此，樹的遍歷實(shí)質(zhì)上是將二叉樹的各個(gè)結(jié)點(diǎn)轉(zhuǎn)換成為一個(gè)線性序列來表示。
按照根節(jié)點(diǎn)訪問的順序不同，二叉樹的遍歷分為以下三種：前序遍歷，中序遍歷，后序遍歷；
前序遍歷：Pre-Order
根節(jié)點(diǎn)->左子樹->右子樹


中序遍歷：In-Order
左子樹->根節(jié)點(diǎn)->右子樹


后序遍歷：Post-Order
左子樹->右子樹->根節(jié)點(diǎn)


因此我們可以得之上面二叉樹的遍歷結(jié)果如下：

前序遍歷：ABDEFGC
中序遍歷：DEBGFAC
后序遍歷：EDGFBCA

6.5 二叉樹的實(shí)現(xiàn)
class Node { 
  constructor(data) { 
    this.left = null
    this.right = null
    this.value = data
  } 
} 

class BST {
    constructor() {
        this.root = null
    }
    // 二叉樹的各種操作
    // insert(value) {...}
    // insertNode(root, newNode) {...}
    // ...
1. insertNode& insert：插入新子節(jié)點(diǎn)/節(jié)點(diǎn)
  insertNode(root, newNode) {
    if (newNode.value < root.value) {
      // 先執(zhí)行無左節(jié)點(diǎn)操作
      (!root.left) ");
2. removeNode& remove：移除子節(jié)點(diǎn)/節(jié)點(diǎn)
  removeNode(root, value) {
    if (!root) {
      return null
    }
    
    // 從該值小于根節(jié)點(diǎn)開始判斷
    if (value < root.value) {
      root.left = this.removeNode(root.left, value)
      return root
    } else if (value > root.value) {
      root.right = tis.removeNode(root.right, value)
      return root
    } else {
      // 如果沒有左右節(jié)點(diǎn)
      if (!root.left && !root.right) {
        root = null
        return root
      }
      
      // 存在左節(jié)點(diǎn)
      if (root.left) {
        root = root.left
        return root
      // 存在右節(jié)點(diǎn)
      } else if (root.right) {
        root = root.right
        return root
      }
      
      // 獲取正確子節(jié)點(diǎn)的最小值以確保我們有有效的替換
      let minRight = this.findMinNode(root.right)
      root.value = minRight.value
      // 確保刪除已替換的節(jié)點(diǎn)
      root.right = this.removeNode(root.right, minRight.value)
      return root
    }
  }
  
remove(value) {
    if (!this.root) {
      return "Tree is empty!"
    } else {
      this.removeNode(this.root, value)
    }
}
  
3. findMinNode:獲取子節(jié)點(diǎn)的最小值
findMinNode(root) {
    if (!root.left) {
      return root
    } else {
      return this.findMinNode(root.left)
    }
}
4. searchNode & search：查找子節(jié)點(diǎn)/節(jié)點(diǎn)
searchNode(root, value) {
    if (!root) {
      return null
    }
    
    if (value < root.value) {
      return this.searchNode(root.left, value)
    } else if (value > root.value) {
      return this.searchNode(root.right, value)
    }
    
    return root
}

search(value) {
    if (!this.root) {
      return "Tree is empty"
    } else {
      return Boolean(this.searchNode(this.root, value))
    }
}

Pre-Order：前序遍歷

preOrder(root) {
    if (!root) {
      return "Tree is empty"
    } else {
      console.log(root.value)
      this.preOrder(root.left)
      this.preOrder(root.right)
    }
  }

In-Order：中序遍歷

inOrder(root) {
    if (!root) {
      return "Tree is empty"
    } else {
      this.inOrder(root.left)
      console.log(root.value)
      this.inOrder(root.right)
    }
  }

Post-Order：后序遍歷

postOrder(root) {
    if (!root) {
      return "Tree is empty"
    } else {
      this.postOrder(root.left)
      this.postOrder(root.right)
      console.log(root.value)
    }
}
7. 圖：Graph
圖是由具有邊的節(jié)點(diǎn)集合組成的數(shù)據(jù)結(jié)構(gòu)。圖可以是定向的或不定向的。
圖的介紹普及，找了一圈文章，還是這篇最佳：
Graphs—-A Visual Introduction for Beginners


7.1 圖的應(yīng)用
在以下場景中，你都使用到了圖：

使用搜索服務(wù)，如Google，百度。
使用LBS地圖服務(wù)，如高德，谷歌地圖。
使用社交媒體網(wǎng)站，如微博，Facebook。


圖用于不同的行業(yè)和領(lǐng)域：

GPS系統(tǒng)和谷歌地圖使用圖表來查找從一個(gè)目的地到另一個(gè)目的地的最短路徑。
社交網(wǎng)絡(luò)使用圖表來表示用戶之間的連接。
Google搜索算法使用圖 來確定搜索結(jié)果的相關(guān)性。
運(yùn)營研究是一個(gè)使用圖 來尋找降低運(yùn)輸和交付貨物和服務(wù)成本的最佳途徑的領(lǐng)域。
甚至化學(xué)使用圖 來表示分子！

圖，可以說是應(yīng)用最廣泛的數(shù)據(jù)結(jié)構(gòu)之一，真實(shí)場景中處處有圖。
7.2 圖的構(gòu)成
圖表用于表示，查找，分析和優(yōu)化元素（房屋，機(jī)場，位置，用戶，文章等）之間的連接。

1. 圖的基本元素

節(jié)點(diǎn)：Node，比如地鐵站中某個(gè)站/多個(gè)村莊中的某個(gè)村莊/互聯(lián)網(wǎng)中的某臺(tái)主機(jī)/人際關(guān)系中的人.
邊：Edge，比如地鐵站中兩個(gè)站點(diǎn)之間的直接連線, 就是一個(gè)邊。


2. 符號(hào)和術(shù)語


|V|=圖中頂點(diǎn)（節(jié)點(diǎn)）的總數(shù)。


|E|=圖中的連接總數(shù)（邊）。


在下面的示例中
|V| = 6 
|E| = 7 

3. 有向圖與無向圖
圖根據(jù)其邊（連接）的特征進(jìn)行分類。
1. 有向圖
在有向圖中，邊具有方向。它們從一個(gè)節(jié)點(diǎn)轉(zhuǎn)到另一個(gè)節(jié)點(diǎn)，并且無法通過該邊返回到初始節(jié)點(diǎn)。
如下圖所示，邊（連接）現(xiàn)在具有指向特定方向的箭頭。 將這些邊視為單行道。您可以向一個(gè)方向前進(jìn)并到達(dá)目的地，但是你無法通過同一條街道返回，因此您需要找到另一條路徑。

有向圖
2. 無向圖
在這種類型的圖中，邊是無向的（它們沒有特定的方向）。將無向邊視為雙向街道。您可以從一個(gè)節(jié)點(diǎn)轉(zhuǎn)到另一個(gè)節(jié)點(diǎn)并返回相同的“路徑”。

4. 加權(quán)圖
在加權(quán)圖中，每條邊都有一個(gè)與之相關(guān)的值（稱為權(quán)重）。該值用于表示它們連接的節(jié)點(diǎn)之間的某種可量化關(guān)系。例如：

權(quán)重可以表示距離，時(shí)間，社交網(wǎng)絡(luò)中兩個(gè)用戶之間共享的連接數(shù)。
或者可以用于描述您正在使用的上下文中的節(jié)點(diǎn)之間的連接的任何內(nèi)容。


著名的Dijkstra算法，就是使用這些權(quán)重通過查找網(wǎng)絡(luò)中節(jié)點(diǎn)之間的最短或最優(yōu)的路徑來優(yōu)化路由。
5. 稀疏圖與密集圖
當(dāng)圖中的邊數(shù)接近最大邊數(shù)時(shí)，圖是密集的。

密集圖
當(dāng)圖中的邊數(shù)明顯少于最大邊數(shù)時(shí)，圖是稀疏的。

稀疏圖
6. 循環(huán)
如果你按照?qǐng)D中的一系列連接，可能會(huì)找到一條路徑，將你帶回到同一節(jié)點(diǎn)。這就像“走在圈子里”，就像你在城市周圍開車一樣，你走的路可以帶你回到你的初始位置。