0
Software Development

## 【Day33】[演算法]-深度優先搜尋DFS與廣度優先搜尋BFS

### JavaScript

``````class Graph {
constructor() {
}

//新增頂點
} else {
return '頂點已存在';
}
}

//新增邊
}else {
return '第二項頂點不存在';
}
} else {
return '第一項頂點不存在';
}
}

//刪除頂點
removeVertex(vertex) {
this.removeEdge(vertex, item)
});
} else {
return '此頂點已不存在';
}
}

//刪除邊
removeEdge(vertex1, vertex2) {
(vertex) => vertex !== vertex2
)
(vertex) => vertex !== vertex1
)
}else {
return '第二項頂點已不存在';
}
} else {
return '第一項頂點已不存在';
}
}

printGraph(){
}

//廣度優先
bfs(start) {
const queue = [start];
const result = [];
const visited = {};
visited[start] = true;
let currentVertex;
while (queue.length) {
currentVertex = queue.shift();
result.push(currentVertex);
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);
if (!visited[neighbor]) {
visited[neighbor] = true;
stack.push(neighbor);
}
});
}
return result;
}

}

let graph = new Graph();

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()
while(len(queue)>0):
currentVertex = queue.pop(0)
result.append(currentVertex)
for neighbor in graph[currentVertex]:
if neighbor not in visited:
queue.append(neighbor)
return result
def dfs(graph,start):
stack = []
result = []
stack.append(start)
visited = set()
while(len(stack)>0):
currentVertex = stack.pop()
result.append(currentVertex)
for neighbor in graph[currentVertex]:
if neighbor not in visited:
stack.append(neighbor)