16.GraphMinPath/src/dijkstra/Graph.java - master - akoub/algo

16.GraphMinPath/src/dijkstra/Graph.java
70 строк2 KB
Alexander Kubenskiy
Renaming
14 дек 2018, 13:25
14 дек 2018, 13:2537586fe
package dijkstra;

import java.util.ArrayList;
import java.util.List;

/**
 * Представление нагруженного графа списками смежности.
 * Нагрузка на дуги - вещественные числа ("длина дуги").
 */
public class Graph {
	/**
	 * Представление дуги графа
	 */
	public static class Arc {
		double weight;	// Нагрузка на дугу
		int to;			// Номер вершины, в которую ведет дуга

		public Arc(int to, double info) {
			this.to = to; this.weight = info;
		}
		
		public double weight() { return weight; }
		
		public int to() { return to; }
	};

	private final List<Arc>[] lGraph;	// Списки смежности
	private final int nVertex;			// Число вершин

	/**
	 * Конструктор пустого графа с заданным числом вершин
	 * @param nVert Число вершин
	 */
	@SuppressWarnings("unchecked")
	public Graph(int nVert) {
		lGraph = new List[nVert];
		for (int i = 0; i < nVert; ++i) {
			lGraph[i] = new ArrayList<Arc>();
		}
		nVertex = nVert;
	}
	
	/**
	 * Число вершин графа
	 * @return
	 */
	public int getCount() { return nVertex; }

	/**
	 * Добавление дуги в граф. Предполагается, что ранее такой дуги в графе не было.
	 * @param from	Начало дуги (номер вершины)
	 * @param to	Конец дуги (номер вершины)
	 * @param info	Нагрузка на дугу
	 */
	public void addArc(int from, int to, double info) {
		assert from < nVertex && from >= 0;
		assert to < nVertex && to >= 0;
		
		lGraph[from].add(new Arc(to, info));
	}
	
	/**
	 * Итератор дуг, ведущих из заданной вершины
	 * @param u	Исходная вершина
	 * @return
	 */
	public Iterable<Arc> arcs(int u) {
		return lGraph[u];
	}
}