面接で聞かれること: アルゴリズムのレビュー、パート 2

この記事は、アルゴリズムに関する私の短いレビューの続きです。ここに最初の部分へのリンクがあります。 前回は、さまざまな配列ソート アルゴリズムと、いわゆる貪欲アルゴリズムについて説明しました。今日はグラフとそれに関連するアルゴリズムについて話します。グラフは、プログラミングにおいて最も柔軟で普遍的な構造の 1 つです。 グラフ G は通常、セットG = (V, R)のペアを使用して指定されます。ここで、

• V - 頂点のセット。
• Rは頂点のペアを接続する線のセットです。

一般的な接続線はエッジと呼ばれます。矢印のある線 -円弧:通常、グラフは、いくつかの頂点がエッジ (円弧) で接続されている図を使用して表されます。方向を直接示す円弧によって相互に接続されたグラフは、有向グラフと呼ばれます。グラフがエッジで接続されている場合、つまり、可能性のある動きの方向が示されていない場合、グラフは無向 になります。これは、頂点 A から B へ、および B から A への両方向で、それらに沿った移動が可能であることを意味します。 接続されたグラフとは、少なくとも 1 つのパスが各頂点から他の頂点につながるグラフです (例のように)その上 ）。そうでない場合、グラフは切断されます。また、エッジ (円弧) に重み、つまり 2 つの頂点間の物理的距離 (または 2 つの頂点間の遷移の相対時間) を表す数値を割り当てることができます。このようなグラフは重み付きと呼ばれます。

3. パス探索アルゴリズム（深さ、幅）

グラフに対して実行される基本操作の 1 つは、特定の頂点から到達可能なすべての頂点を決定することです。ある都市から別の都市に移動する可能性のある移動方法を判断しようとしていると想像してください。直接アクセスできる都市もあれば、他の都市を経由する必要がある都市もあります。特定の頂点からのパスを見つけることができるすべての頂点を見つける必要がある状況は他にもたくさんあります。したがって、グラフを走査するには、深さ優先走査と幅優先走査という2 つの主な方法があり、これらについて検討します。どちらの方法でも、接続されているすべての頂点を確実に反復します。深さ優先アルゴリズムと幅優先アルゴリズムをさらに詳しく検討するには、次のグラフを参照してください。

深さ優先トラバーサル

これは、最も一般的なグラフ走査方法の 1 つです。この深さ優先の検索戦略は、グラフを可能な限り「深く」進み、行き止まりに到達したときに、以前に訪問したことのない隣接する頂点を持つ最も近い頂点に戻ることで構成されます。このアルゴリズムは、デッドロックに達したときにどこに戻るかに関する情報をスタックに保存します。深さ優先トラバーサルのルール:

1. 隣接するまだ訪れていない頂点にアクセスし、マークを付けてスタックに置きます。
2. この頂点に移動します。
3. 手順 1 を繰り返します。
4. ステップ 1 を完了できない場合は、前の頂点に戻ってルール 1 を繰り返します。これが不可能な場合は、その前の頂点に戻り、以降のトラバースを続行できる頂点が見つかるまで同様に繰り返します。
5. すべての頂点がスタック上に配置されるまで続けます。

このアルゴリズムのコードが 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();
  }
}

コンソール出力: 隣接行列があり、walk メソッドではループ内にネストされたループを使用するため、時間計算量はO(N²)になります。

歩行幅

このアルゴリズムは、深さ優先探索と同様、グラフを探索するための最も単純かつ基本的な方法の 1 つです。その本質は、特定の現在の頂点があり、そこからすべての隣接する未通過の頂点をキューに入れ、次の要素 (キューに最初に格納されている) を選択してそれを現在の頂点にすることです。ステージでは、次のルールを強調表示できます。

1. 現在の頂点に隣接する、まだ訪問されていない次の頂点を訪問し、事前にマークしてキューに追加します。
2. ルール #1 を満たすことができない場合は、キューから頂点を削除し、それを現在の頂点にします。
3. ルール #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();
  }
}

コンソール出力: 繰り返しになりますが、隣接行列があり、ループ内にネストされたループを使用しているため、O(N²)が上記のアルゴリズムの時間計算量となります。

4. ダイクストラのアルゴリズム

前述したように、グラフは有向または無向の場合があります。覚えているとおり、それらは依然として重み付けできます。重み付けされた有向グラフは、現実の世界でよく見られます。たとえば、都市の地図では、都市が頂点であり、それらの間の経路が道路であり、道路には一方通行が存在する場合があります。つまり、グラフの方向です。貨物輸送に従事しており、遠く離れた 2 つの都市間の最短ルートを作成する必要があるとします。どうやってやりますか？重み付きグラフに関する最も一般的な問題の 1 つは、2 つの頂点間の最短パスを選択する問題です。この問題を解決するために、ダイクストラのアルゴリズムを使用します。ダイクストラのアルゴリズムを実行すると、与えられた最初の頂点からすべての頂点への最短パスが見つかることにすぐに注目したいと思います。このアルゴリズムにはどのような段階がありますか? この質問に答えてみます。 ダイクストラのアルゴリズムの段階:

• ステージ 1 : 移行コストが最小となるノードを検索します。あなたはまさに先頭に立って、ノードAに行くかノードBに行くか、どこに行けばよいのか迷っています。これらの各ノードに到達するのにどれくらい時間がかかりますか?
• ステージ 2 : Bからエッジに沿って移動するときに、まだアルゴリズムの影響を受けていないB のすべての近傍に到達するのにかかる時間を計算します。この新しい時間が古い時間よりも短いことが判明した場合、エッジ B を通るパスがこの頂点の新しい最短パスになります。
• ステージ 3 : 頂点 B を合格としてマークします。
• ステップ 4 : ステップ 1 に進みます。

すべてのピークが通過するまで、これらの段階のサイクルを繰り返します。次の重み付き有向グラフを考えてみましょう。したがって、上記のアルゴリズムを使用して、A から G への最短経路を決定します。

1. 頂点Aには、重み 3 のBへ、重み 5 のCへ、重み 7 のDへの 3 つのパスが考えられます。アルゴリズムの最初のポイントに従って、遷移が最も低いノードを選択します。コスト - つまりBに。
2. Bの唯一の未通過の隣接頂点は頂点Eであるため、この頂点を通過するときにパスがどのようになるかを確認します。3( AB ) + 6( BE ) = 9。

   したがって、AE への現在の最短経路は 9 であることがわかります。

3. 頂点Bでの作業はすでに完了しているため、その前のエッジの重みが最小である次の頂点の選択に進みます。

   頂点AとBから、これらは頂点D (7)、C (5)、E (6)になります。

   Cのエッジの重みが最小であるため、この頂点に進みます。

4. 次に、前と同様に、C を通過するときに隣接する頂点への最短パスを見つけます。
   • AD = 5( AC ) + 3( CD ) = 8 ですが、前の最短パスAC = 7、つまりCを通る今回の最短パスより短いため、最短パスAD = 7 を変更しないままにします。
   • CE = 5( AC ) + 4( CE ) = 9、この新しい最短パスは前のパスと等しいため、これも変更しないままにします。
5. 最も近い利用可能な頂点EとDから、エッジの重みが最小の頂点、つまりD (3) を選択します。
6. その隣のFへ の最短経路を見つけます。

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

7. 最も近い利用可能な頂点EおよびFから、エッジの重みが最も小さい頂点、つまりF (3) を選択します。
8. その隣のGへ の最短経路を見つけます。

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

   実際、ここでAからGへの道が見つかりました。

   ただし、それが最短であることを確認するには、頂点Eに対してもステップを実行する必要があります。

9. 頂点G には有向パスがつながる隣接頂点がないため、頂点Eだけが残り、それを選択します。
10. 隣人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();
   }
}

そしてコンソールの出力は次のようになります。 ループ内にループがネストされているため、このアルゴリズムの時間計算量はO(N²) にすぎません。それでは、今日はここまでです、ご清聴ありがとうございました！