- V iku sawijining set saka vertex;
- R yaiku kumpulan garis sing nyambungake pasangan vertex.
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:- Dolan maring vertex jejer sing sadurunge ora dibukak, tandhani minangka dibukak, lan push menyang tumpukan.
- Pindhah menyang vertex iki.
- Baleni langkah 1.
- 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.
- Terusake nganti kabeh simpul ana ing tumpukan.
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:
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:- Dolan maring vertex sing sadurunge durung dibukak jejere vertex saiki, tandhani minangka dibukak ing advance, lan ditambahake menyang antrian.
- Yen langkah #1 ora bisa ditindakake, banjur copot vertex saka antrian lan nggawe vertex saiki.
- Yen langkah #1 lan #2 ora bisa ditindakake, mula kita wis rampung nyabrang - saben simpul wis dilewati (yen kita duwe grafik sing nyambung).
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:
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.
- 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.
-
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.
-
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.
-
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.
-
-
Saka vertex sing bisa diakses paling cedhak (E lan D), pilih vertex kanthi bobot pinggir paling cilik, yaiku D (3).
-
Kita nemokake dalan sing paling cedhak menyang tanggane F.
AF = 7(AD) + 3(DF) = 9
-
Saka vertex sing bisa diakses paling cedhak (E lan F), pilih vertex kanthi bobot pinggir paling cilik, yaiku F (3).
-
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.
-
Amarga vertex G ora duwe vertex tetanggan sing ditunjuk dening pinggiran sing diarahake, kita mung duwe vertex E kiwa, mula kita milih.
-
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.
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: