Halo sobat KonsepKoding pada artikel kali ini KonsepKoding akan berbagi tutorial mengenai Depth-First Search (DFS).

Tutorial Algoritma Depth-First Search (DFS) Javascript
Tutorial Algoritma Depth-First Search (DFS) Javascript


 Depth-First Search (DFS) adalah salah satu algoritma pencarian yang digunakan dalam pemrosesan struktur data seperti graf. Tujuan utama DFS adalah untuk menjelajahi semua simpul (node) dalam graf, terutama digunakan untuk graf yang tidak memiliki sifat siklik. Algoritma ini berguna dalam berbagai konteks, termasuk pencarian jalur, analisis grafik, dan pemecahan masalah lain yang melibatkan eksplorasi struktur yang terhubung.


Cara kerja Depth-First Search (DFS):

  1. Memulai dengan simpul awal (biasanya disebut sebagai "simpul awal" atau "simpul sumber").
  2. Tandai simpul tersebut sebagai "dikunjungi" agar tidak dikunjungi lagi.
  3. Jelajahi semua tetangga yang belum dikunjungi dari simpul tersebut. Pilih satu tetangga yang belum dikunjungi.
  4. Lakukan DFS rekursif pada tetangga yang belum dikunjungi tersebut.
  5. Ulangi langkah 3 dan 4 sampai tidak ada tetangga yang belum dikunjungi lagi.
  6. Kembali ke simpul sebelumnya (lewat rekursi atau dengan mengembalikan tumpukan), lalu lanjutkan ke tetangga lain yang belum dikunjungi jika ada.
  7. Ulangi langkah-langkah 3 hingga 6 hingga semua simpul dikunjungi.


Memulai Koding


Disini kita akan menggunakan kelas untuk membuat fiturnya, buat sebuah file dengan nama index.js

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

  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) {
      this.adjacencyList[vertex] = [];
    }
  }

  addEdge(vertex1, vertex2) {
    this.adjacencyList[vertex1].push(vertex2);
    this.adjacencyList[vertex2].push(vertex1); // for undirected graph
  }

  depthFirstSearch(startingVertex) {
    const result = [];
    const visited = {};
    const adjacencyList = this.adjacencyList;

    function dfs(vertex) {
      if (!vertex) return null;
      visited[vertex] = true;
      result.push(vertex);
      adjacencyList[vertex].forEach((neighbor) => {
        if (!visited[neighbor]) {
          return dfs(neighbor);
        }
      });
    }

    dfs(startingVertex);
    return result;
  }
}

// Contoh penggunaan
const graph = new Graph();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('B', 'D');

console.log(graph.depthFirstSearch('A')); // Output: ['A', 'B', 'D', 'C']

Sekian artikel mengenai  Tutorial Algoritma Depth-First Search (DFS) Javascript semoga artikel ini dapat bermanfaat dan membantu kamu yang sedang mempelajari Algoritma dan Struktur Data.