- V āļāļ·āļāđāļāļāļāļāļāļāļļāļāļĒāļāļ
- R āļāļ·āļāļāļļāļāļāļāļāđāļŠāđāļāļāļĩāđāđāļāļ·āđāļāļĄāļāđāļāļāļđāđāļāļāļāļāļļāļāļĒāļāļ
3. āļāļąāļĨāļāļāļĢāļīāļāļķāļĄāļāļēāļĢāļāđāļāļŦāļēāđāļŠāđāļāļāļēāļ (āđāļāđāļāđāļāļīāļāļĨāļķāļ āđāļāđāļāļāļ§āđāļēāļāļāđāļāļ)
āļāļēāļĢāļāļģāđāļāļīāļāļāļēāļĢāļāļ·āđāļāļāļēāļāļāļĢāļ°āļāļēāļĢāļŦāļāļķāđāļāļāļĩāđāļāļģāđāļāļīāļāļāļēāļĢāļāļąāļāļāļĢāļēāļāļāļ·āļāļāļēāļĢāļāļģāļŦāļāļāļāļļāļāļĒāļāļāļāļąāđāļāļŦāļĄāļāļāļĩāđāļŠāļēāļĄāļēāļĢāļāđāļāđāļēāļāļķāļāđāļāđāļāļēāļāļāļļāļāļĒāļāļāļāļĩāđāļāļģāļŦāļāļ āļĨāļāļāļāļķāļāļ āļēāļāļ§āđāļēāļāļļāļāļāļģāļĨāļąāļāļāļĒāļēāļĒāļēāļĄāļāļīāļāļēāļĢāļāļēāļ§āđāļēāļāļ°āļāļąāđāļāļĢāļāļāļąāļŠāļāļēāļāđāļĄāļ·āļāļāļŦāļāļķāđāļāđāļāļĒāļąāļāļāļĩāļāđāļĄāļ·āļāļāļŦāļāļķāđāļāđāļāđāļāļĒāđāļēāļāđāļĢ āļĢāļ§āļĄāļāļķāļāļāļēāļĢāđāļāļīāļāļāļēāļāļāļĩāđāđāļāđāļāđāļāđāļāđāļāđāļ§āļĒ āļāļēāļāđāļĄāļ·āļāļāļŠāļēāļĄāļēāļĢāļāđāļāđāļēāļāļķāļāđāļāđāđāļāļĒāļāļĢāļ āđāļāļāļāļ°āļāļĩāđāļāļēāļāđāļĄāļ·āļāļāļŠāļēāļĄāļēāļĢāļāđāļāđāļēāļāļķāļāđāļāđāđāļāļĒāļāđāļēāļāđāļĄāļ·āļāļāļāļ·āđāļāđāļāđāļēāļāļąāđāļ āļĄāļĩāļŠāļāļēāļāļāļēāļĢāļāđāļāļ·āđāļāđ āļĄāļēāļāļĄāļēāļĒāļāļĩāđāļāļļāļāļāļēāļāļāđāļāļāļāđāļāļŦāļēāļāļļāļāļĒāļāļāļāļąāđāļāļŦāļĄāļāļāļĩāđāļāļļāļāļŠāļēāļĄāļēāļĢāļāđāļāđāļēāļāļķāļāđāļāđāļāļēāļāļāļļāļāļĒāļāļāļāļĩāđāļāļģāļŦāļāļ āļĄāļĩāļŠāļāļāļ§āļīāļāļĩāļŦāļĨāļąāļāđāļāļāļēāļĢāļŠāļģāļĢāļ§āļāļāļĢāļēāļ: āđāļāļīāļāļĨāļķāļāļĄāļēāļāđāļāļāđāļĨāļ°āļāļ§āđāļēāļāļāđāļāļ āđāļĢāļēāļāļ°āļŠāļģāļĢāļ§āļāļāļąāđāļāļŠāļāļāļŠāļīāđāļāļāļĩāđ āļāļąāđāļāļŠāļāļāļ§āļīāļāļĩāļāļ°āļŠāļģāļĢāļ§āļāļāļļāļāļĒāļāļāļāļĩāđāđāļāļ·āđāļāļĄāļāđāļāļāļąāļāļāļąāđāļāļŦāļĄāļ āļŦāļēāļāļāđāļāļāļāļēāļĢāļŠāļģāļĢāļ§āļāļāļąāļĨāļāļāļĢāļīāļāļķāļĄāļāļĩāđāđāļāđāļāđāļāļīāļāļĨāļķāļāđāļĨāļ°āļāļ§āđāļēāļāļāđāļāļāđāļāļīāđāļĄāđāļāļīāļĄ āđāļĢāļēāļāļ°āđāļāđāļāļĢāļēāļāļāđāļāđāļāļāļĩāđ:āļāļēāļĢāļāđāļāļŦāļēāđāļāļīāļāļĨāļķāļāļāđāļāļ
āļāļĩāđāđāļāđāļāļŦāļāļķāđāļāđāļāļ§āļīāļāļĩāļāļēāļĢāļāđāļēāļĄāļāļĢāļēāļāļāļĩāđāđāļāđāļāļąāļāļāļąāđāļ§āđāļ āļāļĨāļĒāļļāļāļāđāļāļĩāđāđāļāđāļāļāļ§āļēāļĄāļĨāļķāļāđāļāđāļāļāļąāļāļāļąāļāđāļĢāļāļāļ·āļāļāļēāļĢāđāļāļēāļ°āļāļĢāļēāļāđāļŦāđāļĨāļķāļāļāļĩāđāļŠāļļāļāđāļāđāļēāļāļĩāđāļāļ°āđāļāđāļāđāļāđāļāđ āļāļēāļāļāļąāđāļāļŦāļĨāļąāļāļāļēāļāļāļķāļāļāļēāļāļāļąāļāđāļĨāđāļ§ āđāļĢāļēāļāļ°āļāļĨāļąāļāđāļāļĒāļąāļāļāļļāļāļĒāļāļāļāļĩāđāđāļāļĨāđāļāļĩāđāļŠāļļāļāļāļķāđāļāļāđāļāļāļŦāļāđāļēāļāļĩāđāđāļĄāđāļĄāļĩāļāļļāļāļĒāļāļāļāļĩāđāļāļĒāļđāđāļāļīāļāļāļąāļ āļāļąāļĨāļāļāļĢāļīāļāļķāļĄāļāļĩāđāļāļąāļāđāļāđāļāļāđāļāļĄāļđāļĨāļāļāļŠāđāļāđāļāđāļāļĩāđāļĒāļ§āļāļąāļāļāļģāđāļŦāļāđāļāļāļĩāđāļāļ°āļŠāđāļāļāļ·āļāđāļĄāļ·āđāļāļāļķāļāļāļļāļāļŠāļīāđāļāļŠāļļāļ āļāļāļŠāļģāļŦāļĢāļąāļāļāļēāļĢāļāđāļāļŦāļēāđāļāļīāļāļĨāļķāļāļāđāļāļ:- āđāļĒāļĩāđāļĒāļĄāļāļĄāļāļļāļāļĒāļāļāļāļĩāđāļāļĒāļđāđāļāļīāļāļāļąāļāļāļķāđāļāđāļĄāđāđāļāđāđāļĒāļĩāđāļĒāļĄāļāļĄāļāđāļāļāļŦāļāđāļēāļāļĩāđ āļāļģāđāļāļĢāļ·āđāļāļāļŦāļĄāļēāļĒāļ§āđāļēāđāļĒāļĩāđāļĒāļĄāļāļĄāđāļĨāđāļ§ āđāļĨāļ°āļ§āļēāļāļĨāļāļāļāļŠāđāļāđāļ
- āļĒāđāļēāļĒāđāļāļāļĩāđāļāļļāļāļĒāļāļāļāļĩāđ
- āļāļģāļāđāļģāļāļąāđāļāļāļāļāļāļĩāđ 1
- āļŦāļēāļāļāļąāđāļāļāļāļāļāļĩāđ 1 āđāļāđāļāđāļāđāļĄāđāđāļāđ āđāļŦāđāļāļĨāļąāļāđāļāļāļĩāđāļāļļāļāļĒāļāļāļāđāļāļāļŦāļāđāļēāđāļĨāđāļ§āļĨāļāļāļāļģāļāļēāļĄāļāļąāđāļāļāļāļāļāļĩāđ 1 āļŦāļēāļāđāļāđāļāđāļāđāļĄāđāđāļāđ āđāļŦāđāļāļĨāļąāļāđāļāļāļĩāđāļāļļāļāļĒāļāļāļāđāļāļāļŦāļāđāļēāļāļąāđāļāđāļĨāļ°āļāđāļāđāļāđāļĢāļ·āđāļāļĒāđ āļāļāļāļ§āđāļēāđāļĢāļēāļāļ°āļāļāļāļļāļāļĒāļāļāļāļĩāđāđāļĢāļēāļŠāļēāļĄāļēāļĢāļāđāļāļīāļāļāļēāļāļāđāļāđāļāđ
- āļāļģāļāđāļāđāļāļāļāļāļ§āđāļēāļāļļāļāļĒāļāļāļāļąāđāļāļŦāļĄāļāļāļ°āļāļĒāļđāđāļāļāļŠāđāļāđāļ
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;
}
}
āļāļļāļāļĒāļāļāļĄāļĩāļĨāļąāļāļĐāļāļ°āļāļąāļāļāļĩāđ:
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;
}
}
āļĨāļāļāđāļāđāļāļąāļĨāļāļāļĢāļīāļāļķāļĄāļāļĩāđāļāļąāļāļāļļāļāļĒāļāļāđāļāļāļēāļ°āđāļĨāđāļ§āļāļđāļ§āđāļēāļāļģāļāļēāļāļāļđāļāļāđāļāļāļŦāļĢāļ·āļāđāļĄāđ:
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();
}
}
āđāļāļēāļāđāļāļļāļāļāļāļāđāļāļĨ:
āļāļēāļĢāļāđāļāļŦāļēāđāļāļāļāļ§āđāļēāļāļāđāļāļ
āđāļāđāļāđāļāļĩāļĒāļ§āļāļąāļāļāļēāļĢāļāđāļāļŦāļēāđāļāļīāļāļĨāļķāļāļāđāļāļ āļāļąāļĨāļāļāļĢāļīāļāļķāļĄāļāļĩāđāđāļāđāļāļŦāļāļķāđāļāđāļāļ§āļīāļāļĩāļāļēāļĢāļŠāļģāļĢāļ§āļāļāļĢāļēāļāļāļĩāđāļāđāļēāļĒāđāļĨāļ°āļāļ·āđāļāļāļēāļāļāļĩāđāļŠāļļāļ āļāļĢāļ°āđāļāđāļāļŠāļģāļāļąāļāļāļ·āļāđāļĢāļēāļĄāļĩāļāļļāļāļĒāļāļāļāļąāļāļāļļāļāļąāļāļāļĒāļđāđāļāđāļēāļ āđāļĢāļēāđāļŠāđāļāļļāļāļĒāļāļāļāļĩāđāļāļĒāļđāđāļāļīāļāļāļąāļāļāļĩāđāļĒāļąāļāđāļĄāđāđāļāđāđāļĒāļĩāđāļĒāļĄāļāļĄāļāļąāđāļāļŦāļĄāļāļĨāļāđāļāļāļīāļ§āđāļĨāļ°āđāļĨāļ·āļāļāļāļāļāđāļāļĢāļ°āļāļāļāļāļąāļāđāļ (āļāļķāđāļāđāļāđāļāļāļļāļāļĒāļāļāļāļĩāđāđāļāđāļāđāļ§āđāļāļĩāđāļŠāđāļ§āļāļŦāļąāļ§āļāļāļāļāļīāļ§) āļāļķāđāļāļāļĨāļēāļĒāđāļāđāļāļāļļāļāļĒāļāļāļāļąāļāļāļļāļāļąāļ... āļāļēāļĢāđāļāđāļāļāļąāļĨāļāļāļĢāļīāļāļķāļĄāļāļĩāđāļāļāļāđāļāđāļāļāļąāđāļāļāļāļ āđāļĢāļēāļŠāļēāļĄāļēāļĢāļāļĢāļ°āļāļļāļāļąāđāļāļāļāļāļāđāļāđāļāļāļĩāđāđāļāđ:- āđāļĒāļĩāđāļĒāļĄāļāļĄāļāļļāļāļĒāļāļāļāļąāļāđāļāļāļĩāđāļĒāļąāļāđāļĄāđāđāļāđāđāļĒāļĩāđāļĒāļĄāļāļĄāļāļķāđāļāļāļĒāļđāđāļāļīāļāļāļąāļāļāļļāļāļŠāļļāļāļĒāļāļāļāļąāļāļāļļāļāļąāļ āļāļģāđāļāļĢāļ·āđāļāļāļŦāļĄāļēāļĒāļ§āđāļēāđāļĒāļĩāđāļĒāļĄāļāļĄāđāļĨāđāļ§āļĨāđāļ§āļāļŦāļāđāļē āđāļĨāļ°āđāļāļīāđāļĄāļĨāļāđāļāļāļīāļ§
- āļŦāļēāļāđāļĄāđāļŠāļēāļĄāļēāļĢāļāļāļģāđāļāļīāļāļāļēāļĢāļāļąāđāļāļāļāļ #1 āđāļāđ āđāļŦāđāļĨāļāļāļļāļāļĒāļāļāļāļāļāļāļēāļāļāļīāļ§āđāļĨāļ°āļāļģāđāļŦāđāđāļāđāļāļāļļāļāļĒāļāļāļāļąāļāļāļļāļāļąāļ
- āļŦāļēāļāđāļĄāđāļŠāļēāļĄāļēāļĢāļāļāļģāđāļāļīāļāļāļēāļĢāļāļąāđāļāļāļāļ #1 āđāļĨāļ° #2 āđāļāđ āđāļŠāļāļāļ§āđāļēāđāļĢāļēāļāđāļēāļĄāļāđāļēāļāđāļŠāļĢāđāļāđāļĨāđāļ§ â āļāļļāļāļāļļāļāļĒāļāļāļāļđāļāļŠāļģāļĢāļ§āļāđāļĨāđāļ§ (āļŦāļēāļāđāļĢāļēāļĄāļĩāļāļĢāļēāļāļāļĩāđāđāļāļ·āđāļāļĄāđāļĒāļāļāļąāļ)
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;
}
}
āļāļĨāļēāļŠ Vertex āļāļąāđāļāđāļŦāļĄāļ·āļāļāļāļąāļāļāļĨāļēāļŠāļāļĩāđāđāļĢāļēāđāļāđāļāļąāļāļāļąāļĨāļāļāļĢāļīāļāļķāļĄāļāļēāļĢāļāđāļāļŦāļēāđāļāļīāļāļĨāļķāļāđāļāđāļāļāļąāļāļāļąāļāđāļĢāļ āđāļĢāļēāļĄāļēāļĨāļāļāļāļģāļāļąāļĨāļāļāļĢāļīāļāļķāļĄāļāļĩāđāđāļāđāļāđāļāļĢāļīāļ:
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();
}
}
āđāļāļēāļāđāļāļļāļāļāļāļāđāļāļĨ:
4. āļāļąāļĨāļāļāļĢāļīāļāļķāļĄāļāļāļ Dijkstra
āļāļēāļĄāļāļĩāđāļāļĨāđāļēāļ§āđāļ§āđāļāđāļēāļāļāđāļ āļāļĢāļēāļāļŠāļēāļĄāļēāļĢāļāļāļģāļŦāļāļāļāļīāļĻāļāļēāļāļŦāļĢāļ·āļāđāļĄāđāļĄāļĩāļāļīāļĻāļāļēāļāđāļāđ āđāļĨāļ°āļāļļāļāļāļ°āļāļģāđāļāđāļ§āđāļēāļŠāļēāļĄāļēāļĢāļāļāđāļ§āļāļāđāļģāļŦāļāļąāļāđāļāđāđāļāđāļāļāļąāļ āļāļ§āļēāļĄāļŠāļąāļĄāļāļąāļāļāđāļāļāļāđāļāļāļāļģāļĨāļāļāļāļĢāļēāļāļāļģāļāļąāļāđāļāļāļāđāļ§āļāļāđāļģāļŦāļāļąāļāļāļĩāđāļĄāļąāļāļāļāđāļāļāļĩāļ§āļīāļāļāļĢāļīāļ āļāļąāļ§āļāļĒāđāļēāļāđāļāđāļ āđāļāļāļāļĩāđāđāļĄāļ·āļāļāļāļĩāđāđāļĄāļ·āļāļāļāđāļēāļāđ āđāļāđāļāļāļļāļāļĒāļāļ āđāļĨāļ°āļāļāļāļĢāļ°āļŦāļ§āđāļēāļāđāļĄāļ·āļāļāđāļŦāļĨāđāļēāļāļąāđāļāđāļāđāļāļāļāļāļāļĩāđāļĄāļĩāļāļēāļĢāļāļĢāļēāļāļĢāļāļēāļāđāļāļĩāļĒāļ§āļāļķāđāļāđāļŦāļĨāđāļāđāļāļāļīāļĻāļāļēāļāļāļāļāļāļāļāļāļĩāđāļāļģāļŦāļāļ āļŠāļĄāļĄāļāļīāļ§āđāļēāļāļļāļāđāļāđāļāļāļĢāļīāļĐāļąāļāļāļāļŠāđāļāļŠāļīāļāļāđāļē āđāļĨāļ°āļāļļāļāļāđāļāļāļāđāļāļŦāļēāđāļŠāđāļāļāļēāļāļāļĩāđāļŠāļąāđāļāļāļĩāđāļŠāļļāļāļĢāļ°āļŦāļ§āđāļēāļāļŠāļāļāđāļĄāļ·āļāļāļāļĩāđāļŦāđāļēāļāđāļāļĨ āļāļļāļāļāļ°āļāļģāļĄāļąāļāđāļāđāļāļĒāđāļēāļāđāļĢ? āļāļēāļĢāļāđāļāļŦāļēāđāļŠāđāļāļāļēāļāļāļĩāđāļŠāļąāđāļāļāļĩāđāļŠāļļāļāļĢāļ°āļŦāļ§āđāļēāļāļāļļāļāļĒāļāļāļŠāļāļāļāļļāļāđāļāđāļāļāļąāļāļŦāļēāļāļĩāđāļāļāļāđāļāļĒāļāļĩāđāļŠāļļāļāļāļąāļāļŦāļēāļŦāļāļķāđāļāļāļĩāđāđāļāđāđāļāđāļāđāđāļāļĒāđāļāđāļāļĢāļēāļāļāđāļ§āļāļāđāļģāļŦāļāļąāļ āđāļāļ·āđāļāđāļāđāđāļāļāļąāļāļŦāļēāļāļĩāđ āđāļĢāļēāđāļāđāļāļąāļĨāļāļāļĢāļīāļāļķāļĄāļāļāļ Dijkstra āđāļĄāļ·āđāļāļāļļāļāļĢāļąāļāđāļĨāđāļ§ āļāļļāļāļāļ°āļĢāļđāđāđāļŠāđāļāļāļēāļāļāļĩāđāļŠāļąāđāļāļāļĩāđāļŠāļļāļāļāļēāļāļāļļāļāļĒāļāļāđāļĢāļīāđāļĄāļāđāļāļāļĩāđāļāļģāļŦāļāļāđāļāļĒāļąāļāļāļļāļāļĒāļāļāļāļ·āđāļāđ āļāļąāđāļāļāļāļāļāļāļāļāļąāļĨāļāļāļĢāļīāļāļķāļĄāļāļĩāđāļĄāļĩāļāļ°āđāļĢāļāđāļēāļ? āļāļąāļāļāļ°āļāļĒāļēāļĒāļēāļĄāļāļāļāļāļģāļāļēāļĄāļāļĩāđ āļāļąāđāļāļāļāļāļāļāļāļāļąāļĨāļāļāļĢāļīāļāļķāļĄāļāļāļ Dijkstra:- āļāļąāđāļāļāļāļāļāļĩāđ 1: āļāđāļāļŦāļēāđāļŦāļāļāļāļĩāđāļāļĒāļđāđāļāļīāļāļāļąāļāļāļķāđāļāļĄāļĩāļāđāļāļāļļāļāļāļēāļĢāļāļģāļāļēāļāļāđāļģāļāļĩāđāļŠāļļāļ (āļāđāļģāļŦāļāļąāļāļāļāļāļāđāļģāļŠāļļāļ) āļāļļāļāļāļģāļĨāļąāļāļĒāļ·āļāļāļĒāļđāđāļāļĩāđāļāļļāļāđāļĢāļīāđāļĄāļāđāļāđāļĨāļ°āļāļīāļāļ§āđāļēāļāļ°āđāļāļāļĩāđāđāļŦāļ: āđāļāļĒāļąāļāđāļŦāļāļ A āļŦāļĢāļ·āļāđāļŦāļāļ B āļāļēāļĢāļĒāđāļēāļĒāđāļāļĒāļąāļāđāļāđāļĨāļ°āđāļŦāļāļāđāļŦāļĨāđāļēāļāļĩāđāļĄāļĩāļāđāļēāđāļāđāļāđāļēāļĒāđāļāđāļēāđāļĢ
- āļāļąāđāļāļāļāļāļāļĩāđ 2: āļāļģāļāļ§āļāļĢāļ°āļĒāļ°āļāļēāļāđāļāļāļēāļĢāđāļāļīāļāļāļēāļāđāļāļĒāļąāļāđāļāļ·āđāļāļāļāđāļēāļāļāļāļāđāļŦāļāļāļāļąāđāļāļŦāļĄāļāļāļĩāđāļāļąāļĨāļāļāļĢāļīāļāļķāļĄāļĒāļąāļāđāļĄāđāđāļāđāđāļĒāļĩāđāļĒāļĄāļāļĄāđāļĄāļ·āđāļāļŠāļģāļĢāļ§āļāļāļāļāļāļēāļ Ð āļŦāļēāļāļĢāļ°āļĒāļ°āļāļēāļāđāļŦāļĄāđāļāđāļāļĒāļāļ§āđāļēāļĢāļ°āļĒāļ°āļāļēāļāđāļāđāļē āđāļŠāđāļāļāļēāļāļāđāļēāļāļāļāļ B āļāļ°āļāļĨāļēāļĒāđāļāđāļāđāļŠāđāļāļāļēāļāđāļŦāļĄāđāļāļĩāđāļŠāļąāđāļāļāļĩāđāļŠāļļāļāļŠāļģāļŦāļĢāļąāļāļāļļāļāļĒāļāļāļāļĩāđ
- āļāļąāđāļāļāļāļāļāļĩāđ 3: āļāļģāđāļāļĢāļ·āđāļāļāļŦāļĄāļēāļĒāļāļļāļāļĒāļāļ B āļ§āđāļēāđāļĒāļĩāđāļĒāļĄāļāļĄāđāļĨāđāļ§
- āļāļąāđāļāļāļāļāļāļĩāđ 4: āđāļāļāļĩāđāļāļąāđāļāļāļāļāļāļĩāđ 1
- āļĄāļĩāļŠāļēāļĄāđāļŠāđāļāļāļēāļāļāļĩāđāđāļāđāļāđāļāđāļāđāļŠāļģāļŦāļĢāļąāļāļāļļāļāļĒāļāļ A: āđāļāļĒāļąāļ B āļāļĩāđāļĄāļĩāļāđāļģāļŦāļāļąāļ 3 āļāļķāļ ÐĄ āļāļĩāđāļĄāļĩāļāđāļģāļŦāļāļąāļ 5 āđāļĨāļ°āđāļāļĒāļąāļ D āļāļĩāđāļĄāļĩāļāđāļģāļŦāļāļąāļ 7 āļāļēāļĄāļāļąāđāļāļāļāļāđāļĢāļāļāļāļāļāļąāļĨāļāļāļĢāļīāļāļķāļĄ āđāļĢāļēāđāļĨāļ·āļāļāđāļŦāļāļāļāļĩāđāļĄāļĩāļāđāļāļāļļāļāļāđāļģāļāļĩāđāļŠāļļāļ (āļāđāļģāļŦāļāļąāļāļāļāļ) āđāļāļāļĢāļāļĩāļāļĩāđ āļāļĩ.
-
āđāļāļ·āđāļāļāļāļēāļāđāļāļ·āđāļāļāļāđāļēāļāļāļĩāđāđāļĄāđāļĄāļĩāđāļāļĢāđāļĒāļĩāđāļĒāļĄāļāļĄāđāļāļĩāļĒāļāļāļāđāļāļĩāļĒāļ§āļāļāļ B āļāļ·āļāļāļļāļāļĒāļāļ Ð āđāļĢāļēāļāļķāļāļāļĢāļ§āļāļŠāļāļāļ§āđāļēāđāļŠāđāļāļāļēāļāļāļ°āđāļāđāļāđāļāđāļāđāļĢāļŦāļēāļāđāļĢāļēāļāđāļēāļāļāļļāļāļĒāļāļāļāļĩāđ 3(AB) + 6(āļ.āļĻ.) = 9.
āļāļąāļāļāļąāđāļāđāļĢāļēāļāļķāļāļāļąāļāļāļķāļāļ§āđāļēāđāļŠāđāļāļāļēāļāļāļĩāđāļŠāļąāđāļāļāļĩāđāļŠāļļāļāđāļāļāļąāļāļāļļāļāļąāļāļāļēāļ A āļāļķāļ E āļāļ·āļ 9
-
āđāļāļ·āđāļāļāļāļēāļāļāļēāļāļāļāļāđāļĢāļēāļāļąāļāļāļļāļāļĒāļāļ B āđāļŠāļĢāđāļāļŠāļĄāļāļđāļĢāļāđāđāļĨāđāļ§ āđāļĢāļēāļāļķāļāļāļģāđāļāļīāļāļāļēāļĢāđāļĨāļ·āļāļāļāļļāļāļĒāļāļāļāļąāļāđāļāļāļĩāđāļāļāļāļĄāļĩāļāđāļģāļŦāļāļąāļāļāļąāđāļāļāđāļģ
āļāļēāļāļāļļāļāļĒāļāļ A āđāļĨāļ° B āļāļ§āļēāļĄāđāļāđāļāđāļāđāļāđāļāļ·āļāļāļļāļāļĒāļāļ D (7), C (5) āļŦāļĢāļ·āļ E (6)
āļāļāļāļāļķāļ ÐĄ āļĄāļĩāļāđāļģāļŦāļāļąāļāļāđāļāļĒāļāļĩāđāļŠāļļāļ āļāļąāļāļāļąāđāļāđāļĢāļēāļāļķāļāđāļāļāļĩāđāļāļļāļāļĒāļāļāļāļĩāđ
-
āļāđāļāđāļ āđāļāđāļāđāļāļĒ āđāļĢāļēāļāļ°āļāđāļāļŦāļēāđāļŠāđāļāļāļēāļāļāļĩāđāļŠāļąāđāļāļāļĩāđāļŠāļļāļāđāļāļĒāļąāļāļāļļāļāļĒāļāļāļāđāļēāļāđāļāļĩāļĒāļāđāļĄāļ·āđāļāļāđāļēāļ C:
-
AD = 5 (AC) + 3 (CD) = 8 āđāļāđāđāļāļ·āđāļāļāļāļēāļāđāļŠāđāļāļāļēāļāļāļĩāđāļŠāļąāđāļāļāļĩāđāļŠāļļāļāļāđāļāļāļŦāļāđāļē (AC = 7) āļāđāļāļĒāļāļ§āđāļēāđāļŠāđāļāļāļēāļāļāļĩāđāļāļķāļ ÐĄ āđāļĢāļēāļāļķāļāļāļāđāļŠāđāļāļāļēāļāļāļĩāđāļŠāļąāđāļāļāļĩāđāļŠāļļāļ (AC = 7) āđāļ§āđāđāļĄāđāđāļāļĨāļĩāđāļĒāļāđāļāļĨāļ
-
CE = 5(AC) + 4(CE) = 9 āđāļŠāđāļāļāļēāļāļāļĩāđāļŠāļąāđāļāļāļĩāđāļŠāļļāļāđāļŦāļĄāđāļāļĩāđāđāļāđāļēāļāļąāļāđāļŠāđāļāļāļēāļāļāđāļāļāļŦāļāđāļē āļāļąāļāļāļąāđāļāđāļĢāļēāļāļķāļāļāļĨāđāļāļĒāđāļŦāđāļĄāļąāļāđāļĄāđāļĄāļĩāļāļēāļĢāđāļāļĨāļĩāđāļĒāļāđāļāļĨāļ
-
-
āļāļēāļāļāļļāļāļĒāļāļāļāļĩāđāđāļāļĨāđāļāļĩāđāļŠāļļāļāļāļĩāđāđāļāđāļēāļāļķāļāđāļāđ (E āđāļĨāļ° D) āđāļŦāđāđāļĨāļ·āļāļāļāļļāļāļĒāļāļāļāļĩāđāļĄāļĩāļāđāļģāļŦāļāļąāļāļāļāļāļāđāļāļĒāļāļĩāđāļŠāļļāļ āđāļāđāļ D (3)
-
āđāļĢāļēāļāļāđāļŠāđāļāļāļēāļāļāļĩāđāļŠāļąāđāļāļāļĩāđāļŠāļļāļāđāļāļĒāļąāļāđāļāļ·āđāļāļāļāđāļēāļ F.
AF = 7(āđāļāļĐāļāļē) + 3(DF) = 9
-
āļāļēāļāļāļļāļāļĒāļāļāļāļĩāđāđāļāļĨāđāļāļĩāđāļŠāļļāļāļāļĩāđāđāļāđāļēāļāļķāļāđāļāđ (E āđāļĨāļ° F) āđāļŦāđāđāļĨāļ·āļāļāļāļļāļāļĒāļāļāļāļĩāđāļĄāļĩāļāđāļģāļŦāļāļąāļāļāļāļāļāđāļāļĒāļāļĩāđāļŠāļļāļ āđāļāđāļ F (3)
-
āļāđāļāļŦāļēāđāļŠāđāļāļāļēāļāļāļĩāđāļŠāļąāđāļāļāļĩāđāļŠāļļāļāđāļāļĒāļąāļāđāļāļ·āđāļāļāļāđāļēāļ G.
āđāļāļāļĩ = 7(āđāļāļĐāļāļē) + 3(DF) + 4(FG) = 14
āļāļąāļāļāļąāđāļāđāļĢāļēāļāļķāļāļāļāđāļŠāđāļāļāļēāļāļāļēāļ A āļāļķāļ G
āđāļāđāđāļāļ·āđāļāđāļŦāđāđāļāđāđāļāļ§āđāļēāļĄāļąāļāļŠāļąāđāļāļāļĩāđāļŠāļļāļ āđāļĢāļēāļāđāļāļāļāļģāļāļēāļĄāļāļąāđāļāļāļāļāļāļāļāđāļĢāļēāļāļāļāļļāļāļĒāļāļ E āļāđāļ§āļĒ
-
āđāļāļ·āđāļāļāļāļēāļāļāļļāļāļĒāļāļ G āđāļĄāđāļĄāļĩāļāļļāļāļĒāļāļāļāđāļēāļāđāļāļĩāļĒāļāļāļĩāđāļāļĩāđāđāļāđāļāļĒāļāļāļāļāļĩāđāļāļģāļŦāļāļ āđāļĢāļēāļāļķāļāđāļŦāļĨāļ·āļāđāļāļĩāļĒāļāļāļļāļāļĒāļāļ E āđāļāđāļēāļāļąāđāļ āļāļąāļāļāļąāđāļāđāļĢāļēāļāļķāļāđāļĨāļ·āļāļāļĄāļąāļ
-
āļāđāļāļŦāļēāđāļŠāđāļāļāļēāļāļāļĩāđāļŠāļąāđāļāļāļĩāđāļŠāļļāļāđāļāļĒāļąāļāđāļāļ·āđāļāļāļāđāļēāļ G.
AG = 3 (AB) + 6 (BE) + 6 (EG) = 15 āđāļŠāđāļāļāļēāļāļāļĩāđāļĒāļēāļ§āļāļ§āđāļēāđāļŠāđāļāļāļēāļāļāļĩāđāļŠāļąāđāļāļāļĩāđāļŠāļļāļāļāđāļāļāļŦāļāđāļē (AG (14)) āļāļąāļāļāļąāđāļāđāļĢāļēāļāļķāļāļāļĨāđāļāļĒāđāļŦāđāđāļŠāđāļāļāļēāļāļāļĩāđāđāļĄāđāđāļāļĨāļĩāđāļĒāļāđāļāļĨāļ
āđāļāļ·āđāļāļāļāļēāļāđāļĄāđāļĄāļĩāļāļļāļāļĒāļāļāļāļĩāđāļāļģāļāļēāļ G āļāļķāļāđāļĄāđāļŠāļĄāđāļŦāļāļļāļŠāļĄāļāļĨāļāļĩāđāļāļ°āļĢāļąāļāļāļąāđāļāļāļāļāļāļāļāļąāļĨāļāļāļĢāļīāļāļķāļĄāļāļāļāļļāļāļĒāļāļāļāļĩāđ āļāļąāđāļāļŦāļĄāļēāļĒāļāļ§āļēāļĄāļ§āđāļēāļāļēāļĢāļāļģāļāļēāļāļāļāļāļāļąāļĨāļāļāļĢāļīāļāļķāļĄāđāļŠāļĢāđāļāļŠāļĄāļāļđāļĢāļāđ
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;
}
}
āļāļĨāļēāļŠāļāļļāļāļŠāļļāļāļĒāļāļāđāļāļāļāļ°āđāļŦāļĄāļ·āļāļāļāļąāļāļāļĨāļēāļŠāļāļļāļāļŠāļļāļāļĒāļāļāļāļĩāđāđāļāđāļŠāļģāļŦāļĢāļąāļāļāļēāļĢāļāđāļāļŦāļēāđāļāļāļāļ§āđāļēāļāļāđāļāļ āđāļāļāļēāļĢāđāļŠāļāļāđāļŠāđāļāļāļēāļāļāļĩāđāļŠāļąāđāļāļāļĩāđāļŠāļļāļ āđāļĢāļēāļāļģāđāļāđāļāļāđāļāļāļĄāļĩāļāļĨāļēāļŠāđāļŦāļĄāđāļāļĩāđāļāļ°āļĄāļĩāļāđāļāļĄāļđāļĨāļāļĩāđāđāļĢāļēāļāđāļāļāļāļēāļĢ:
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;
}
}
āđāļāļāļąāđāļāđāļĢāļĩāļĒāļāļāļĩāđ āđāļĢāļēāļāļ°āđāļŦāđāļāļĢāļ°āļĒāļ°āļāļēāļāļĢāļ§āļĄāļāļāļāđāļŠāđāļāļāļēāļāđāļĨāļ°āļāļļāļāļĒāļāļāļāļĩāđāļāļ°āđāļāļĨāļ·āđāļāļāļāļĩāđāđāļĄāļ·āđāļāļāđāļēāļāđāļāļāļēāļĄāđāļŠāđāļāļāļēāļāļāļĩāđāļŠāļąāđāļāļāļĩāđāļŠāļļāļ āļāļĩāļāļĩāđāļĨāļāļāļāļđāļāļĨāļēāļŠāļāļĩāđāđāļĢāļēāļŠāļģāļĢāļ§āļāđāļŠāđāļāļāļēāļāļāļĩāđāļŠāļąāđāļāļāļĩāđāļŠāļļāļāļāđāļēāļāļāļĢāļēāļāļāļąāļ āļāļąāļāļāļąāđāļāđāļĢāļēāļāļķāļāļĄāļĩāļāļĨāļēāļŠāļāļĢāļēāļ:
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() + ")");
}
}
}
}
āļāļąāđāļāļāļ·āļāļāļ§āļēāļĄāļĄāļŦāļąāļĻāļāļĢāļĢāļĒāđāļāļąāđāļāļŦāļĄāļ =) āļāļāļāļāļĩāđāđāļĢāļēāļĄāļēāļāļđāļāļēāļĢāļāļģāļāļēāļāļāļāļāļāļąāļĨāļāļāļĢāļīāļāļķāļĄāļāļĩāđāļāļąāļ:
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();
}
}
āđāļĨāļ°āđāļāļēāļāđāļāļļāļāļāļāļāđāļāļĨāļāļ·āļ: