[LeetCode] DFS && BFS

[plh97]

graph = {
  "A": ["B","C"],
  "B": ["A", "C", "D"],
  "C": ["A", "B", "D", "E"],
  "D": ["B", "C", "E", "F"],
  "E": ["C", "D"],
  "F": ["D"],
}

DFS 依靠stack后入后出来设计深度优先.
BSF 依靠queue先入后出来设计广度优先.

DSF 深度优先搜索(python)

def DSF(graph , s):
  stack=[]
  stack.append(s)
  seen = set()
  seen.add(s)
  while (len(stack) > 0):
    vertex = stack.pop()
    nodes = graph[vertex]
    for w in nodes:
      if w not in seen:
        stack.append(w)
        seen.add(w)
    print(vertex)

DSF(graph, "A")  # A->C->E->D->F->B

BSF 广度优先搜索(python)

依靠queue先入先出的概念,来实现广度搜索.

def BSF(graph , s):
  queue=[]                 # 直接当做数组来看待.
  queue.append(s)          # [].append => [1,2,3] ,  队列将初始节点 S加入
  seen = set()             # 就是无序不重复集合
  seen.add(s)              # set([]).add() => set([1,2,3])   集合将初始节点加入
  while (len(queue) > 0):  # 当队列长度>0 就一直循环
    vertex = queue.pop(0)  # 队列将第一个元素推出, 并赋值给 vertex
    nodes = graph[vertex]  # 队列 在图中找出所有可能的下个节点, 并赋值给nodes
    for w in nodes:        # 循环nodejs所有可能,
      if w not in seen:    # 如果这个可能的下个节点没有走过
        queue.append(w)    # 推入队列, 也就是下一个要走的节点目标由queue队列组合.
        seen.add(w)        # 将它加入集合中, 这个节点已经走过, 不再走了.
    print(vertex)          # 打印当前走的节点.


BSF(graph, "A")  # A->B->C->D->E->F

---

BSF 广度优先(JavaScript)

function BSF(graph, s) {
  // queue 队列  [a, b, c, d]  移入 [new, a, b, c] , 移除 pop
  queue = []
  queue.unshift(s)
  seen = new Set()
  seen.add(s)       // 用于记录曾经访问过的节点, 不再访问
  while (queue.length > 0) {
    vertex = queue.shift()
    nodes = graph[vertex]
    for (let w of nodes) {
      if (!seen.has(w)) {
        queue.unshift(w)
        seen.add(w)
      }
    }
    console.log(vertex)
  }
}

// A->B->C->D->E->F
BSF(graph, "A")

DSF 深度优先(JavaScript)

// 深度优先
function DSF(graph, s) {
  stack = []
  stack.push(s)
  seen = new Set()
  seen.add(s)
  while (stack.length > 0) {
    vertex = stack.pop()
    nodes = graph[vertex]
    for (let w of nodes) {
      if (!seen.has(w)) {
        stack.push(w)
        seen.add(w)
      }
    }
    console.log(vertex)
  }
}

// A->C->E->D->F->B
DSF(graph, "A")

---

var graph = map[string][]string{
	"A": []string{"B", "C"},
	"B": []string{"A", "C", "D"},
	"C": []string{"A", "B", "D", "E"},
	"D": []string{"B", "C", "E", "F"},
	"E": []string{"C", "D"},
	"F": []string{"D"},
}

深度优先 DFS(GoLang)

func DFS(graph map[string][]string, s string) []string {
	res := []string{}
	stack := []string{}
	stack = append([]string{s}, stack...) // 队列压入最后一个
	seen := make(map[string]string)       // 可去重的集合映射关系
	seen[s] = s
	for len(stack) > 0 {
		vertex := stack[0] // 队列推出最后一个
		stack = stack[1:]
		nodes := graph[vertex]
		for i := range nodes {
			node := nodes[i]
			_, ok := seen[node]
			if !ok {
				stack = append([]string{node}, stack...) // 队列压入最后一个
				seen[node] = node
			}
		}
		res = append(res, vertex)
	}
	return res
}

---

广度优先 BFS(GoLang)

func BSF(graph map[string][]string, s string) []string {
	res := []string{}
	queue := []string{}
	queue = append([]string{s}, queue...) // 队列压入第一个
	seen := make(map[string]string)       // 可去重的集合映射关系
	seen[s] = s
	for len(queue) > 0 {
		vertex := queue[len(queue)-1] // 队列推出最后一个
		queue = queue[:len(queue)-1]
		nodes := graph[vertex]
		for i := range nodes {
			node := nodes[i]
			_, ok := seen[node]
			if !ok {
				queue = append([]string{node}, queue...) // 插入第一个
				seen[node] = node
			}
		}
		res = append(res, vertex)
	}
	return res
}

参考

YouTube视频: [Python] BFS和DFS算法

leetcode练手

107. Binary Tree Level Order Traversal II