【Day33】[演算法]-深度优先搜寻DFS与广度优先搜寻BFS

深度优先搜寻(Depth-First Search,DFS)与广度优先搜寻(Breadth-First Search, BFS)，是可以用来走访或搜寻树节点与图顶点的演算法，先前介绍的二元树走访就是使用上述方法走访各节点，这边以图结构来介绍。

树的走访可以参考此篇。

下面相邻串列构成的图来示范搜寻

图的介绍可以参考此篇。

深度优先搜寻DFS

先选定一个顶点开始走访，接着从此顶点相邻未被走过的顶点中，择一走访标示为记录点，以此类推，不断从新记录点的相邻未被走过顶点中寻找。
若新纪录点的相邻顶点都被走过，则退回前一个纪录点，继续从未被走过顶点中寻找。

深度优先可以利用堆叠(Stack)的方式来处理。

堆叠的介绍可以参考此篇。

广度优先搜寻BFS

先选定一个顶点开始走访，逐一走过此顶点相邻未被走过的顶点，若相邻顶点都被走过，再从走访过的顶点中择一为新记录点，逐一走过新记录点相邻未被走过的顶点，以此类推。

广度优先可以利用伫列(Queue)的方式来处理。

伫列的介绍可以参考此篇。

JavaScript

class Graph {
  constructor() {
    this.adjacencyList = {}
  }

	//新增顶点
  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) {
     	this.adjacencyList[vertex] = []
    } else {
      return '顶点已存在';
    }
  }
  
  //新增边
  addEdge(vertex1, vertex2) {
    if (this.adjacencyList[vertex1]) {
      if (this.adjacencyList[vertex2]){
        this.adjacencyList[vertex1].push(vertex2)
        this.adjacencyList[vertex2].push(vertex1)
      }else {
        return '第二项顶点不存在';
      }
    } else {
      return '第一项顶点不存在';
    }
  }
  
  //删除顶点
  removeVertex(vertex) {
    if (this.adjacencyList[vertex]) {
     	this.adjacencyList[vertex].forEach(function(item) {
        this.removeEdge(vertex, item)
        delete this.adjacencyList[vertex]
      });
    } else {
      return '此顶点已不存在';
    }
  }
  
  //删除边
  removeEdge(vertex1, vertex2) {
    if (this.adjacencyList[vertex1]) {
      if (this.adjacencyList[vertex2]){
        this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
        	(vertex) => vertex !== vertex2
        )
        this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
        	(vertex) => vertex !== vertex1
        )
      }else {
        return '第二项顶点已不存在';
      }
    } else {
      return '第一项顶点已不存在';
    }
  }

	printGraph(){
  	console.log(this.adjacencyList)
  }
  
  //广度优先
	bfs(start) {
      const queue = [start];
      const result = [];
      const visited = {};
      visited[start] = true;
      let currentVertex;
      while (queue.length) {
        currentVertex = queue.shift();
        result.push(currentVertex);
        this.adjacencyList[currentVertex].forEach(neighbor => {
          if (!visited[neighbor]) {
            visited[neighbor] = true;
            queue.push(neighbor);
          }
        });
      }
      return result;
  }
  
  //深度优先
  dfs(start) {
      const result = [];
      const stack = [start];
      const visited = {};
      visited[start] = true;
      let currentVertex;
      while (stack.length) {
        currentVertex = stack.pop();
        result.push(currentVertex);
        this.adjacencyList[currentVertex].forEach(neighbor => {
          if (!visited[neighbor]) {
            visited[neighbor] = true;
            stack.push(neighbor);
          }
        });
      }
      return result;
  }  

}

let graph = new Graph();

graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addVertex('E');
graph.addVertex('F');

graph.addEdge('A', 'B');
graph.addEdge('A', 'D');
graph.addEdge('A', 'E');
graph.addEdge('B', 'C');
graph.addEdge('D', 'E');
graph.addEdge('E', 'F');
graph.addEdge('E', 'C');
graph.printGraph();
//{
//  A: ["B", "D", "E"],
//  B: ["A", "C"],
//  C: ["B", "E"],
//  D: ["A", "E"],
//  E: ["A", "D", "F", "C"],
//  F: ["E"]
//}

console.log(graph.bfs('A'))
//["A", "B", "D", "E", "C", "F"]
console.log(graph.dfs('A'))
//["A", "E", "C", "F", "D", "B"]
console.log(graph.dfs('B'))
//["B", "C", "E", "F", "D", "A"]
console.log(graph.dfs('C'))
//["C", "E", "F", "D", "A", "B"]
console.log(graph.dfs('D'))
//["D", "E", "C", "B", "F", "A"]
console.log(graph.dfs('E'))
//["E", "C", "B", "F", "D", "A"]
console.log(graph.dfs('F'))
//["F", "E", "C", "B", "D", "A"]

Python

#Graph
graph = {
    'A': ["B", "D", "E"],
    'B': ["A", "C"],
    'C': ["B", "E"],
    'D': ["A", "E"],
    'E': ["A", "D", "F", "C"],
    'F': ["E"]     
}
def bfs(graph,start):
    queue = []
    queue.append(start)
    result = []
    visited = set()
    visited.add(start)
    while(len(queue)>0):
        currentVertex = queue.pop(0)
        result.append(currentVertex)
        for neighbor in graph[currentVertex]:
            if neighbor not in visited:
                queue.append(neighbor)
                visited.add(neighbor)
    return result
def dfs(graph,start):
    stack = []
    result = []
    stack.append(start)
    visited = set()
    visited.add(start)
    while(len(stack)>0):
        currentVertex = stack.pop()
        result.append(currentVertex)
        for neighbor in graph[currentVertex]:
            if neighbor not in visited:
                stack.append(neighbor)
                visited.add(neighbor)
    return result


print(bfs(graph,'A'))
#['A', 'B', 'D', 'E', 'C', 'F']

print(dfs(graph,'A'))
#['A', 'E', 'C', 'F', 'D', 'B']