パッケージ library.graph

クラス Graph

java.lang.Object
java.util.AbstractCollection<ArrayList<Edge>>
java.util.AbstractList<ArrayList<Edge>>
java.util.ArrayList<ArrayList<Edge>>
library.graph.Graph
すべての実装されたインタフェース:
Serializable, Cloneable, Iterable<ArrayList<Edge>>, Collection<ArrayList<Edge>>, List<ArrayList<Edge>>, RandomAccess, SequencedCollection<ArrayList<Edge>>
public class Graph extends ArrayList<ArrayList<Edge>>
グラフクラス
関連項目:

  • コンストラクタの詳細

    • Graph

      public Graph(int n, int indexed, boolean undirected, boolean weighted)
      コンストラクタ
      パラメータ:
      n - 頂点の個数
      indexed - ?-indexed 0-indexedなら0, 1-indexedなら1
      undirected - 無向グラフかどうか 無向グラフならtrue, 有向グラフならfalse
      weighted - 重みつきかどうか 重みつきならtrue, 重みなしならfalse

  • メソッドの詳細

    • of

      public static Graph of(List<ArrayList<Edge>> g, boolean undirected, boolean weighted)
      グラフ化する
      パラメータ:
      g -
      undirected -
      weighted -
      戻り値:
      List入力が無効です: '<'ArrayList>をWeightedGraph化したもの

    • addEdge

      public final void addEdge(int a, int b)
      辺を追加する
      パラメータ:
      a -
      b -

    • addEdge

      public final void addEdge(int a, int b, long cost)
      重みつきの辺を追加する
      パラメータ:
      a -
      b -
      cost -

    • input

      public final void input(int m)
      辺をm個入力する
      パラメータ:
      m - 辺の個数

    • getEdge

      public final Edge[] getEdge()
      辺の配列を返す
      戻り値:
      辺の配列

    • toArray

      public final int[][] toArray()
      グラフを二次元配列にして返す
      定義:
      toArray インタフェース内 Collection<ArrayList<Edge>>
      定義:
      toArray インタフェース内 List<ArrayList<Edge>>
      オーバーライド:
      toArray クラス内 ArrayList<ArrayList<Edge>>
      戻り値:
      二次元配列にしたグラフ

    • allDist

      public final int[] allDist(int v)
      BFSをして頂点vから各頂点に対する距離を求める
      パラメータ:
      v -

    • dist

      public final int dist(int u, int v)
      頂点uと頂点vとの距離
      パラメータ:
      u -
      v -
      戻り値:
      頂点uと頂点vとの距離

    • topologicalSort

      public final ArrayList<Integer> topologicalSort()
      トポロジカルソート

    • cycleDetector

      public final int[] cycleDetector()
      サイクル検出
      戻り値:
      サイクル if non-existence: 空配列

    • diameter

      public final long diameter()
      path(直径を構成する辺)を構築する
      戻り値:
      木の直径

    • getPath

      public final Edge[] getPath()
      pathを返す
      戻り値:
      直径を構成する辺

    • dijkstra

      public final ShortestPath dijkstra(int v)
      Dijkstra法 負辺のないグラフで単一始点全点間最短路を求める
      パラメータ:
      v -

    • spfa

      public final long[] spfa(int v)
      Shortest Path Faster Algorithm 負辺が存在していても単一始点全点間最短路を求められる 負閉路も検出する
      パラメータ:
      v -

    • floydWarshall

      public final long[][] floydWarshall()
      Floyd-Warshall法 全点対間最短路を求める

    • kruskal

      public final MST kruskal()
      Kruskal法によって最小全域木を求める

    • directed

      public final MST directed(int v)
      最小有向全域木を求める
      パラメータ:
      v -
      関連項目:

    • toString

      public String toString()
      オーバーライド:
      toString クラス内 AbstractCollection<ArrayList<Edge>>