JavaRush /Java Blog /Random-KO /인터뷰에서 묻는 것: 알고리즘 검토, 2부

레벨 36

28 February 2021
41 views
0 comments

인터뷰에서 묻는 것: 알고리즘 검토, 2부

이 기사는 알고리즘에 대한 짧은 리뷰의 연속입니다. 첫 번째 부분 에 대한 링크는 다음과 같습니다 . 이전에는 다양한 배열 정렬 알고리즘과 소위 탐욕 알고리즘(Greedy Algorithm) 에 대해 살펴보았습니다 . 오늘은 이와 관련된 그래프와 알고리즘에 대해 이야기해보겠습니다. 인터뷰에서 묻는 것: 알고리즘 검토, 2부 - 1

그래프는 프로그래밍에서 가장 유연하고 다양한 구조 중 하나입니다. 그래프 G는 일반적으로 집합 G = (V, R) 쌍을 사용하여 지정됩니다 . 여기서:

V 는 꼭지점 집합입니다.
R 은 정점 쌍을 연결하는 선 집합입니다.

일반적인 연결선을 모서리( edge) 라고 합니다 . 인터뷰에서 묻는 것: 알고리즘 검토, 2부 - 2

화살표가 있는 선 - 호( arc) : 인터뷰에서 묻는 것: 알고리즘 검토, 2~3부

일반적으로 그래프는 일부 꼭지점을 모서리(호)로 연결하는 다이어그램을 사용하여 표현됩니다. 방향을 직접적으로 나타내는 호로 서로 연결된 그래프를 방향성 이라고 합니다 . 그래프가 모서리로 연결된 경우, 즉 이동 가능한 방향을 표시하지 않은 경우 방향이 지정되지 않습니다 . 이는 정점 A에서 B로, B에서 A로 양방향으로 이동할 수 있음을 의미합니다. 연결된 그래프 는 최소한 하나의 경로가 각 정점에서 다른 정점으로 연결되는 그래프입니다(예제 참조). 위에 ). 그렇지 않은 경우 그래프의 연결이 끊어 집니다 . 인터뷰에서 묻는 것: 알고리즘 검토, 2~4부

또한 가장자리(호)에 가중치(두 정점 사이의 물리적 거리(또는 두 정점 사이의 상대적 전환 시간)를 나타내는 숫자)를 할당할 수 있습니다. 이러한 그래프를 가중치 라고 합니다 . 인터뷰에서 묻는 것: 알고리즘 검토, 2~5부

3. 경로 검색 알고리즘(깊이, 너비)

그래프에서 수행되는 기본 작업 중 하나는 주어진 꼭지점에서 도달할 수 있는 모든 꼭지점을 결정하는 것입니다. 가능한 환승을 통해 한 도시에서 다른 도시로 이동하는 방법을 결정하려고 한다고 상상해 보십시오. 일부 도시는 직접 도달할 수 있지만 다른 도시는 다른 도시를 거쳐 우회해야 합니다. 주어진 정점에서 경로를 찾을 수 있는 모든 정점을 찾아야 하는 상황이 많이 있습니다. 따라서 그래프를 순회하는 방법에는 깊이 우선 순회 와 너비 우선 순회라는 두 가지 주요 방법이 있습니다 . 이를 고려해 보겠습니다. 두 방법 모두 연결된 모든 정점에 대해 반복을 보장합니다. 깊이 우선 및 너비 우선 알고리즘을 더 자세히 고려하려면 다음 그래프를 사용하십시오. 인터뷰에서 묻는 것: 알고리즘 검토, 2~6부

깊이 우선 순회

이는 가장 일반적인 그래프 순회 방법 중 하나입니다. 이 깊이 우선 탐색 전략은 그래프 속으로 최대한 깊이 들어가 막다른 골목에 도달하면 이전에 방문하지 않은 인접한 정점이 있는 가장 가까운 정점으로 돌아가는 것으로 구성됩니다 . 이 알고리즘은 교착 상태에 도달했을 때 반환할 위치에 대한 정보를 스택에 저장합니다. 깊이 우선 탐색 규칙:

이전에 방문하지 않은 인접한 정점을 방문하여 표시하고 스택에 놓습니다.
이 정상으로 가세요.
1단계를 반복합니다.
1단계를 완료하는 것이 불가능하면 이전 정점으로 돌아가서 규칙 1을 반복해 보십시오. 이것이 불가능하다면 이전 정점으로 돌아가는 식으로 순회를 계속할 수 있는 정점을 찾을 때까지 계속합니다.
모든 정점이 스택에 있을 때까지 계속합니다.

이 알고리즘의 코드가 Java에서 어떻게 보이는지 살펴보겠습니다.

public class Graph {
  private final int MAX_VERTS = 10;
  private Vertex vertexArray[]; //массив вершин
  private int adjMat[][]; // матрица смежности
  private int nVerts; // текущее количество вершин
  private Stack<integer> stack;

  public Graph() { // инициализация внутрених полей
     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() { // обход в глубину
     vertexArray[0].setWasVisited(true); // берётся первая вершина
     displayVertex(0);
     stack.push(0);

     while (!stack.empty()) {
        int v = getAdjUnvisitedVertex(stack.peek()); // вынуть индекс смежной веришины, еckи есть 1, нету -1
        if (v == -1) { // если непройденных смежных вершин нету
           stack.pop(); // элемент извлекается из стека
        }
        else {
           vertexArray[v].setWasVisited(true);
           displayVertex(v);
           stack.push(v); // элемент попадает на вершину стека
        }
     }

     for (int j = 0; j < nVerts; j++) {  // сброс флагов
        vertexArray[j].wasVisited = false;
     }

  }

  private int getAdjUnvisitedVertex(int v) {
     for (int j = 0; j < nVerts; j++) {
        if (adjMat[v][j] == 1 && vertexArray[j].wasVisited == false) {
           return j; //возвращает первую найденную вершину
        }
     }
     return -1;
  }
}
</integer>

상단은 다음과 같습니다.

public class Vertex {
  private char label;  // метка А например
  public boolean wasVisited;

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

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

  public boolean isWasVisited() {
     return this.wasVisited;
  }

  public void setWasVisited(final boolean wasVisited) {
     this.wasVisited = wasVisited;
  }
}

특정 꼭짓점을 사용하여 이 알고리즘을 실행하고 올바르게 작동하는지 살펴보겠습니다.

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

콘솔 출력:

방문 횟수: A B E C D F G

인접 행렬이 있고 걷기 방법에서는 루프 내에 중첩된 루프를 사용하므로 시간 복잡도는 O(N²) 입니다 .

폭으로 걷다

깊이 우선 순회와 마찬가지로 이 알고리즘은 그래프 순회를 위한 가장 간단하고 기본적인 방법 중 하나입니다. 그 본질은 우리가 특정 현재 정점을 가지고 있다는 것입니다. 이 정점에서 인접하고 통과되지 않은 모든 정점을 큐에 넣고 다음 요소(큐에 먼저 저장됨)를 선택하여 현재로 만듭니다... 인터뷰에서 묻는 것: 알고리즘 검토, 2부 - 8부

이 알고리즘을 다음과 같이 나누면 단계에서는 다음 규칙을 강조할 수 있습니다.

현재 정점에 인접한 이전에 방문하지 않은 다음 정점을 방문하고 미리 표시한 후 대기열에 추가합니다.
규칙 #1을 충족할 수 없는 경우 큐에서 정점을 제거하고 이를 현재 정점으로 만듭니다.
규칙 #1과 #2가 불가능하면 순회가 완료되고 모든 정점이 순회됩니다(그래프가 연결된 경우).

그래프 클래스는 알고리즘을 처리하고 내부 스택을 대기열로 바꾸는 메서드를 제외하고 깊이 우선 검색 알고리즘의 유사한 클래스와 거의 동일합니다.

public class Graph {
  private final int MAX_VERTS = 10;
  private Vertex vertexList[]; //массив вершин
  private int adjMat[][]; // матрица смежности
  private int nVerts; // текущее количество вершин
  private Queue<integer> 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++) {  // заполнение матрицы смежности нулями
           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() { // обход в глубину
     vertexList[0].setWasVisited(true);
     displayVertex(0);
     queue.add(0);
     int v2;

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

        while((v2 = getAdjUnvisitedVertex(v))!=-1) {// цикл будет работать, пока все смежные вершины не будут найденны, и не будут добавлены в очередь
           vertexList[v2].wasVisited =true;
           displayVertex(v2);
           queue.add(v2);
        }
     }

     for (int j = 0; j < nVerts; j++) {  // сброс флагов
        vertexList[j].wasVisited = false;
     }

  }

  private int getAdjUnvisitedVertex(int v) {
     for (int j = 0; j < nVerts; j++) {
        if (adjMat[v][j] == 1 && vertexList[j].wasVisited == false) {
           return j; //возвращает первую найденную вершину
        }
     }
     return -1;
  }
}
</integer>

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

콘솔 출력:

방문 횟수: A B C D E F G

다시 말하지만, 인접 행렬이 있고 루프 내에 중첩된 루프를 사용하므로 O(N²) 는 위 알고리즘의 시간 복잡도입니다.

4. Dijkstra 알고리즘

앞서 언급했듯이 그래프는 방향이 지정 되거나 방향이 지정되지 않을 수 있습니다 . 그리고 기억하시겠지만, 여전히 가중치를 부여할 수 있습니다 . 가중치가 부여된 방향성 그래프는 실생활에서 흔히 볼 수 있습니다. 예를 들어, 도시가 꼭지점이고 도시 사이의 경로가 도로인 도시 지도와 같이 도로는 일방 통행, 즉 그래프 방향을 가질 수 있습니다. 당신이 화물 운송에 종사하고 있고 멀리 떨어져 있는 두 도시 사이의 최단 경로를 만들어야 한다고 가정해 보겠습니다. 어떻게 하시겠습니까? 가중치 그래프와 관련된 가장 일반적인 문제 중 하나는 두 정점 사이의 최단 경로를 선택하는 문제입니다. 이 문제를 해결하기 위해 Dijkstra 알고리즘을 사용합니다 . 나는 Dijkstra의 알고리즘을 실행함으로써 주어진 초기 정점에서 모든 정점에 대한 최단 경로를 찾을 것이라는 점을 즉시 언급하고 싶습니다. 이 알고리즘에는 어떤 단계가 있나요? 나는 이 질문에 답하려고 노력할 것이다. Dijkstra 알고리즘의 단계:

1단계 : 전환 비용이 가장 적게 드는 노드를 검색합니다. 당신은 맨 처음에 서서 어디로 가야 할지 고민하고 있습니다: 노드 A 로 갈 것인지 , 노드 B 로 갈 것인지. 각 노드에 도달하는 데 얼마나 걸리나요?
2단계 : B 에서 가장자리를 따라 이동할 때 아직 알고리즘 의 영향을 받지 않은 B의 모든 이웃에 도달하는 데 걸리는 시간을 계산합니다. 이 새로운 시간이 이전 시간보다 짧은 것으로 판명되면 모서리 B를 통과하는 경로가 이 정점에 대한 새로운 최단 경로가 됩니다.
3단계 : 정점 B를 통과한 것으로 표시합니다.
4단계 : 1단계로 이동합니다.

우리는 모든 정점을 통과할 때까지 이 단계의 주기를 반복할 것입니다. 다음 가중치 방향 그래프를 고려해 보겠습니다. 인터뷰에서 묻는 것: 알고리즘 검토, 2부 - 10

따라서 위 알고리즘을 사용하여 A에서 G까지의 최단 경로를 결정합니다.

정점 A 에는 세 가지 가능한 경로가 있습니다. 가중치가 3인 B , 가중치가 5인 C , 가중치가 7인 D 입니다. 알고리즘의 첫 번째 지점에 따라 전환이 가장 낮은 노드를 선택합니다. 비용 - 즉, B 입니다 .
B 에 대해 통과되지 않은 유일한 인접 정점은 정점 E 이므로 이 정점을 통과할 때 경로가 무엇인지 확인합니다. 3( AB ) + 6( BE ) = 9.
따라서 현재 AE에 대한 최단 경로는 9라는 것을 알 수 있습니다.
정점 B 에 대한 작업이 이미 완료되었으므로 이전 가장자리의 최소 가중치를 사용하여 다음 정점을 선택하는 것으로 넘어갑니다.
정점 A 와 B 에서 정점 D (7), C (5), E (6) 가 될 수 있습니다 .

C는 가장 작은 간선 가중치를 가지 므로 이 정점으로 이동합니다.
다음으로 이전과 마찬가지로 C를 통과할 때 이웃 꼭지점까지의 최단 경로를 찾습니다.
- AD = 5( AC ) + 3( CD ) = 8이지만 이전 최단 경로 AC = 7, 즉 C 를 통해 이보다 작으므로 최단 경로 AD = 7은 변경하지 않고 그대로 둡니다.
- CE = 5( AC ) + 4( CE ) = 9, 이 새로운 최단 경로는 이전 경로와 동일하므로 변경하지 않고 그대로 둡니다.
사용 가능한 가장 가까운 정점 E 와 D 중에서 가장자리 가중치가 가장 작은 정점, 즉 D (3)를 선택합니다.
우리는 이웃인 F 까지 의 최단 경로를 알아냅니다.
AF = 7( AD ) + 3( DF ) = 10
사용 가능한 가장 가까운 정점 E 및 F 중에서 가장자리의 가중치가 가장 작은 정점, 즉 F (3)를 선택합니다.
우리는 이웃인 G 까지 의 최단 경로를 알아냅니다.
AG = 7( AD ) + 3( DF ) + 4( FG ) = 14

실제로 여기서 우리는 A 에서 G 로 가는 길을 찾았습니다.

그러나 이것이 가장 짧은지 확인하려면 정점 E 에 대해서도 단계를 실행해야 합니다 .
정점 G 에는 방향이 지정된 경로가 연결되는 이웃 정점이 없으므로 정점 E 만 남습니다 . 이를 선택합니다.
우리는 이웃 G 까지 의 최단 경로를 알아냅니다.
AG = 3( AB ) + 6( BE ) + 6( EG ) = 15, 이 경로는 이전의 가장 짧은 AG(14)보다 길기 때문에 이 경로를 변경하지 않고 그대로 둡니다.

G 에서 이어지는 정점이 없기 때문에 주어진 정점에 대해 단계를 실행하는 것은 의미가 없습니다. 따라서 알고리즘 작업이 완료된 것으로 간주될 수 있습니다.

앞서 말했듯이 AG 에 대한 최단 경로를 찾는 것 외에도 정점 A(AB, AC, AD, AE, AF) 에서 모든 정점에 대한 최단 경로를 얻었습니다 . 이제 이것이 Java에서 어떻게 구현될 수 있는지 살펴보겠습니다. 먼저 정점 클래스를 살펴보겠습니다.

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 { // an object данного класса содержащий расстояние и предыдущие и пройденные вершины
   private int distance; // текущая дистанция от начальной вершины
   private List<integer> parentVertices; // текущий родитель вершины

   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<integer> getParentVertices() {
       return parentVertices;
   }

   public void setParentVertices(List<integer> parentVertices) {
       this.parentVertices = parentVertices;
   }
}
</integer></integer></integer>

이 수업에서는 경로의 전체 거리와 최단 경로를 통과할 때 덮게 될 정점을 볼 수 있습니다. 이제 실제로 그래프의 최단 순회가 발생하는 클래스를 고려하고 싶습니다. 따라서 그래프 클래스는 다음과 같습니다.

public class Graph {
   private final int MAX_VERTS = 10;// максимальное количество вершин
   private final int INFINITY = 100000000; // это число у нас будет служить в качестве "бесконечности"
   private Vertex vertexList[]; // список вершин
   private int relationMatrix[][]; // матрица связей вершин
   private int countOfVertices; // текущее количество вершин
   private int countOfVertexInTree; // количество рассмотренных вершин в дереве
   private List<path> shortestPaths; // список данных кратчайших путей
   private int currentVertex; // текущая вершина
   private int startToCurrent; //расстояние до currentVertex

   public Graph() {
       vertexList = new Vertex[MAX_VERTS]; // матрица смежности
       relationMatrix = new int[MAX_VERTS][MAX_VERTS];
       countOfVertices = 0;
       countOfVertexInTree = 0;
       for (int i = 0; i < MAX_VERTS; i++) {// матрица смежности заполняется
           for (int k = 0; k < MAX_VERTS; k++) { // бесконечными расстояниями
               relationMatrix[i][k] = INFINITY; // задания значений по умолчанию
               shortestPaths = new ArrayList<>();// задается пустым
           }
       }
   }

   public void addVertex(char lab) {// задание новых вершин
       vertexList[countOfVertices++] = new Vertex(lab);
   }

   public void addEdge(int start, int end, int weight) {
       relationMatrix[start][end] = weight; // задание ребер между вершинами, с весом между ними
   }

   public void path() { // выбор кратчайшего пути
       //  задание данных для стартовой вершины
       int startTree = 0; // стартуем с вершины 0
       vertexList[startTree].setInTree(true); // включение в состав дерева первого element
       countOfVertexInTree = 1;

       // заполнение коротких путей для вершин смежных с стартовой
       for (int i = 0; i < countOfVertices; i++) {
           int tempDist = relationMatrix[startTree][i];
           Path path = new Path(tempDist);
           path.getParentVertices().add(0);// первым родительским элементом, будет всегда стартовая вершина
           shortestPaths.add(path);
       }
       // пока все вершины не окажутся в дереве
       while (countOfVertexInTree < countOfVertices) { // выполняем, пока количество вершин в дереве не сравняется с общим количеством вершин
           int indexMin = getMin();//получаем индекс вершины с наименшей дистанцией, из вершин еще не входящих в дерево
           int minDist = shortestPaths.get(indexMin).getDistance();// минимальная дистанция вершины, из тек которые ещё не в дереве

           if (minDist == INFINITY) {
               System.out.println("В графе пристувствуют недостижимые вершины");
               break;// в случае если остались непройденными только недостижимые вершины, мы выходим из цикла
           } else {
               currentVertex = indexMin; // переводим указатель currentVert к текущей вершине
               startToCurrent = shortestPaths.get(indexMin).getDistance();// задаем дистанцию к текущей вершине
           }

           vertexList[currentVertex].setInTree(true);  //включение текущей вершины в дерево
           countOfVertexInTree++; // увеличиваем счетчик вершин в дереве
           updateShortestPaths(); // обновление списка кратчайших путей
       }

       displayPaths(); // выводим в консоль результаты
   }

   public void clean() { // очиска дерева
       countOfVertexInTree = 0;
       for (int i = 0; i < countOfVertices; i++) {
           vertexList[i].setInTree(false);
       }
   }

   private int getMin() {
       int minDist = INFINITY; // за точку старта взята "бесконечная" длина
       int indexMin = 0;
       for (int i = 1; i < countOfVertices; i++) {// для каждой вершины
           if (!vertexList[i].isInTree() && shortestPaths.get(i).getDistance() < minDist) { // если вершина ещё не ве дереве и её растояние меньше старого минимума
               minDist = shortestPaths.get(i).getDistance(); // задаётся новый минимум
               indexMin = i; // обновление индекса вершины содержащую минимаьную дистанцию
           }
       }
       return indexMin; //возвращает индекс вершины с наименшей дистанцией, из вершин еще не входящих в дерево
   }

   private void updateShortestPaths() {
       int vertexIndex = 1; // стартовая вершина пропускается
       while (vertexIndex < countOfVertices) { // перебор столбцов

           if (vertexList[vertexIndex].isInTree()) { // если вершина column уже включена в дерево, она пропускается
               vertexIndex++;
               continue;
           }
           // вычисление расстояния для одного element sPath
           // получение ребра от currentVert к column
           int currentToFringe = relationMatrix[currentVertex][vertexIndex];
           // суммирование всех расстояний
           int startToFringe = startToCurrent + currentToFringe;
           // определение расстояния текущего element vertexIndex
           int shortPathDistance = shortestPaths.get(vertexIndex).getDistance();

           // сравнение расстояния через currentVertex с текущим расстоянием в вершине с индексом vertexIndex
           if (startToFringe < shortPathDistance) {// если меньше, то у вершины под индексом vertexIndex будет задан новый кратчайший путь
               List<integer> newParents = new ArrayList<>(shortestPaths.get(currentVertex).getParentVertices());//создаём копию списка родителей вершины currentVert
               newParents.add(currentVertex);// задаём в него и currentVertex How предыдущий
               shortestPaths.get(vertexIndex).setParentVertices(newParents); // соохраняем новый маршут
               shortestPaths.get(vertexIndex).setDistance(startToFringe); // соохраняем новую дистанцию
           }
           vertexIndex++;
       }
   }

   private void displayPaths() { // метод для вывода кратчайших путей на экран
       for (int i = 0; i < countOfVertices; 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<integer> 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() + ")");
           }
       }
   }
}
</integer></integer></path>

사실, 그게 전부 마법입니다 =) 이제 이 알고리즘이 실제로 작동하는 모습을 살펴보겠습니다.

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("Элементы имеют кратчайшие пути из точки A: ");
       graph.path();
       graph.clean();
   }
}

콘솔의 출력은 다음과 같습니다.

요소는 A 지점에서 최단 경로를 갖습니다. A = 0 B = 3 (A -> B) C = 5 (A -> C) D = 7 (A -> D) E = 9 (A -> B -> E) F = 10 (A -> D -> F) G = 14 (A -> D -> F -> G)

이 알고리즘의 시간 복잡도는 루프 내에 루프가 중첩되어 있으므로 O(N²) 에 지나지 않습니다. 오늘은 여기까지입니다. 관심을 가져주셔서 감사합니다! 인터뷰에서 묻는 것: 알고리즘 검토, 2부 - 11

코멘트

TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION