Javaでのグラフ実装例

この記事では、Javaでのグラフ実装例をゼロから表示します.Javaでグラフデータ構造を作成し、使用する方法を学びます.実際の演習では、多くのインタビュープロセスで見てきました.
この例は、エキサイティングで挑戦的な問題を解決することです.まず、Javaで問題を解決し、解決する方法を紹介します.

問題

配達サービス会社は、顧客注文を届けるために配達トラックのためにルートを計画するシステムをつくります.プランナーは、グリッドとして抽象化されている各注文の配信領域を作成します.課題は、トラックの順序を提供するためのパスを見つけるためにアルゴリズムを書くことです.
配信エリアは、次の整数の2次元グリッドとして表されます.

は、アクセス可能領域

を表す

は、非アクセス可能エリア

を表す

は、注文先

を表します
この演習は、正しいデータ構造を使用する方法をはるかに簡単に何かに複雑な問題を変えることができるJavaの優れた例です.グラフの実装を使用すると、問題がより簡単になります.
いくつかのものを開始する前に考慮する必要があります.トラックはグリッドを離れることができず、アクセス可能な領域を介して注文先に到達する必要があります.そして、トラックは一度に一つのセル、下、左、または右に移動することができます.
入力と対応する出力の異なる場合の例をいくつか示します.

  Example 1
  grid = [[1,1,0],[0,1,2][0,1,1]]
  Output: [0,0][0,1][1,1][2,1][2,2][1,2]

  Example 2
  grid = [[1,1,1,1],[0,1,0,1],[0,1,0,1],[0,1,1,0],[0,1,2,1]]
  Output: [0,0][0,1][1,1][2,1][3,1][3,2]

解決策

この問題に対する最良の解決策は、Javaグラフ実装を使用しています.一般的に、グラフは、グリッドをナビゲートする必要があるすべての状況のための適切なソリューションです.
この解決策は、各マトリックスセルを表すCellクラスと、トラックが移動する領域を表すDeliveryAreaという2つのクラスを持つことになる.下記のスケルトン、ちょうどクラスとメソッド署名を見てください.次のセクションで実装を完了します.

public class Cell {
    public int row;
    public int col;

    public Cell(int row, int col){
        this.row = row;
        this.col = col;
    }

    public String hashKey(){
        return String.valueOf(this.row)+String.valueOf(this.col);
    }
}

import java.util.List;
import java.util.Map;

public class DeliveryArea {

    private final static int ACCESSIBLE_CELL = 1;
    private final static int NON_ACCESSIBLE_CELL = 0;
    private final static int DESTINATION = 2;

    public int[][] matrix;

    public DeliveryArea(int[][] matrix){
        this.matrix = matrix;
    }
    private Map<String, List<Cell>> buildGraph(){
        return null;
    }
    public List<Cell> findRoute(){
        return null;
    }
}

Check out the full solution