Pitakonan saka wawancara kerja: algoritma ing Jawa, bagean 2

Iki minangka bagean kapindho saka ringkesan algoritma. Punika pranala menyang artikel pisanan . Sadurungé kita ndeleng macem-macem algoritma kanggo ngurutake array uga algoritma sing diarani rakus. Dina iki kita bakal ngomong babagan grafik lan algoritma sing ana gandhengane. Grafik minangka salah sawijining struktur sing paling fleksibel lan serbaguna ing pemrograman. Grafik G biasane ditemtokake dening pasangan set, yaiku G = (V, R), ing ngendi:

• V iku sawijining set saka vertex;
• R yaiku kumpulan garis sing nyambungake pasangan vertex.

Garis panyambung sing ora diarahake diarani pinggiran: Garis sing diarahake diarani busur: Biasane, grafik diwakili dening diagram sing sawetara simpul disambungake kanthi pinggiran (busur). Grafik sing pinggiran nuduhake arah traversal diarani grafik terarah. Yen grafik disambungake dening pinggiran sing ora nuduhake arah traversal, banjur kita ngomong iku graph undirected. Iki tegese gerakan bisa ing loro arah: loro saka vertex A kanggo vertex B, lan saka vertex B kanggo vertex A. Grafik sing disambungake yaiku grafik sing paling ora siji path ndadékaké saka saben vertex menyang vertex liyane (kaya ing conto ing ndhuwur). Yen iki ora cilik, banjur graph ngandika pedhot: Bobot uga bisa diutus kanggo sudhut (busur). Bobot minangka angka sing makili, contone, jarak fisik antarane rong vertex (utawa wektu lelungan relatif antarane rong vertex). Grafik kasebut diarani grafik bobot:

3. Algoritma Pathfinding (depth-first, breadth-first)

Salah sawijining operasi dhasar sing ditindakake kanthi grafik yaiku nemtokake kabeh verteks sing bisa digayuh saka vertex tartamtu. Mbayangno sing nyoba kanggo nemtokake carane sampeyan bisa numpak bis saka siji kutha menyang liyane, kalebu transfer bisa. Sawetara kutha bisa ditekani kanthi langsung, nanging sawetara mung bisa digayuh liwat kutha liyane. Ana akeh kahanan liyane ing ngendi sampeyan bisa uga kudu nemokake kabeh vertex sing bisa tekan saka vertex tartamtu. Ana rong cara utama kanggo ngliwati grafik: depth-first lan breadth-first. Kita bakal njelajah loro iki. Loro-lorone cara ngliwati kabeh simpul sing disambungake. Kanggo luwih njelajah algoritma depth-first lan breadth-first, kita bakal nggunakake grafik ing ngisor iki:

Panelusuran paling jero

Iki minangka salah sawijining metode traversal grafik sing paling umum. Strategi depth-first yaiku nggawe grafik sing paling jero. Banjur sawise tekan buntu, kita bali menyang verteks paling cedhak sing sadurunge ora ditekani vertex jejer. Algoritma iki nyimpen informasi ing tumpukan babagan ngendi arep bali nalika buntu wis tekan. Aturan kanggo nggoleki depth-first:

1. Dolan maring vertex jejer sing sadurunge ora dibukak, tandhani minangka dibukak, lan push menyang tumpukan.
2. Pindhah menyang vertex iki.
3. Baleni langkah 1.
4. Yen langkah 1 ora mungkin, bali menyang vertex sadurunge lan coba tindakake langkah 1. Yen ora bisa, bali menyang vertex sadurunge, lan sateruse, nganti kita nemokake vertex saka ngendi kita bisa nerusake traversal.
5. Terusake nganti kabeh simpul ana ing tumpukan.

Ayo goleki kaya apa kode Java kanggo algoritma iki:

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;
  }
}

A vertex katon kaya iki:

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;
  }
}

Ayo mbukak algoritma iki kanthi simpul tartamtu lan deleng yen bisa digunakake kanthi bener:

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();
  }
}

Output konsol: Amarga kita duwe matriks adjacency lan nggunakake loop ing loop, kerumitan wektu bakal dadi O(N²).

Breadth-first search

Kaya depth-first search, algoritma iki minangka salah sawijining metode traversal grafik sing paling gampang lan paling dhasar. Intine yaiku kita duwe sawetara vertex saiki. Kita sijine kabeh vertex jejer sing ora dibukak menyang antrian lan pilih unsur sabanjuré (yaiku vertex sing disimpen ing sirah antrian), kang dadi vertex saiki… Breaking algoritma iki menyang orane tumrap sekolah, kita bisa ngenali langkah ing ngisor iki:

1. Dolan maring vertex sing sadurunge durung dibukak jejere vertex saiki, tandhani minangka dibukak ing advance, lan ditambahake menyang antrian.
2. Yen langkah #1 ora bisa ditindakake, banjur copot vertex saka antrian lan nggawe vertex saiki.
3. Yen langkah #1 lan #2 ora bisa ditindakake, mula kita wis rampung nyabrang - saben simpul wis dilewati (yen kita duwe grafik sing nyambung).

Kelas grafik ing kene meh padha karo sing digunakake kanggo algoritma telusuran sing paling jero, kajaba metode telusuran dhewe lan kasunyatan manawa antrian ngganti 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 karo sing digunakake karo algoritma telusuran sing paling jero. Ayo tumindak algoritma iki:

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();
  }
}

Output konsol: Maneh: kita duwe matriks adjacency lan nggunakake loop nested ing loop, supaya kerumitan wektu saka algoritma ndhuwur iku O(N²).

4. Algoritma Dijkstra

Kaya sing wis kasebut sadurunge, grafik bisa diarahake utawa ora diarahake. Lan sampeyan bakal kelingan sing padha uga bisa bobot. Diboboti, diarahake graphs sesambetan model asring ditemokaké ing urip nyata: contone, peta kutha ngendi kutha-kutha vertex, lan pinggiran antarane wong-wong mau dalan karo lalu lintas siji-arah, mili menyang arah pinggiran diarahake. Contone, sampeyan minangka perusahaan kargo lan sampeyan kudu nemokake rute paling cedhak ing antarane rong kutha sing adoh. Kepiye carane sampeyan nindakake? Nemokake jalur paling cedhak ing antarane rong simpul minangka salah sawijining masalah sing paling umum ditanggulangi kanthi nggunakake grafik bobot. Kanggo ngatasi masalah iki, kita nggunakake algoritma Dijkstra. Sawise sampeyan mbukak, sampeyan bakal ngerti dalan paling cendhak saka titik wiwitan sing diwenehake menyang saben liyane. Apa langkah-langkah algoritma iki? Aku bakal nyoba njawab pitakonan iki. Langkah-langkah algoritma Dijkstra:

• Langkah 1: Temokake simpul jejer sing nduweni biaya paling murah kanggo navigasi (bobot pinggiran paling murah). Sampeyan lagi ngadeg ing awal banget lan mikir bab ngendi kanggo pindhah: menyang simpul A utawa simpul B. Apa biaya obah kanggo saben kelenjar iki?
• langkah 2: ngetung kadohan kanggo lelungan kanggo kabeh tanggi simpul В kang durung dibukak dening algoritma nalika traversing pinggiran saka В. Yen jarak anyar kurang saka sing lawas, banjur dalan liwat pinggiran B dadi jalur paling cedhak anyar kanggo vertex iki.
• Langkah 3: tandhani vertex B minangka dibukak.
• Langkah 4: Pindhah menyang langkah 1.

Kita bakal mbaleni langkah-langkah iki ing daur ulang nganti kabeh vertex wis dibukak. Ayo nimbang grafik diarahake bobot ing ngisor iki: Nggunakake algoritma ing ndhuwur, kita bakal nemtokake dalan paling cedhak saka A nganti G:

1. Ana telung jalur sing bisa kanggo vertex A: menyang B kanthi bobot 3, nganti С kanthi bobot 5, lan menyang D kanthi bobot 7. Miturut langkah pisanan saka algoritma, kita milih simpul kanthi biaya paling murah (bobot pinggir). Ing kasus iki, B.

2. Wiwit pepadhamu mung B sing ora dibukak iku vertex Е, kita mriksa apa path bakal yen kita liwat vertex iki. 3(AB) + 6(BE) = 9.

   Dadi, kita nyathet yen jalur paling cedhak saiki saka A nganti E yaiku 9.

3. Wiwit karya kita karo vertex B wis rampung, kita nerusake kanggo milih vertex sabanjuré kang pinggiran bobot minimal.

   Saka simpul A lan B, kemungkinan yaiku simpul D (7), C (5), utawa E (6).

   Sisih menyang С nduweni bobot paling cilik, mula kita pindhah menyang vertex iki.

4. Sabanjure, kaya sadurunge, kita nemokake dalan paling cedhak menyang simpul tetanggan nalika ngliwati C:

   • AD = 5 (AC) + 3 (CD) = 8, nanging wiwit path paling cedhak sadurungé (AC = 7) kurang saka iki liwat С, kita tetep path paling cendhak (AC = 7) ora diganti.

   • CE = 5(AC) + 4(CE) = 9. Path paling cedhak anyar iki padha karo sadurunge, supaya kita uga ninggalake iku panggah.

5. Saka vertex sing bisa diakses paling cedhak (E lan D), pilih vertex kanthi bobot pinggir paling cilik, yaiku D (3).

6. Kita nemokake dalan sing paling cedhak menyang tanggane F.

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

7. Saka vertex sing bisa diakses paling cedhak (E lan F), pilih vertex kanthi bobot pinggir paling cilik, yaiku F (3).

8. Temokake dalan sing paling cedhak menyang tanggane G.

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

   Dadi, kita wis nemokake dalan saka A nganti G.

   Nanging kanggo mesthekake yen paling cendhak, kita uga kudu nindakake langkah-langkah ing vertex E.

9. Amarga vertex G ora duwe vertex tetanggan sing ditunjuk dening pinggiran sing diarahake, kita mung duwe vertex E kiwa, mula kita milih.

10. Temokake dalan sing paling cedhak menyang tanggane G.

    AG = 3 (AB) + 6 (BE) + 6 (EG) = 15. Path iki luwih dawa tinimbang path paling cedhak sadurungé (AG (14)), supaya kita ninggalake path iki ora diganti.

    Wiwit ora ana vertex anjog saka G, iku ndadekake ora pangertèn kanggo mbukak langkah ing algoritma ing vertex iki. Tegese karya algoritma wis rampung.

Kaya sing wis dakkandhakake sadurunge, saliyane nemokake jalur paling cedhak kanggo AG, kita uga entuk jalur paling cedhak saka vertex A menyang saben vertex liyane (AB, AC, AD, AE, AF). Nah, saiki wektune kanggo ndeleng kepiye carane iki bisa ditindakake ing basa Jawa. Ayo miwiti karo 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 vertex meh padha karo kelas vertex sing digunakake kanggo telusuran pertama. Kanggo nampilake dalan sing paling cendhak, kita butuh kelas anyar sing bakal ngemot data sing dibutuhake:

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;
   }
}

Ing kelas iki, kita bisa ndeleng total jarak dalan lan verteks sing bakal dilewati nalika ngliwati dalan sing paling cedhak. Lan saiki ayo goleki kelas ing ngendi kita bener-bener ngliwati jalur paling cendhak liwat grafik. Dadi ing kene kita duwe 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() + ")");
           }
       }
   }
}

Dadi kabeh sihir =) Saiki, ayo deleng algoritma iki ing tumindak:

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();
   }
}

Lan output konsol yaiku: Kerumitan wektu algoritma iki ora liya O(N²), amarga kita duwe puteran nested. Mung kuwi sing dakkarepake dina iki. Matur nuwun kanggo manungsa waé!