Dfs và bfs khác nhau như thế nào

Nếu 1 người nào đó trong gia phả muốn tìm kiếm 1 người nào đó vẫn còn sống thì ta thấy DFS  thường hoạt động nhanh hơn.Tuy nhiên, nếu người đó muốn tìm một người nào đó đã mất cách đây rất lâu thì BFS thường nhanh hơn DFS.

Nói tóm lại , cái nào tốt hơn cái nào thì còn tùy thuộc vào dữ liệu và những gì bạn đang tìm kiếm.

Code: nếu bạn nào rành C# thì sẽ thấy code rất gần với mã giả vì trong C# đã hỗ trợ kiểu dữ liệu tree, stack, queue, list(có sẵn các hàm truy vấn dữ liệu luôn)… vì vậy công việc của bạn chỉ là gọi đúng hàm đúng việc là được.

Ah còn câu thầy hỏi BFS và DFS là thuật toán hay giải thuật mình xin có vài ý kiến.

Theo mình biết vẫn chưa có định nghĩa thuật toán nào được chấp nhận cả và ít thông dụng, nhưng còn giải thuật (đặc biệt là giải thuật heurictis) thì được sử dụng rộng rãi. Để đáp ứng những yêu cầu của thuật toán đòi hỏi thời gian chạy rất lớn, hoặc các điều kiện cho thuật toán khó đáp ứng(tính xác định và tính đúng đắn). Tuy nhiên ngày nay người ta đã mở rộng 2 tiêu chuẩn này.Chẳng hạn mở rộng tính xác định thể hiện qua các giải thuật đệ quy và ngẫu nhiên.Còn tính chính xác thì người ta đã chấp nhận các cách giải ít phức tạp và cho kết quả tốt(nhưng không phải lúc nào cũng tốt).

Các cách giải chấp nhận được nhưng không hoàn toàn đáp ứng đủ các tiêu chuẩn của thuật toán được gọi là giải thuật.

Vì vậy mình nghĩ BFS và DFS là thuật toán. Vì nó thỏa 2 yêu cầu của thuật toán.Dữ liệu là có giới hạn, chẳng hạn các trạng thái của 1 ván cờ vua tuy nhiều nhưng có giới hạn vì nó giới hạn trong phạm vi bàn cờ, giới hạn số quân và giới hạn cách đi của mỗi quân cờ. Vậy là thỏa tính xác định. Tính đúng đắn thì khỏi bàn cải, chỉ cần thứ mình tìm có tồn tại trong dữ liệu chắc chắn sẽ tìm thấy, vì nó duyệt qua hết “ngóc ngách” của dữ liệu.

Trong bài này, class

function bfs(s, e) {
// Do a BFS starting at node s
let prev = solve(s);// Return reconstructed path from s to e
return reconstructPath(s, e, prev);
}function solve(s) {
let q = [];
q.push(s); // enqueue method: push node into the arraylet visited = new Array(graph.vertices).fill(false);
visited[s] = true;let prev = new Array(graph.vertices).fill(null);while (q.length) {
let node = q.shift(); // dequeue method: shift first node (s) from the array
let neighbors = graph.edges[node]; // get all neighbors (nodes) in adjacency list of slet curr = neighbors.head;
while (curr) {
if (!visited[curr.data]) {
if (!q.includes(curr.data)) {
q.push(curr.data);
}
visited[curr.data] = true;
prev[curr.data] = node;
}
curr = curr.next;
}
}
return prev;
}function reconstructPath(s, e, prev) {
let path = [];for (let i = e; i !== null; i = prev[i]) {
path.push(i);
}path.reverse();if (path[0] === s) {
return path;
}
return [];
}console.log(bfs(0, 3)); // Returns [0, 1, 3]2 mình sử dụng để biểu diễn đồ thị là graph có các adjacency lists được biểu diễn dưới dạng linked list được mình implement trong phần 1.

Breadth first search — BFS (Tìm kiếm chiều rộng):

Breadth first search là thuật toán tìm kiếm đơn giản nhất trong graph và có thể được sử dụng nhiều trong các thuật toán khác: thuật toán của Prim tìm cây khung nhỏ nhất, thuật toán Dijkstra tìm đường đi ngắn nhất cũng sử dụng ý tưởng giống với BFS. Thuật toán BFS thường tỏ ra hiệu quả khi mình cần tìm đường đi ngắn nhất (shortest path) trong một đồ thị không trọng số (unweighted graph).

Ý tưởng của thuật toán BFS là mình sẽ bắt đầu tại một node (thường gọi là source) của đồ thị sau đó “loang” ra các node kề (hoặc có cạnh nối) với node source, trước khi đi đến những node kề xa hơn.

Để biết được những node nào sẽ được thăm, BFS sử dụng một queue (hàng đợi) để lưu thông tin các node kề với node đang được thăm. Đây cũng là một khác biệt quan trọng của BFS với DFS, mình có thể viết DFS dưới dạng đệ quy (gọi lại hàn DFS(), giống hình ảnh của Stack — ngăn xếp) nhưng khi implement BFS thì cần nhớ thuật toán này sử dụng Queue.

Queue Q có thể được implement đơn giản bằng một mảng và hai thao tác enqueue, dequeue tương ứng với thao tác push và shift (để đảm bảo tính FIFO của queue) trong array.

function Queue() {
collection = [];
this.print = function () {
console.log(collection);
};
// this method push the first item into the queue (at the end of the array)
this.enqueue = function (element) {
collection.push(element);
};
// this method take the item off the queue
this.dequeue = function () {
return collection.shift(); // remove the first item of the array
};
this.front = function () {
return collection[0];
};
this.size = function () {
return collection.length;
};
this.isEmpty = function () {
return collection.length === 0;
};
}

Khi nói đến độ phức tạp của thuật toán BFS này, trong giải thuật trên, chúng ta có vòng lặp đầu tiên để khởi tạo những giá trị ban đầu cho các đỉnh trong G.V trừ đỉnh source (gốc), có O(V) time complexity. Các thao tác gán giá trị cho đỉnh source sau đó mất O(1). Việc enqueue và dequeue cũng mất thời gian O(1). Vòng lặp khi queue Q khác rỗng thực chất là mình đang đi duyệt tất cả các cạnh trong danh sách kề với đỉnh u. Như vậy, khi vòng lặp kết thúc, tất cả các cạnh sẽ được duyệt nên mình có time complexity là O(E). Từ đó mình có thể kết luận độ phức tạp về mặt thời gian cho thuật toán này là O(V+E).

Bidirectional search

Bidirectional search được sử dụng để tìm đường đi ngắn nhất giữa 2 đỉnh source và destination. Thuật toán chạy hai hàm BFS, một bắt đầu từ đỉnh source và một bắt đầu từ đỉnh destination.

Trong thuật toán BFS nguyên thủy, mình search k nodes kề với node gốc, mỗi node kề lại có thể có thêm k′ nodes kề với node kth. Nếu mình thực hiện d lần thì mình phải search qua O(k^d) nodes. Ví dụ trong hình trên là d=4.

Bidirectional search sẽ giúp mình giảm xuống còn khoảng k^(d/2) nodes cho mỗi thuật toán chạy BFS từ đỉnh s và từ đỉnh t.

Implement thuật toán BFS

Sau khi đã tìm hiểu ý tưởng của thuật toán BFS, mình sẽ implement thuật toán này với JavaScript. Yêu cầu của mình hiện tại là hàm

function bfs(s, e) {
// Do a BFS starting at node s
let prev = solve(s);// Return reconstructed path from s to e
return reconstructPath(s, e, prev);
}function solve(s) {
let q = [];
q.push(s); // enqueue method: push node into the arraylet visited = new Array(graph.vertices).fill(false);
visited[s] = true;let prev = new Array(graph.vertices).fill(null);while (q.length) {
let node = q.shift(); // dequeue method: shift first node (s) from the array
let neighbors = graph.edges[node]; // get all neighbors (nodes) in adjacency list of slet curr = neighbors.head;
while (curr) {
if (!visited[curr.data]) {
if (!q.includes(curr.data)) {
q.push(curr.data);
}
visited[curr.data] = true;
prev[curr.data] = node;
}
curr = curr.next;
}
}
return prev;
}function reconstructPath(s, e, prev) {
let path = [];for (let i = e; i !== null; i = prev[i]) {
path.push(i);
}path.reverse();if (path[0] === s) {
return path;
}
return [];
}console.log(bfs(0, 3)); // Returns [0, 1, 3]3 sẽ nhận vào 2 tham số đầu vào tương ứng với 2 nodes s và e sau đó sẽ in ra đường đi ngắn nhất từ s tới e (nếu có) bằng thuật toán BFS.

Để thuận tiện, hàm

function bfs(s, e) {
// Do a BFS starting at node s
let prev = solve(s);// Return reconstructed path from s to e
return reconstructPath(s, e, prev);
}function solve(s) {
let q = [];
q.push(s); // enqueue method: push node into the arraylet visited = new Array(graph.vertices).fill(false);
visited[s] = true;let prev = new Array(graph.vertices).fill(null);while (q.length) {
let node = q.shift(); // dequeue method: shift first node (s) from the array
let neighbors = graph.edges[node]; // get all neighbors (nodes) in adjacency list of slet curr = neighbors.head;
while (curr) {
if (!visited[curr.data]) {
if (!q.includes(curr.data)) {
q.push(curr.data);
}
visited[curr.data] = true;
prev[curr.data] = node;
}
curr = curr.next;
}
}
return prev;
}function reconstructPath(s, e, prev) {
let path = [];for (let i = e; i !== null; i = prev[i]) {
path.push(i);
}path.reverse();if (path[0] === s) {
return path;
}
return [];
}console.log(bfs(0, 3)); // Returns [0, 1, 3]3 của mình sẽ gọi lần lượt tới 2 hàm con là

function bfs(s, e) {
// Do a BFS starting at node s
let prev = solve(s);// Return reconstructed path from s to e
return reconstructPath(s, e, prev);
}function solve(s) {
let q = [];
q.push(s); // enqueue method: push node into the arraylet visited = new Array(graph.vertices).fill(false);
visited[s] = true;let prev = new Array(graph.vertices).fill(null);while (q.length) {
let node = q.shift(); // dequeue method: shift first node (s) from the array
let neighbors = graph.edges[node]; // get all neighbors (nodes) in adjacency list of slet curr = neighbors.head;
while (curr) {
if (!visited[curr.data]) {
if (!q.includes(curr.data)) {
q.push(curr.data);
}
visited[curr.data] = true;
prev[curr.data] = node;
}
curr = curr.next;
}
}
return prev;
}function reconstructPath(s, e, prev) {
let path = [];for (let i = e; i !== null; i = prev[i]) {
path.push(i);
}path.reverse();if (path[0] === s) {
return path;
}
return [];
}console.log(bfs(0, 3)); // Returns [0, 1, 3]5 và

function bfs(s, e) {
// Do a BFS starting at node s
let prev = solve(s);// Return reconstructed path from s to e
return reconstructPath(s, e, prev);
}function solve(s) {
let q = [];
q.push(s); // enqueue method: push node into the arraylet visited = new Array(graph.vertices).fill(false);
visited[s] = true;let prev = new Array(graph.vertices).fill(null);while (q.length) {
let node = q.shift(); // dequeue method: shift first node (s) from the array
let neighbors = graph.edges[node]; // get all neighbors (nodes) in adjacency list of slet curr = neighbors.head;
while (curr) {
if (!visited[curr.data]) {
if (!q.includes(curr.data)) {
q.push(curr.data);
}
visited[curr.data] = true;
prev[curr.data] = node;
}
curr = curr.next;
}
}
return prev;
}function reconstructPath(s, e, prev) {
let path = [];for (let i = e; i !== null; i = prev[i]) {
path.push(i);
}path.reverse();if (path[0] === s) {
return path;
}
return [];
}console.log(bfs(0, 3)); // Returns [0, 1, 3]6. Như tên gọi, hàm

function bfs(s, e) {
// Do a BFS starting at node s
let prev = solve(s);// Return reconstructed path from s to e
return reconstructPath(s, e, prev);
}function solve(s) {
let q = [];
q.push(s); // enqueue method: push node into the arraylet visited = new Array(graph.vertices).fill(false);
visited[s] = true;let prev = new Array(graph.vertices).fill(null);while (q.length) {
let node = q.shift(); // dequeue method: shift first node (s) from the array
let neighbors = graph.edges[node]; // get all neighbors (nodes) in adjacency list of slet curr = neighbors.head;
while (curr) {
if (!visited[curr.data]) {
if (!q.includes(curr.data)) {
q.push(curr.data);
}
visited[curr.data] = true;
prev[curr.data] = node;
}
curr = curr.next;
}
}
return prev;
}function reconstructPath(s, e, prev) {
let path = [];for (let i = e; i !== null; i = prev[i]) {
path.push(i);
}path.reverse();if (path[0] === s) {
return path;
}
return [];
}console.log(bfs(0, 3)); // Returns [0, 1, 3]7 áp dụng thuật toán BFS tìm kiếm đường đi đến tất cả các đỉnh trong đồ thị bắt đầu từ đỉnh s. Kết quả hàm

function bfs(s, e) {
// Do a BFS starting at node s
let prev = solve(s);// Return reconstructed path from s to e
return reconstructPath(s, e, prev);
}function solve(s) {
let q = [];
q.push(s); // enqueue method: push node into the arraylet visited = new Array(graph.vertices).fill(false);
visited[s] = true;let prev = new Array(graph.vertices).fill(null);while (q.length) {
let node = q.shift(); // dequeue method: shift first node (s) from the array
let neighbors = graph.edges[node]; // get all neighbors (nodes) in adjacency list of slet curr = neighbors.head;
while (curr) {
if (!visited[curr.data]) {
if (!q.includes(curr.data)) {
q.push(curr.data);
}
visited[curr.data] = true;
prev[curr.data] = node;
}
curr = curr.next;
}
}
return prev;
}function reconstructPath(s, e, prev) {
let path = [];for (let i = e; i !== null; i = prev[i]) {
path.push(i);
}path.reverse();if (path[0] === s) {
return path;
}
return [];
}console.log(bfs(0, 3)); // Returns [0, 1, 3]7 trả về là một mảng lưu thông tin prev với prev[i] cho biết node liền trước node i theo thuật toán BFS. Từ mảng prev này, hàm

function bfs(s, e) {
// Do a BFS starting at node s
let prev = solve(s);// Return reconstructed path from s to e
return reconstructPath(s, e, prev);
}function solve(s) {
let q = [];
q.push(s); // enqueue method: push node into the arraylet visited = new Array(graph.vertices).fill(false);
visited[s] = true;let prev = new Array(graph.vertices).fill(null);while (q.length) {
let node = q.shift(); // dequeue method: shift first node (s) from the array
let neighbors = graph.edges[node]; // get all neighbors (nodes) in adjacency list of slet curr = neighbors.head;
while (curr) {
if (!visited[curr.data]) {
if (!q.includes(curr.data)) {
q.push(curr.data);
}
visited[curr.data] = true;
prev[curr.data] = node;
}
curr = curr.next;
}
}
return prev;
}function reconstructPath(s, e, prev) {
let path = [];for (let i = e; i !== null; i = prev[i]) {
path.push(i);
}path.reverse();if (path[0] === s) {
return path;
}
return [];
}console.log(bfs(0, 3)); // Returns [0, 1, 3]9 sẽ truy vết ngược lại và in ra đường đi ngắn nhất từ đỉnh s tới đỉnh e, trường hợp không có sẽ trả về mảng rỗng.

function bfs(s, e) {
// Do a BFS starting at node s
let prev = solve(s);// Return reconstructed path from s to e
return reconstructPath(s, e, prev);
}function solve(s) {
let q = [];
q.push(s); // enqueue method: push node into the arraylet visited = new Array(graph.vertices).fill(false);
visited[s] = true;let prev = new Array(graph.vertices).fill(null);while (q.length) {
let node = q.shift(); // dequeue method: shift first node (s) from the array
let neighbors = graph.edges[node]; // get all neighbors (nodes) in adjacency list of slet curr = neighbors.head;
while (curr) {
if (!visited[curr.data]) {
if (!q.includes(curr.data)) {
q.push(curr.data);
}
visited[curr.data] = true;
prev[curr.data] = node;
}
curr = curr.next;
}
}
return prev;
}function reconstructPath(s, e, prev) {
let path = [];for (let i = e; i !== null; i = prev[i]) {
path.push(i);
}path.reverse();if (path[0] === s) {
return path;
}
return [];
}console.log(bfs(0, 3)); // Returns [0, 1, 3]

Việc chứng minh đường đi (nếu có) từ s đến e, trong trường hợp test của mình là từ 0 đến 3 theo BFS cũng chính là đường đi ngắn nhất từ s đến e ( từ 0 đến 3) (theo định nghĩa đi qua ít cạnh nhất), các bạn có thể xem trong sách Introduction to Algorithms, CLRS (implement bằng mã giả) hoặc tài liệu của thầy Lê Minh Hoàng (implement bằng Pascal).

Thử một đồ thị có nhiều đỉnh và cạnh hơn để xem thuật toán của mình chạy như thế nào:

const graph = new Graph(13);
graph.addEdge(1, 10);
graph.addEdge(1, 8);
graph.addEdge(0, 9);
graph.addEdge(0, 7);
graph.addEdge(0, 11);
graph.addEdge(9, 8);
graph.addEdge(8, 12);
graph.addEdge(2, 12);
graph.addEdge(3, 4);
graph.addEdge(3, 2);
graph.addEdge(3, 7);
graph.addEdge(7, 11);
graph.addEdge(6, 7);
graph.addEdge(5, 6);
graph.addEdge(10, 9);console.log("BFS shortest path from 5 -> 12: ", bfs(5, 12)); // returns [5, 6, 7, 3, 2, 12]
console.log("BFS shortest path from 0 -> 11", bfs(0, 11)); // returns [0, 11]
console.log("BFS shortest path from 11 -> 3", bfs(11, 3)); // returns [11, 7, 3]
console.log("BFS shortest path from 0 -> 12", bfs(0, 12)); // returns [0, 9, 8, 12]

Ngoài ra, cách cài đặt trên cho hàm

function bfs(s, e) {
// Do a BFS starting at node s
let prev = solve(s);// Return reconstructed path from s to e
return reconstructPath(s, e, prev);
}function solve(s) {
let q = [];
q.push(s); // enqueue method: push node into the arraylet visited = new Array(graph.vertices).fill(false);
visited[s] = true;let prev = new Array(graph.vertices).fill(null);while (q.length) {
let node = q.shift(); // dequeue method: shift first node (s) from the array
let neighbors = graph.edges[node]; // get all neighbors (nodes) in adjacency list of slet curr = neighbors.head;
while (curr) {
if (!visited[curr.data]) {
if (!q.includes(curr.data)) {
q.push(curr.data);
}
visited[curr.data] = true;
prev[curr.data] = node;
}
curr = curr.next;
}
}
return prev;
}function reconstructPath(s, e, prev) {
let path = [];for (let i = e; i !== null; i = prev[i]) {
path.push(i);
}path.reverse();if (path[0] === s) {
return path;
}
return [];
}console.log(bfs(0, 3)); // Returns [0, 1, 3]3 cho phép mình trả lời được câu hỏi: Cho một đồ thị (có thể vô hướng hoặc không), xác định liệu có đường đi nối giữa hai đỉnh cho trước hay không. Mình sẽ đi sâu vào ứng dụng của BFS và DFS trong các bài tiếp theo.

Depth First Search — DFS (Tìm kiếm chiều sâu)

Tương tự như thuật toán BFS, mình cũng sẽ tìm hiểu template của thuật toán DFS trước bằng mã giả sau đó implement chi tiết bằng JavaScript.

Thuật toán DFS ưu tiên duyệt theo chiều “sâu”. Bắt đầu từ node source, DFS sẽ duyệt các node thuộc cùng một nhánh đến khi không thể đi xa hơn được nữa, mình mới chuyển sang duyệt nhánh tiếp theo (đệ quy backtrack). Thuật toán cứ tiếp tục đến khi tất cả các cạnh của đồ thị được duyệt quạ

Như vậy, có thể thấy về mặt time complexity, DFS cũng giống như BFS là O(V+E).

Trong các bài toán tìm đường đi ngắn nhất hoặc duyệt để kiểm tra có hay không đường đi giữa các đỉnh thì thuật toán BFS tỏ ra hiệu quả hơn dù phần cài đặt cần nhiều kỹ thuật một chút . DFS sẽ không có hiệu quả khi implement thuần túy, tuy nhiên ý tưởng của DFS sẽ rất hiệu quả trong các thuật toán quan trọng của đồ thị về tìm thành phần liên thông, liên thông mạnh, xác định khớp đồ thị, …

Implement thuật toán DFS

Bây giờ mình sẽ implement thuật toán DFS bằng ngôn ngữ JavaScript. Để thuận tiện mình sẽ không đánh dấu hay tô màu các đỉnh dựa vào trạng thái của chúng trong quá trình duyệt như mã giả ở trên, thay vào đó mình dùng một mảng

const graph = new Graph(13);
graph.addEdge(1, 10);
graph.addEdge(1, 8);
graph.addEdge(0, 9);
graph.addEdge(0, 7);
graph.addEdge(0, 11);
graph.addEdge(9, 8);
graph.addEdge(8, 12);
graph.addEdge(2, 12);
graph.addEdge(3, 4);
graph.addEdge(3, 2);
graph.addEdge(3, 7);
graph.addEdge(7, 11);
graph.addEdge(6, 7);
graph.addEdge(5, 6);
graph.addEdge(10, 9);console.log("BFS shortest path from 5 -> 12: ", bfs(5, 12)); // returns [5, 6, 7, 3, 2, 12]
console.log("BFS shortest path from 0 -> 11", bfs(0, 11)); // returns [0, 11]
console.log("BFS shortest path from 11 -> 3", bfs(11, 3)); // returns [11, 7, 3]
console.log("BFS shortest path from 0 -> 12", bfs(0, 12)); // returns [0, 9, 8, 12]1 (giống như phần implement BFS) để đánh dấu xem nếu

const graph = new Graph(13);
graph.addEdge(1, 10);
graph.addEdge(1, 8);
graph.addEdge(0, 9);
graph.addEdge(0, 7);
graph.addEdge(0, 11);
graph.addEdge(9, 8);
graph.addEdge(8, 12);
graph.addEdge(2, 12);
graph.addEdge(3, 4);
graph.addEdge(3, 2);
graph.addEdge(3, 7);
graph.addEdge(7, 11);
graph.addEdge(6, 7);
graph.addEdge(5, 6);
graph.addEdge(10, 9);console.log("BFS shortest path from 5 -> 12: ", bfs(5, 12)); // returns [5, 6, 7, 3, 2, 12]
console.log("BFS shortest path from 0 -> 11", bfs(0, 11)); // returns [0, 11]
console.log("BFS shortest path from 11 -> 3", bfs(11, 3)); // returns [11, 7, 3]
console.log("BFS shortest path from 0 -> 12", bfs(0, 12)); // returns [0, 9, 8, 12]2 thì đỉnh i đã được duyệt, ngược lại ban đầu tất cả các đỉnh chưa được duyệt qua thì

const graph = new Graph(13);
graph.addEdge(1, 10);
graph.addEdge(1, 8);
graph.addEdge(0, 9);
graph.addEdge(0, 7);
graph.addEdge(0, 11);
graph.addEdge(9, 8);
graph.addEdge(8, 12);
graph.addEdge(2, 12);
graph.addEdge(3, 4);
graph.addEdge(3, 2);
graph.addEdge(3, 7);
graph.addEdge(7, 11);
graph.addEdge(6, 7);
graph.addEdge(5, 6);
graph.addEdge(10, 9);console.log("BFS shortest path from 5 -> 12: ", bfs(5, 12)); // returns [5, 6, 7, 3, 2, 12]
console.log("BFS shortest path from 0 -> 11", bfs(0, 11)); // returns [0, 11]
console.log("BFS shortest path from 11 -> 3", bfs(11, 3)); // returns [11, 7, 3]
console.log("BFS shortest path from 0 -> 12", bfs(0, 12)); // returns [0, 9, 8, 12]3.

Chương trình

const graph = new Graph(13);
graph.addEdge(1, 10);
graph.addEdge(1, 8);
graph.addEdge(0, 9);
graph.addEdge(0, 7);
graph.addEdge(0, 11);
graph.addEdge(9, 8);
graph.addEdge(8, 12);
graph.addEdge(2, 12);
graph.addEdge(3, 4);
graph.addEdge(3, 2);
graph.addEdge(3, 7);
graph.addEdge(7, 11);
graph.addEdge(6, 7);
graph.addEdge(5, 6);
graph.addEdge(10, 9);console.log("BFS shortest path from 5 -> 12: ", bfs(5, 12)); // returns [5, 6, 7, 3, 2, 12]
console.log("BFS shortest path from 0 -> 11", bfs(0, 11)); // returns [0, 11]
console.log("BFS shortest path from 11 -> 3", bfs(11, 3)); // returns [11, 7, 3]
console.log("BFS shortest path from 0 -> 12", bfs(0, 12)); // returns [0, 9, 8, 12]4 nhận tham số đầu vào là s, đỉnh bắt đầu duyệt và có chương trình con

const graph = new Graph(13);
graph.addEdge(1, 10);
graph.addEdge(1, 8);
graph.addEdge(0, 9);
graph.addEdge(0, 7);
graph.addEdge(0, 11);
graph.addEdge(9, 8);
graph.addEdge(8, 12);
graph.addEdge(2, 12);
graph.addEdge(3, 4);
graph.addEdge(3, 2);
graph.addEdge(3, 7);
graph.addEdge(7, 11);
graph.addEdge(6, 7);
graph.addEdge(5, 6);
graph.addEdge(10, 9);console.log("BFS shortest path from 5 -> 12: ", bfs(5, 12)); // returns [5, 6, 7, 3, 2, 12]
console.log("BFS shortest path from 0 -> 11", bfs(0, 11)); // returns [0, 11]
console.log("BFS shortest path from 11 -> 3", bfs(11, 3)); // returns [11, 7, 3]
console.log("BFS shortest path from 0 -> 12", bfs(0, 12)); // returns [0, 9, 8, 12]5 để thực hiện thăm tất cả các đỉnh theo ý tưởng DFS nếu đỉnh đó trong mảng đánh dấu

const graph = new Graph(13);
graph.addEdge(1, 10);
graph.addEdge(1, 8);
graph.addEdge(0, 9);
graph.addEdge(0, 7);
graph.addEdge(0, 11);
graph.addEdge(9, 8);
graph.addEdge(8, 12);
graph.addEdge(2, 12);
graph.addEdge(3, 4);
graph.addEdge(3, 2);
graph.addEdge(3, 7);
graph.addEdge(7, 11);
graph.addEdge(6, 7);
graph.addEdge(5, 6);
graph.addEdge(10, 9);console.log("BFS shortest path from 5 -> 12: ", bfs(5, 12)); // returns [5, 6, 7, 3, 2, 12]
console.log("BFS shortest path from 0 -> 11", bfs(0, 11)); // returns [0, 11]
console.log("BFS shortest path from 11 -> 3", bfs(11, 3)); // returns [11, 7, 3]
console.log("BFS shortest path from 0 -> 12", bfs(0, 12)); // returns [0, 9, 8, 12]1 là chưa được thăm.

Thủ tục đệ quy

const graph = new Graph(13);
graph.addEdge(1, 10);
graph.addEdge(1, 8);
graph.addEdge(0, 9);
graph.addEdge(0, 7);
graph.addEdge(0, 11);
graph.addEdge(9, 8);
graph.addEdge(8, 12);
graph.addEdge(2, 12);
graph.addEdge(3, 4);
graph.addEdge(3, 2);
graph.addEdge(3, 7);
graph.addEdge(7, 11);
graph.addEdge(6, 7);
graph.addEdge(5, 6);
graph.addEdge(10, 9);console.log("BFS shortest path from 5 -> 12: ", bfs(5, 12)); // returns [5, 6, 7, 3, 2, 12]
console.log("BFS shortest path from 0 -> 11", bfs(0, 11)); // returns [0, 11]
console.log("BFS shortest path from 11 -> 3", bfs(11, 3)); // returns [11, 7, 3]
console.log("BFS shortest path from 0 -> 12", bfs(0, 12)); // returns [0, 9, 8, 12]5 sẽ bắt đầu bằng lời gọi

const graph = new Graph(13);
graph.addEdge(1, 10);
graph.addEdge(1, 8);
graph.addEdge(0, 9);
graph.addEdge(0, 7);
graph.addEdge(0, 11);
graph.addEdge(9, 8);
graph.addEdge(8, 12);
graph.addEdge(2, 12);
graph.addEdge(3, 4);
graph.addEdge(3, 2);
graph.addEdge(3, 7);
graph.addEdge(7, 11);
graph.addEdge(6, 7);
graph.addEdge(5, 6);
graph.addEdge(10, 9);console.log("BFS shortest path from 5 -> 12: ", bfs(5, 12)); // returns [5, 6, 7, 3, 2, 12]
console.log("BFS shortest path from 0 -> 11", bfs(0, 11)); // returns [0, 11]
console.log("BFS shortest path from 11 -> 3", bfs(11, 3)); // returns [11, 7, 3]
console.log("BFS shortest path from 0 -> 12", bfs(0, 12)); // returns [0, 9, 8, 12]8.

function dfs(s) {
let visited = new Array(graph.vertices).fill(false);let visit = (at) => {
if (visited[at]) return;
visited[at] = true;let neighbors = graph.edges[at];
let curr = neighbors.head;
while (curr) {
visit(curr.data);
curr = curr.next;
}
};return visit(s);
}

Để kiểm tra xem hàm

const graph = new Graph(13);
graph.addEdge(1, 10);
graph.addEdge(1, 8);
graph.addEdge(0, 9);
graph.addEdge(0, 7);
graph.addEdge(0, 11);
graph.addEdge(9, 8);
graph.addEdge(8, 12);
graph.addEdge(2, 12);
graph.addEdge(3, 4);
graph.addEdge(3, 2);
graph.addEdge(3, 7);
graph.addEdge(7, 11);
graph.addEdge(6, 7);
graph.addEdge(5, 6);
graph.addEdge(10, 9);console.log("BFS shortest path from 5 -> 12: ", bfs(5, 12)); // returns [5, 6, 7, 3, 2, 12]
console.log("BFS shortest path from 0 -> 11", bfs(0, 11)); // returns [0, 11]
console.log("BFS shortest path from 11 -> 3", bfs(11, 3)); // returns [11, 7, 3]
console.log("BFS shortest path from 0 -> 12", bfs(0, 12)); // returns [0, 9, 8, 12]4 của mình duyệt đúng hay không, mình sẽ thử với test case đồ thị có 13 đỉnh, 15 cạnh giống như hàm

function bfs(s, e) {
// Do a BFS starting at node s
let prev = solve(s);// Return reconstructed path from s to e
return reconstructPath(s, e, prev);
}function solve(s) {
let q = [];
q.push(s); // enqueue method: push node into the arraylet visited = new Array(graph.vertices).fill(false);
visited[s] = true;let prev = new Array(graph.vertices).fill(null);while (q.length) {
let node = q.shift(); // dequeue method: shift first node (s) from the array
let neighbors = graph.edges[node]; // get all neighbors (nodes) in adjacency list of slet curr = neighbors.head;
while (curr) {
if (!visited[curr.data]) {
if (!q.includes(curr.data)) {
q.push(curr.data);
}
visited[curr.data] = true;
prev[curr.data] = node;
}
curr = curr.next;
}
}
return prev;
}function reconstructPath(s, e, prev) {
let path = [];for (let i = e; i !== null; i = prev[i]) {
path.push(i);
}path.reverse();if (path[0] === s) {
return path;
}
return [];
}console.log(bfs(0, 3)); // Returns [0, 1, 3]3 ở trên. Mình sẽ thêm vào trước bước

function dfs(s) {
let visited = new Array(graph.vertices).fill(false);let visit = (at) => {
if (visited[at]) return;
visited[at] = true;let neighbors = graph.edges[at];
let curr = neighbors.head;
while (curr) {
visit(curr.data);
curr = curr.next;
}
};return visit(s);
}1 một dòng

function dfs(s) {
let visited = new Array(graph.vertices).fill(false);let visit = (at) => {
if (visited[at]) return;
visited[at] = true;let neighbors = graph.edges[at];
let curr = neighbors.head;
while (curr) {
visit(curr.data);
curr = curr.next;
}
};return visit(s);
}2 để log ra màn hình node mà hàm

const graph = new Graph(13);
graph.addEdge(1, 10);
graph.addEdge(1, 8);
graph.addEdge(0, 9);
graph.addEdge(0, 7);
graph.addEdge(0, 11);
graph.addEdge(9, 8);
graph.addEdge(8, 12);
graph.addEdge(2, 12);
graph.addEdge(3, 4);
graph.addEdge(3, 2);
graph.addEdge(3, 7);
graph.addEdge(7, 11);
graph.addEdge(6, 7);
graph.addEdge(5, 6);
graph.addEdge(10, 9);console.log("BFS shortest path from 5 -> 12: ", bfs(5, 12)); // returns [5, 6, 7, 3, 2, 12]
console.log("BFS shortest path from 0 -> 11", bfs(0, 11)); // returns [0, 11]
console.log("BFS shortest path from 11 -> 3", bfs(11, 3)); // returns [11, 7, 3]
console.log("BFS shortest path from 0 -> 12", bfs(0, 12)); // returns [0, 9, 8, 12]4 đang duyệt.

Khi đó kết quả ở màn hình console mình thu được như sau:

visit node: 0
visit node: 9
visit node: 8
visit node: 1
visit node: 10
visit node: 12
visit node: 2
visit node: 3
visit node: 4
visit node: 7
visit node: 11
visit node: 6
visit node: 5

Sau khi đối chiếu với hình minh họa của đồ thị này trong phần BFS ở trên, mình thấy kết quả duyệt theo DFS là đúng.

Như đã nói, thuật toán DFS sẽ rất hữu dụng trong việc xác định các connected components của đồ thị nên mình sẽ thử áp dụng ý tưởng DFS trên cho bài toán này. Các ứng dụng khác của DFS sẽ được nói đến ở các bài sau.

Connected Component

Connected components có thể được định nghĩa là những vùng thuộc đồ thị, bao gồm các đỉnh sao cho 2 đỉnh x, y bất kỳ trong 1 component mình luôn có:

• luôn tồn tại đường đi từ x đến y
• đồng thời gọi xA là đỉnh thuộc component A và xB là đỉnh thuộc component B khi đó cạnh (xA,yB) không thuộc E và không tồn tại đường đi từ xA đến xB

Các components này chia graph ban đầu thành những vùng khác nhau, mình có thể phân biệt các vùng này bằng cách đánh dấu các đỉnh thuộc cùng một component thành 1 màu. Việc tô màu các đỉnh tương đương với việc mình label các đỉnh trong component đó bằng cùng một giá trị nào đó, có thể là (0,1,2,…) giống như hình minh họa dưới đây:

Giả sử ban đầu các đỉnh chưa được tô màu, mình sẽ tạo một đồ thị như hình trên và đánh số các đỉnh theo thứ tự từ 0…17.

let newGraph = new Graph(18);newGraph.addEdge(0, 4);
newGraph.addEdge(0, 8);
newGraph.addEdge(0, 13);
newGraph.addEdge(0, 14);
newGraph.addEdge(14, 8);
newGraph.addEdge(13, 14);
newGraph.addEdge(4, 8);
newGraph.addEdge(1, 5);
newGraph.addEdge(17, 5);
newGraph.addEdge(5, 16);
newGraph.addEdge(6, 11);
newGraph.addEdge(11, 7);
newGraph.addEdge(7, 6);
newGraph.addEdge(3, 9);
newGraph.addEdge(9, 2);
newGraph.addEdge(2, 15);
newGraph.addEdge(9, 15);
newGraph.addEdge(10, 15);

Thuật toán ở đây là mình cũng sẽ cần một mảng đánh dấu xem node thứ ith đã được duyệt qua hay chưa là

const graph = new Graph(13);
graph.addEdge(1, 10);
graph.addEdge(1, 8);
graph.addEdge(0, 9);
graph.addEdge(0, 7);
graph.addEdge(0, 11);
graph.addEdge(9, 8);
graph.addEdge(8, 12);
graph.addEdge(2, 12);
graph.addEdge(3, 4);
graph.addEdge(3, 2);
graph.addEdge(3, 7);
graph.addEdge(7, 11);
graph.addEdge(6, 7);
graph.addEdge(5, 6);
graph.addEdge(10, 9);console.log("BFS shortest path from 5 -> 12: ", bfs(5, 12)); // returns [5, 6, 7, 3, 2, 12]
console.log("BFS shortest path from 0 -> 11", bfs(0, 11)); // returns [0, 11]
console.log("BFS shortest path from 11 -> 3", bfs(11, 3)); // returns [11, 7, 3]
console.log("BFS shortest path from 0 -> 12", bfs(0, 12)); // returns [0, 9, 8, 12]1. Bắt đầu từ một node chưa được duyệt, thuật toán DFS sẽ duyệt qua tất cả các node đồng thời label các node này bằng một

function dfs(s) {
let visited = new Array(graph.vertices).fill(false);let visit = (at) => {
if (visited[at]) return;
visited[at] = true;let neighbors = graph.edges[at];
let curr = neighbors.head;
while (curr) {
visit(curr.data);
curr = curr.next;
}
};return visit(s);
}5 giống nhau, ví dụ ban đầu mình có thể để

function dfs(s) {
let visited = new Array(graph.vertices).fill(false);let visit = (at) => {
if (visited[at]) return;
visited[at] = true;let neighbors = graph.edges[at];
let curr = neighbors.head;
while (curr) {
visit(curr.data);
curr = curr.next;
}
};return visit(s);
}6 hoặc

function dfs(s) {
let visited = new Array(graph.vertices).fill(false);let visit = (at) => {
if (visited[at]) return;
visited[at] = true;let neighbors = graph.edges[at];
let curr = neighbors.head;
while (curr) {
visit(curr.data);
curr = curr.next;
}
};return visit(s);
}7.

Hàm

function dfs(s) {
let visited = new Array(graph.vertices).fill(false);let visit = (at) => {
if (visited[at]) return;
visited[at] = true;let neighbors = graph.edges[at];
let curr = neighbors.head;
while (curr) {
visit(curr.data);
curr = curr.next;
}
};return visit(s);
}8 trả về 2 giá trị

function dfs(s) {
let visited = new Array(graph.vertices).fill(false);let visit = (at) => {
if (visited[at]) return;
visited[at] = true;let neighbors = graph.edges[at];
let curr = neighbors.head;
while (curr) {
visit(curr.data);
curr = curr.next;
}
};return visit(s);
}9 là số connected components có trong graph và mảng

visit node: 0
visit node: 9
visit node: 8
visit node: 1
visit node: 10
visit node: 12
visit node: 2
visit node: 3
visit node: 4
visit node: 7
visit node: 11
visit node: 6
visit node: 50 cho biết thông tin node thứ ith thuộc component thứ components[i].

function findComponents() {
let count = 0;
let components = [];
let visited = new Array(newGraph.vertices).fill(false);for (let i = 0; i < newGraph.vertices; i++) {
if (!visited[i]) {
count++;
visit(i);
}
}function visit(at) {
visited[at] = true;
components[at] = count;let neighbors = newGraph.edges[at];
let curr = neighbors.head;
while (curr) {
if (!visited[curr.data]) {
visit(curr.data);
}
curr = curr.next;
}
}return {
count: count,
components: components,
};
}console.log("Find components: ", findComponents());

Kết quả ở màn hình console của mình:

Find components: {
count: 5,
components: [
1, 2, 3, 3, 1, 2, 4,
4, 1, 3, 3, 4, 5, 1,
1, 3, 2, 2
]
}

Từ mảng

visit node: 0
visit node: 9
visit node: 8
visit node: 1
visit node: 10
visit node: 12
visit node: 2
visit node: 3
visit node: 4
visit node: 7
visit node: 11
visit node: 6
visit node: 50 mà hàm

function dfs(s) {
let visited = new Array(graph.vertices).fill(false);let visit = (at) => {
if (visited[at]) return;
visited[at] = true;let neighbors = graph.edges[at];
let curr = neighbors.head;
while (curr) {
visit(curr.data);
curr = curr.next;
}
};return visit(s);
}8 trả về mình thấy các node (0,4,8,13,14) thuộc cùng một component được label là 1 ... Đúng với hình vẽ minh họa

visit node: 0
visit node: 9
visit node: 8
visit node: 1
visit node: 10
visit node: 12
visit node: 2
visit node: 3
visit node: 4
visit node: 7
visit node: 11
visit node: 6
visit node: 53 ở trên.

Ngoài ra, mảng

visit node: 0
visit node: 9
visit node: 8
visit node: 1
visit node: 10
visit node: 12
visit node: 2
visit node: 3
visit node: 4
visit node: 7
visit node: 11
visit node: 6
visit node: 50 được trả về từ hàm

function dfs(s) {
let visited = new Array(graph.vertices).fill(false);let visit = (at) => {
if (visited[at]) return;
visited[at] = true;let neighbors = graph.edges[at];
let curr = neighbors.head;
while (curr) {
visit(curr.data);
curr = curr.next;
}
};return visit(s);
}8 cho phép mình liệt kê thông tin của tất cả các connected components trong graph.

Bằng cách sử dụng

visit node: 0
visit node: 9
visit node: 8
visit node: 1
visit node: 10
visit node: 12
visit node: 2
visit node: 3
visit node: 4
visit node: 7
visit node: 11
visit node: 6
visit node: 56, mình sẽ lưu thông tin của các đỉnh thuộc cùng một components và in ra thông tin của map này. Giả sử mình đã có mảng

visit node: 0
visit node: 9
visit node: 8
visit node: 1
visit node: 10
visit node: 12
visit node: 2
visit node: 3
visit node: 4
visit node: 7
visit node: 11
visit node: 6
visit node: 50, chương trình in ra các connected components của mình như sau:

let map = new Map();
for (let i = 0; i < components.length; i++) {
if (map.has(`Connected component ${components[i]}`)) {
map.get(`Connected component ${components[i]}`).push(i);
} else {
map.set(`Connected component ${components[i]}`, [i]);
}
}console.log("Connected Components: ", map);

Thử chạy và kiểm tra kết quả trên màn hình console:

Connected Components: Map {
'Connected component 1' => [ 0, 4, 8, 13, 14 ],
'Connected component 2' => [ 1, 5, 16, 17 ],
'Connected component 3' => [ 2, 3, 9, 10, 15 ],
'Connected component 4' => [ 6, 7, 11 ],
'Connected component 5' => [ 12 ]
}

Trong chương trình in ra các connected components, mình tạo ra một

visit node: 0
visit node: 9
visit node: 8
visit node: 1
visit node: 10
visit node: 12
visit node: 2
visit node: 3
visit node: 4
visit node: 7
visit node: 11
visit node: 6
visit node: 58 để lưu trữ và các thao tác

visit node: 0
visit node: 9
visit node: 8
visit node: 1
visit node: 10
visit node: 12
visit node: 2
visit node: 3
visit node: 4
visit node: 7
visit node: 11
visit node: 6
visit node: 59 và

let newGraph = new Graph(18);newGraph.addEdge(0, 4);
newGraph.addEdge(0, 8);
newGraph.addEdge(0, 13);
newGraph.addEdge(0, 14);
newGraph.addEdge(14, 8);
newGraph.addEdge(13, 14);
newGraph.addEdge(4, 8);
newGraph.addEdge(1, 5);
newGraph.addEdge(17, 5);
newGraph.addEdge(5, 16);
newGraph.addEdge(6, 11);
newGraph.addEdge(11, 7);
newGraph.addEdge(7, 6);
newGraph.addEdge(3, 9);
newGraph.addEdge(9, 2);
newGraph.addEdge(2, 15);
newGraph.addEdge(9, 15);
newGraph.addEdge(10, 15);0 mất thời gian O(1). Bên cạnh đó, mình dùng một vòng

let newGraph = new Graph(18);newGraph.addEdge(0, 4);
newGraph.addEdge(0, 8);
newGraph.addEdge(0, 13);
newGraph.addEdge(0, 14);
newGraph.addEdge(14, 8);
newGraph.addEdge(13, 14);
newGraph.addEdge(4, 8);
newGraph.addEdge(1, 5);
newGraph.addEdge(17, 5);
newGraph.addEdge(5, 16);
newGraph.addEdge(6, 11);
newGraph.addEdge(11, 7);
newGraph.addEdge(7, 6);
newGraph.addEdge(3, 9);
newGraph.addEdge(9, 2);
newGraph.addEdge(2, 15);
newGraph.addEdge(9, 15);
newGraph.addEdge(10, 15);1 để duyệt qua tất cả phần tử của

visit node: 0
visit node: 9
visit node: 8
visit node: 1
visit node: 10
visit node: 12
visit node: 2
visit node: 3
visit node: 4
visit node: 7
visit node: 11
visit node: 6
visit node: 50 nên sẽ mất thời gian là O(N) với N là độ dài mảng

visit node: 0
visit node: 9
visit node: 8
visit node: 1
visit node: 10
visit node: 12
visit node: 2
visit node: 3
visit node: 4
visit node: 7
visit node: 11
visit node: 6
visit node: 50 hay chính là số đỉnh

let newGraph = new Graph(18);newGraph.addEdge(0, 4);
newGraph.addEdge(0, 8);
newGraph.addEdge(0, 13);
newGraph.addEdge(0, 14);
newGraph.addEdge(14, 8);
newGraph.addEdge(13, 14);
newGraph.addEdge(4, 8);
newGraph.addEdge(1, 5);
newGraph.addEdge(17, 5);
newGraph.addEdge(5, 16);
newGraph.addEdge(6, 11);
newGraph.addEdge(11, 7);
newGraph.addEdge(7, 6);
newGraph.addEdge(3, 9);
newGraph.addEdge(9, 2);
newGraph.addEdge(2, 15);
newGraph.addEdge(9, 15);
newGraph.addEdge(10, 15);4 của đồ thị, O(V). Do đó, độ phức tạp time complexity của chương trình này là O(V).

Xác định các connected components bằng BFS

Trong thuật toán tìm thành phần liên thông (Connected Components) ở trên, mình đã sử dụng ý tưởng duyệt DFS. Nếu quan sát kỹ đồ thị ở ví dụ này, mình vẫn có thể xác định các thành phần liên thông bằng thuật toán duyệt BFS.

Cụ thể, thay vì duyệt từ đỉnh 0 (ví dụ) rồi đi đến một đỉnh nào đó có cạnh nối với 0, … thì mình sẽ duyệt theo BFS “loang” ra tất cả các đỉnh kề với đỉnh 0, những đỉnh này chắc chắn sẽ thuộc chung một connected components và sẽ được label chung một chỉ số.

Chương trình dưới đây implement cho thuật toán tìm thành phần liên thông theo BFS.

function bfs(s, e) {
// Do a BFS starting at node s
let prev = solve(s);// Return reconstructed path from s to e
return reconstructPath(s, e, prev);
}function solve(s) {
let q = [];
q.push(s); // enqueue method: push node into the arraylet visited = new Array(graph.vertices).fill(false);
visited[s] = true;let prev = new Array(graph.vertices).fill(null);while (q.length) {
let node = q.shift(); // dequeue method: shift first node (s) from the array
let neighbors = graph.edges[node]; // get all neighbors (nodes) in adjacency list of slet curr = neighbors.head;
while (curr) {
if (!visited[curr.data]) {
if (!q.includes(curr.data)) {
q.push(curr.data);
}
visited[curr.data] = true;
prev[curr.data] = node;
}
curr = curr.next;
}
}
return prev;
}function reconstructPath(s, e, prev) {
let path = [];for (let i = e; i !== null; i = prev[i]) {
path.push(i);
}path.reverse();if (path[0] === s) {
return path;
}
return [];
}console.log(bfs(0, 3)); // Returns [0, 1, 3]0

Thử chạy chương trình và so sánh

visit node: 0
visit node: 9
visit node: 8
visit node: 1
visit node: 10
visit node: 12
visit node: 2
visit node: 3
visit node: 4
visit node: 7
visit node: 11
visit node: 6
visit node: 50 trả về với kết quả của hàm

function dfs(s) {
let visited = new Array(graph.vertices).fill(false);let visit = (at) => {
if (visited[at]) return;
visited[at] = true;let neighbors = graph.edges[at];
let curr = neighbors.head;
while (curr) {
visit(curr.data);
curr = curr.next;
}
};return visit(s);
}8 dùng DFS:

function bfs(s, e) {
// Do a BFS starting at node s
let prev = solve(s);// Return reconstructed path from s to e
return reconstructPath(s, e, prev);
}function solve(s) {
let q = [];
q.push(s); // enqueue method: push node into the arraylet visited = new Array(graph.vertices).fill(false);
visited[s] = true;let prev = new Array(graph.vertices).fill(null);while (q.length) {
let node = q.shift(); // dequeue method: shift first node (s) from the array
let neighbors = graph.edges[node]; // get all neighbors (nodes) in adjacency list of slet curr = neighbors.head;
while (curr) {
if (!visited[curr.data]) {
if (!q.includes(curr.data)) {
q.push(curr.data);
}
visited[curr.data] = true;
prev[curr.data] = node;
}
curr = curr.next;
}
}
return prev;
}function reconstructPath(s, e, prev) {
let path = [];for (let i = e; i !== null; i = prev[i]) {
path.push(i);
}path.reverse();if (path[0] === s) {
return path;
}
return [];
}console.log(bfs(0, 3)); // Returns [0, 1, 3]1

Từ kết quả trả về của hàm

let newGraph = new Graph(18);newGraph.addEdge(0, 4);
newGraph.addEdge(0, 8);
newGraph.addEdge(0, 13);
newGraph.addEdge(0, 14);
newGraph.addEdge(14, 8);
newGraph.addEdge(13, 14);
newGraph.addEdge(4, 8);
newGraph.addEdge(1, 5);
newGraph.addEdge(17, 5);
newGraph.addEdge(5, 16);
newGraph.addEdge(6, 11);
newGraph.addEdge(11, 7);
newGraph.addEdge(7, 6);
newGraph.addEdge(3, 9);
newGraph.addEdge(9, 2);
newGraph.addEdge(2, 15);
newGraph.addEdge(9, 15);
newGraph.addEdge(10, 15);7, mình hoàn toàn có thể xây dựng chương trình in ra thông tin của các

visit node: 0
visit node: 9
visit node: 8
visit node: 1
visit node: 10
visit node: 12
visit node: 2
visit node: 3
visit node: 4
visit node: 7
visit node: 11
visit node: 6
visit node: 50 giống như ví dụ DFS.