Tanya Jawab dari wawancara kerja: algoritma di Java, bagian 2

Ini adalah bagian kedua dari gambaran singkat tentang algoritma. Berikut tautan ke artikel pertama . Sebelumnya kita melihat berbagai algoritma untuk mengurutkan array serta apa yang disebut algoritma serakah. Hari ini kita akan berbicara tentang grafik dan algoritma yang terkait dengannya. Grafik adalah salah satu struktur paling fleksibel dan serbaguna dalam pemrograman. Graf G biasanya didefinisikan oleh sepasang himpunan, yaitu G = (V, R), dimana:

• V adalah himpunan simpul;
• R adalah himpunan garis yang menghubungkan pasangan simpul.

Garis penghubung tidak berarah disebut rusuk: Garis berarah disebut busur: Biasanya, suatu graf direpresentasikan dengan diagram yang beberapa simpulnya dihubungkan oleh rusuk (busur). Grafik yang ujung-ujungnya menunjukkan arah traversal disebut grafik berarah. Jika suatu graf dihubungkan oleh sisi-sisi yang tidak menunjukkan arah traversal, maka graf tersebut dikatakan graf tak berarah. Artinya, pergerakan dapat terjadi dalam dua arah: baik dari titik A ke titik B, maupun dari titik B ke titik A. Graf terhubung adalah graf yang paling sedikit terdapat satu jalur yang mengarah dari setiap titik ke titik lainnya (seperti pada contoh di atas). Jika tidak demikian, maka graf tersebut dikatakan tidak terhubung: Bobot juga dapat diberikan pada sisi-sisinya (busur). Bobot adalah angka yang mewakili, misalnya, jarak fisik antara dua simpul (atau waktu tempuh relatif antara dua simpul). Grafik ini disebut grafik berbobot:

3. Algoritma pathfinding (kedalaman-pertama, keluasan-pertama)

Salah satu operasi dasar yang dilakukan dengan graf adalah menentukan semua simpul yang dapat dijangkau dari suatu simpul tertentu. Bayangkan Anda mencoba menentukan bagaimana Anda bisa naik bus dari satu kota ke kota lain, termasuk kemungkinan transfernya. Ada kota yang bisa dijangkau secara langsung, ada pula yang hanya bisa dicapai dengan melewati kota lain. Ada banyak situasi lain di mana Anda mungkin perlu menemukan semua simpul yang dapat Anda jangkau dari suatu simpul tertentu. Ada dua cara utama untuk melintasi grafik: kedalaman-pertama dan lebar-pertama. Kami akan mengeksplorasi keduanya. Kedua metode melintasi semua simpul yang terhubung. Untuk mengeksplorasi lebih jauh algoritma depth-first dan breadth-first, kita akan menggunakan grafik berikut:

Pencarian mendalam pertama

Ini adalah salah satu metode traversal grafik yang paling umum. Strategi depth-first adalah mempelajari grafik sedalam mungkin. Kemudian setelah mencapai jalan buntu, kita kembali ke simpul terdekat yang sebelumnya belum dikunjungi simpul-simpul bertetangga. Algoritma ini menyimpan informasi pada tumpukan tentang ke mana harus kembali ketika jalan buntu tercapai. Aturan untuk pencarian mendalam pertama:

1. Kunjungi titik berdekatan yang belum pernah dikunjungi sebelumnya, tandai sebagai telah dikunjungi, dan dorong ke dalam tumpukan.
2. Pindah ke titik ini.
3. Ulangi langkah 1.
4. Jika langkah 1 tidak memungkinkan, kembalilah ke simpul sebelumnya dan coba lakukan langkah 1. Jika tidak memungkinkan, maka kembalilah ke simpul sebelumnya, dan seterusnya, hingga kita menemukan simpul yang dapat kita lanjutkan traversalnya.
5. Lanjutkan sampai semua simpul berada di tumpukan.

Mari kita lihat seperti apa kode Java untuk algoritma ini:

public class Graph {
  private final int MAX_VERTS = 10;
  private Vertex vertexArray[]; // Array of vertices
  private int adjMat[][]; // Adjacency matrix
  private int nVerts; // Current number of vertices
  private Stack stack;

  public Graph() { // Initialize internal fields
     vertexArray = new Vertex[MAX_VERTS];
     adjMat = new int[MAX_VERTS][MAX_VERTS];
     nVerts = 0;
     for (int j = 0; j < MAX_VERTS; j++) {
        for (int k = 0; k < MAX_VERTS; k++) {
           adjMat[j][k] = 0;
        }
     }
     stack = new Stack<>();
  }

  public void addVertex(char lab) {
     vertexArray[nVerts++] = new Vertex(lab);
  }

  public void addEdge(int start, int end) {
     adjMat[start][end] = 1;
     adjMat[end][start] = 1;
  }

  public void displayVertex(int v) {
     System.out.println(vertexArray[v].getLabel());
  }

  public void dfs() { // Depth-first search
     vertexArray[0].setVisited(true); // Take the first vertex
     displayVertex(0);
     stack.push(0);

     while (!stack.empty()) {
        int v = getAdjUnvisitedVertex(stack.peek()); // Return the index of the adjacent vertex: if any, 1; if not, -1
        if (v == -1) { // If there is no unvisited adjacent vertex
           stack.pop(); // The element is removed from the stack
        }
        else {
           vertexArray[v].setVisited(true);
           displayVertex(v);
           stack.push(v); // The element goes on top of the stack
        }
     }

     for (int j = 0; j < nVerts; j++) {  // Reset the flags
        vertexArray[j].visited = false;
     }

  }

  private int getAdjUnvisitedVertex(int v) {
     for (int j = 0; j < nVerts; j++) {
        if (adjMat[v][j] == 1 && vertexArray[j].visited == false) {
           return j; // Returns the first vertex found
        }
     }
     return -1;
  }
}

Sebuah simpul terlihat seperti ini:

public class Vertex {
  private char label;  // for example, 'A'
  public boolean visited;

  public Vertex(final char label) {
     this.label = label;
     visited = false;
  }

  public char getLabel() {
     return this.label;
  }

  public boolean isVisited() {
     return this.visited;
  }

  public void setVisited(final boolean visited) {
     this.visited = visited;
  }
}

Mari kita jalankan algoritme ini dengan simpul tertentu dan lihat apakah algoritme berfungsi dengan benar:

public class Solution {
  public static void main(String[] args) {
     Graph graph = new Graph();
     graph.addVertex('A'); //0
     graph.addVertex('B'); //1
     graph.addVertex('C'); //2
     graph.addVertex('D'); //3
     graph.addVertex('E'); //4
     graph.addVertex('F'); //5
     graph.addVertex('G'); //6

     graph.addEdge(0,1);
     graph.addEdge(0,2);
     graph.addEdge(0,3);
     graph.addEdge(1,4);
     graph.addEdge(3,5);
     graph.addEdge(5,6);

     System.out.println("Visits: ");
     graph.dfs();
  }
}

Keluaran konsol: Karena kita memiliki matriks ketetanggaan dan menggunakan perulangan di dalam perulangan, kompleksitas waktunya adalah O(N²).

Pencarian yang mengutamakan luas

Seperti pencarian depth-first, algoritma ini adalah salah satu metode traversal grafik yang paling sederhana dan mendasar. Intinya adalah kita memiliki beberapa titik saat ini. Kami menempatkan semua simpul tetangga yang belum dikunjungi ke dalam antrian dan memilih elemen berikutnya (yang merupakan simpul yang disimpan di kepala antrian), yang menjadi simpul saat ini… Memecah algoritma ini menjadi beberapa tahap, kita dapat mengidentifikasi langkah-langkah berikut:

1. Kunjungi simpul berikutnya yang belum dikunjungi sebelumnya yang berdekatan dengan simpul saat ini, tandai simpul tersebut sebagai telah dikunjungi terlebih dahulu, dan tambahkan ke antrian.
2. Jika langkah #1 tidak dapat dilakukan, hapus simpul tersebut dari antrian dan jadikan simpul tersebut sebagai simpul saat ini.
3. Jika langkah #1 dan #2 tidak dapat dilakukan, maka kita selesai melakukan traversing - setiap titik telah dilintasi (jika kita mempunyai graf terhubung).

Kelas grafik di sini hampir identik dengan yang kami gunakan untuk algoritma pencarian depth-first, kecuali untuk metode pencarian itu sendiri dan fakta bahwa antrian menggantikan tumpukan internal:

public class Graph {
  private final int MAX_VERTS = 10;
  private Vertex vertexList[]; // Array of vertices
  private int adjMat[][]; // Adjacency matrix
  private int nVerts; // Current number of vertices
  private Queue queue;

  public Graph() {
     vertexList = new Vertex[MAX_VERTS];
     adjMat = new int[MAX_VERTS][MAX_VERTS];
     nVerts = 0;
     for (int j = 0; j < MAX_VERTS; j++) {
        for (int k = 0; k < MAX_VERTS; k++) {  // Fill the adjacency matrix with zeros
           adjMat[j][k] = 0;
        }
     }
     queue = new PriorityQueue<>();
  }

  public void addVertex(char lab) {
     vertexList[nVerts++] = new Vertex(lab);
  }

  public void addEdge(int start, int end) {
     adjMat[start][end] = 1;
     adjMat[end][start] = 1;
  }

  public void displayVertex(int v) {
     System.out.println(vertexList[v].getLabel());
  }

  public void bfc() { // Depth-first search
     vertexList[0].setVisited(true);
     displayVertex(0);
     queue.add(0);
     int v2;

     while (!queue.isEmpty()) {
        int v = queue.remove();

        while((v2 = getAdjUnvisitedVertex(v))!=-1) {// The loop runs until every adjacent vertex is found and added to the queue
           vertexList[v2].visited = true;
           displayVertex(v2);
           queue.add(v2);
        }
     }

     for (int j = 0; j < nVerts; j++) {  // Reset the flags
        vertexList[j].visited = false;
     }

  }

  private int getAdjUnvisitedVertex(int v) {
     for (int j = 0; j < nVerts; j++) {
        if (adjMat[v][j] == 1 && vertexList[j].visited == false) {
           return j; // Returns the first vertext found
        }
     }
     return -1;
  }
}

Kelas Vertex identik dengan yang kami gunakan dengan algoritma pencarian mendalam pertama. Mari kita terapkan algoritma ini:

public class Solution {
  public static void main(String[] args) {
     Graph graph = new Graph();
     graph.addVertex('A'); //0
     graph.addVertex('B'); //1
     graph.addVertex('C'); //2
     graph.addVertex('D'); //3
     graph.addVertex('E'); //4
     graph.addVertex('F'); //5
     graph.addVertex('G'); //6

     graph.addEdge(0,1);
     graph.addEdge(0,2);
     graph.addEdge(0,3);
     graph.addEdge(1,4);
     graph.addEdge(3,5);
     graph.addEdge(5,6);

     System.out.println("Visits: ");
     graph.bfc();
  }
}

Keluaran konsol: Sekali lagi: kita memiliki matriks ketetanggaan dan menggunakan loop yang disarangkan dalam satu loop, sehingga kompleksitas waktu dari algoritma di atas adalah O(N²).

4. Algoritma Dijkstra

Seperti yang telah disebutkan sebelumnya, grafik dapat berarah atau tidak berarah. Dan Anda akan ingat bahwa mereka juga dapat ditimbang. Grafik berarah dan berbobot memodelkan hubungan yang sering ditemukan dalam kehidupan nyata: misalnya, peta kota yang kota-kotanya merupakan simpul, dan sisi-sisi di antara keduanya adalah jalan dengan lalu lintas satu arah, mengalir ke arah tepi yang diarahkan. Katakanlah Anda adalah perusahaan angkutan barang dan Anda perlu menemukan rute terpendek antara dua kota yang berjauhan. Bagaimana Anda melakukannya? Menemukan jalur terpendek antara dua simpul adalah salah satu masalah paling umum yang diselesaikan dengan menggunakan grafik berbobot. Untuk mengatasi permasalahan tersebut digunakan algoritma Dijkstra. Setelah Anda menjalankannya, Anda akan mengetahui jalur terpendek dari titik awal tertentu ke titik lainnya. Apa langkah-langkah algoritma ini? Saya akan mencoba menjawab pertanyaan ini. Langkah-langkah algoritma Dijkstra:

• Langkah 1: Temukan node berdekatan yang memiliki biaya navigasi terendah (bobot tepi terendah). Anda berdiri di awal dan memikirkan ke mana harus pergi: ke node A atau node B. Berapa biaya untuk berpindah ke masing-masing node ini?
• Langkah 2: hitung jarak yang harus ditempuh ke semua tetangga node В yang belum dikunjungi oleh algoritma saat melintasi tepi dari В. Jika jarak baru lebih kecil dari jarak lama, maka jalur yang melalui sisi B menjadi jalur terpendek baru untuk titik tersebut.
• Langkah 3: tandai simpul B sebagai telah dikunjungi.
• Langkah 4: Lanjutkan ke langkah 1.

Kami akan mengulangi langkah-langkah ini dalam satu lingkaran sampai semua simpul telah dikunjungi. Mari kita perhatikan graf berarah berbobot berikut ini: Dengan menggunakan algoritma di atas, kita akan menentukan jalur terpendek dari A ke G:

1. Ada tiga kemungkinan jalur untuk simpul A: ke B dengan bobot 3, ke C dengan bobot 5, dan ke D dengan bobot 7. Berdasarkan langkah pertama algoritme, kita memilih simpul dengan biaya terendah (bobot tepi). Dalam hal ini,B.

2. Karena satu-satunya tetangga B yang belum dikunjungi adalah simpul Е, kita periksa jalur apa yang akan kita ambil jika kita melewati simpul ini. 3(AB) + 6(BE) = 9.

   Jadi, kita catat bahwa jalur terpendek saat ini dari A ke E adalah 9.

3. Karena pekerjaan kita dengan simpul B selesai, kita lanjutkan dengan memilih simpul berikutnya yang rusuknya mempunyai bobot minimum.

   Dari simpul A dan B, kemungkinannya adalah simpul D (7), C (5), atau E (6).

   Sisi ke С memiliki bobot paling kecil, jadi kita menuju ke titik ini.

4. Selanjutnya, seperti sebelumnya, kita mencari jalur terpendek ke simpul tetangga ketika melewati C:

   • AD = 5 (AC) + 3 (CD) = 8, tetapi karena jalur terpendek sebelumnya (AC = 7) lebih kecil dari jalur ini yang melalui С, kami mempertahankan jalur terpendek (AC = 7) tidak berubah.

   • CE = 5(AC) + 4(CE) = 9. Jalur terpendek baru ini sama dengan jalur sebelumnya, jadi kita biarkan juga tidak berubah.

5. Dari simpul-simpul terdekat yang dapat diakses (E dan D), pilih simpul yang mempunyai bobot sisi terkecil, yaitu D (3).

6. Kami menemukan jalur terpendek ke tetangganya F.

   AF = 7(IKLAN) + 3(DF) = 9

7. Dari simpul-simpul terdekat yang dapat diakses (E dan F), pilih simpul yang mempunyai bobot sisi terkecil, yaitu F (3).

8. Temukan jalur terpendek ke tetangganya G.

   AG = 7(AD) + 3(DF) + 4(FG) = 14

   Jadi, kami telah menemukan jalur dari A ke G.

   Namun untuk memastikannya terpendek, kita juga harus melakukan langkah kita pada titik E.

9. Karena simpul G tidak mempunyai simpul tetangga yang ditunjuk oleh sisi berarah, kita hanya mempunyai simpul E yang tersisa, jadi kita memilihnya.

10. Temukan jalur terpendek ke tetangga G.

    AG = 3 (AB) + 6 (BE) + 6 (EG) = 15. Jalur ini lebih panjang dari jalur terpendek sebelumnya (AG (14)), jadi jalur ini kita biarkan tidak berubah.

    Karena tidak ada simpul yang mengarah dari G, maka tidak masuk akal untuk menjalankan langkah-langkah algoritma pada simpul ini. Artinya, pekerjaan algoritma telah selesai.

Seperti yang saya katakan tadi, selain mencari jalur terpendek untuk AG, kita juga memperoleh jalur terpendek dari simpul A ke setiap simpul lainnya (AB, AC, AD, AE, AF). Nah, sekarang saatnya melihat bagaimana hal ini bisa dilakukan di Java. Mari kita mulai dengan kelas vertex:

public class Vertex {
   private char label;
   private boolean isInTree;

   public Vertex(char label) {
       this.label = label;
       this.isInTree = false;
   }

   public char getLabel() {
       return label;
   }

   public void setLabel(char label) {
       this.label = label;
   }

   public boolean isInTree() {
       return isInTree;
   }

   public void setInTree(boolean inTree) {
       isInTree = inTree;
   }
}

Kelas simpul sebenarnya identik dengan kelas simpul yang digunakan untuk pencarian luas pertama. Untuk menampilkan jalur terpendek, kita memerlukan kelas baru yang berisi data yang kita perlukan:

public class Path { // A class that contains the distance and the previous and traversed vertices
   private int distance; // Current distance from the starting vertex
   private List parentVertices; // Current parent vertex

   public Path(int distance) {
       this.distance = distance;
       this.parentVertices = new ArrayList<>();
   }

   public int getDistance() {
       return distance;
   }

   public void setDistance(int distance) {
       this.distance = distance;
   }

   public List getParentVertices() {
       return parentVertices;
   }

   public void setParentVertices(List parentVertices) {
       this.parentVertices = parentVertices;
   }
}

Pada kelas ini kita dapat melihat total jarak lintasan dan simpul yang akan dilalui ketika melewati lintasan terpendek. Dan sekarang mari kita lihat kelas di mana kita melintasi jalur terpendek melalui grafik. Jadi di sini kita memiliki kelas Graph:

public class Graph {
   private final int MAX_VERTS = 10;// Maximum number of vertices
   private final int INFINITY = 100000000; // This number represents infinity
   private Vertex vertexList[]; // List of vertices
   private int relationMatrix[][]; // Matrix of edges between vertices
   private int numberOfVertices; // Current number of vertices
   private int numberOfVerticesInTree; // Number of visited vertices in the tree
   private List shortestPaths; // List of shortest paths
   private int currentVertex; // Current vertex
   private int startToCurrent; // Distance to currentVertex

   public Graph() {
       vertexList = new Vertex[MAX_VERTS]; // Adjacency matrix
       relationMatrix = new int[MAX_VERTS][MAX_VERTS];
       numberOfVertices = 0;
       numberOfVerticesInTree = 0;
       for (int i = 0; i < MAX_VERTS; i++) { // Fill the adjacency matrix
           for (int k = 0; k < MAX_VERTS; k++) { // with "infinity"
               relationMatrix[i][k] = INFINITY; // Assign default values
               shortestPaths = new ArrayList<>(); // Assign an empty list
           }
       }
   }

   public void addVertex(char lab) {// Assign new vertices
       vertexList[numberOfVertices++] = new Vertex(lab);
   }

   public void addEdge(int start, int end, int weight) {
       relationMatrix[start][end] = weight; // Set weighted edges between vertices
   }

   public void path() { // Choose the shortest path
       // Set the initial vertex data
       int startTree = 0; // Start from vertex 0
       vertexList[startTree].setInTree(true); // Include the first element in the tree
       numberOfVerticesInTree = 1;

       // Fill out the shortest paths for vertices adjacent to the initial vertex
       for (int i = 0; i < numberOfVertices; i++) {
           int tempDist = relationMatrix[startTree][i];
           Path path = new Path(tempDist);
           path.getParentVertices().add(0);// The starting vertex will always be a parent vertex
           shortestPaths.add(path);
       }
       // Until every vertex is in the tree
       while (numberOfVerticesInTree < numberOfVertices) { // Do this until the number of of vertices in the tree equals the total number of vertices
           int indexMin = getMin();// Get the index of the of the vertex with the smallest distance from the vertices not yet in the tree
           int minDist = shortestPaths.get(indexMin).getDistance(); // Minimum distance to the vertices not yet in the tree

           if (minDist == INFINITY) {
               System.out.println("The graph has an unreachable vertex");
               break; // If only unreachable vertices have not been visited, then we exit the loop
           } else {
               currentVertex = indexMin; // Set currentVert to the index of the current vertex
               startToCurrent = shortestPaths.get(indexMin).getDistance(); // Set the distance to the current vertex
           }

           vertexList[currentVertex].setInTree(true);  // Add the current vertex to the tree
           numberOfVerticesInTree++; // Increase the count of vertices in the tree
           updateShortestPaths(); // Update the list of shortest paths
       }

       displayPaths(); // Display the results on the console
   }

   public void clear() { // Clear the tree
       numberOfVerticesInTree = 0;
       for (int i = 0; i < numberOfVertices; i++) {
           vertexList[i].setInTree(false);
       }
   }

   private int getMin() {
       int minDist = INFINITY; // The distance of the initial shortest path is taken to be infinite
       int indexMin = 0;
       for (int i = 1; i < numberOfVertices; i++) { // For each vertex
           if (!vertexList[i].isInTree() && shortestPaths.get(i).getDistance() < minDist) { // If the vertex is not yet in the tree and the distance to the vertex is less than the current minimum
               minDist = shortestPaths.get(i).getDistance(); // then update the minimum
               indexMin = i; // Update the index of the vertex with the minimum distance
           }
       }
       return indexMin; // Returns the index of the vertex with the smallest distance among those not yet in the tree
   }

   private void updateShortestPaths() {
       int vertexIndex = 1; // The initial vertex is skipped
       while (vertexIndex < numberOfVertices) { // Run over the columns

           if (vertexList[vertexIndex].isInTree()) { // If the column vertex is already in the tree, then we skip it
               vertexIndex++;
               continue;
           }
           // Calculate the distance for one element sPath
           // Get the edge from currentVert to column
           int currentToFringe = relationMatrix[currentVertex][vertexIndex];
           // Add up all the distances
           int startToFringe = startToCurrent + currentToFringe;
           // Determine the distance to the current vertexIndex
           int shortPathDistance = shortestPaths.get(vertexIndex).getDistance();

           // Compare the distance through currentVertex with the current distance in the vertex with index vertexIndex
           if (startToFringe < shortPathDistance) { // If it is smaller, then the vertex at vertexIndex is assigned the new shortest path
               List newParents = new ArrayList<>(shortestPaths.get(currentVertex).getParentVertices()); // Create a copy of the list of vertices of vertex currentVert's parents
               newParents.add(currentVertex); // And add currentVertex to it as the previous vertex
               shortestPaths.get(vertexIndex).setParentVertices(newParents); // Save the new path
               shortestPaths.get(vertexIndex).setDistance(startToFringe); // Save the new distance
           }
           vertexIndex++;
       }
   }

   private void displayPaths() { // A method for displaying the shortest paths on the screen
       for (int i = 0; i < numberOfVertices; i++) {
           System.out.print(vertexList[i].getLabel() + " = ");
           if (shortestPaths.get(i).getDistance() == INFINITY) {
               System.out.println("0");
           } else {
               String result = shortestPaths.get(i).getDistance() + " (";
               List parents = shortestPaths.get(i).getParentVertices();
               for (int j = 0; j < parents.size(); j++) {
                   result += vertexList[parents.get(j)].getLabel() + " -> ";
               }
               System.out.println(result + vertexList[i].getLabel() + ")");
           }
       }
   }
}

Jadi itu saja keajaibannya =) Sekarang, mari kita lihat cara kerja algoritma ini:

public class Solution {

   public static void main(String[] args) {
       Graph graph = new Graph();
       graph.addVertex('A');
       graph.addVertex('B');
       graph.addVertex('C');
       graph.addVertex('D');
       graph.addVertex('E');
       graph.addVertex('F');
       graph.addVertex('G');

       graph.addEdge(0, 1, 3);
       graph.addEdge(0, 2, 5);
       graph.addEdge(0, 3, 7);
       graph.addEdge(1, 4, 6);
       graph.addEdge(2, 4, 4);
       graph.addEdge(2, 3, 3);
       graph.addEdge(3, 5, 3);
       graph.addEdge(4, 6, 6);
       graph.addEdge(5, 6, 4);

       System.out.println("The following nodes form the shortest paths from node A:");
       graph.path();
       graph.clear();
   }
}

Dan keluaran konsolnya adalah ini: Kompleksitas waktu dari algoritma ini tidak lain adalah O(N²), karena kita memiliki loop bersarang. Hanya itu yang saya punya hari ini. Terima kasih atas perhatian Anda!