Algoritma DFS

Depth-first search (DFS) melakukan pencarian secara preorder. Mengunjungi anak suatu simpul sebelum simpul tetangganya.

Algoritma

Step 1: letakkan root parent di tempat yang paling atas

Step 2: Lakukan looping hingga titik terakhir

Step 3: letakkan titik yang terhubung dengan root parent pada satu garis lurus

Step 4: lakukan pengecekan, jika titik tidak memiliki child letakkan pada garis, pindah ke titik selanjutnya

Step 5: jika titik yang ditemui memiliki child hubungkan dengan titik sebelumnya

 pseudocode:

DFS(G,v)   ( v is the vertex where the search starts )
         Stack S := {};   ( start with an empty stack )
         for each vertex u, set visited[u] := false;
         push S, v;
         while (S is not empty) do
            u := pop S;
            if (not visited[u]) then
               visited[u] := true;
               for each unvisited neighbour w of u
                  push S, w;
            end if
         end while
      END DFS() 

Sumber : http://www.cs.toronto.edu/~heap/270F02/node36.html 

http://yufi27.wordpress.com/2009/03/29/algoritma-dfs-bfs/ 

Posted in: Algoritma