1、文章背景

一直以来，在java的应用中，我对图的研究不是很多，这次有一个加拿大的留学生遇到了一个研究图的题目。我准备以一系列的文章来描述一下这个项目。希望对各位面试大厂算法题的时候能有所裨益。本篇文章先对项目简单做个介绍，起到抛砖引玉的作用。

2、原文介绍

原文对于项目背景的介绍如下，每段后面附上我自己的见解：

A graph is a set of vertices and a set of edges. A vertex is also called a node. An edge represents a connection between a pair of vertices. Edges can be associated with a length or a weight. Graphs can be used to represent a variety of data including navigational maps (and graph algorithms are used to find routes between two places on a map, for instance).

这段介绍了一下图，主要说明，图是由顶点和边组成。顶点也叫节点，边则是一对顶点之间的连接。每个边上可以关联一个长度或者一个权重值。图可以用于表示包括地图导航的许多数据。比如，图的这些算法经常用来查找地图上两个位置之间的路径。

注1：顶点和顶点的连接可以有向，也可以无向。从后面题目给出的部分代码来看，本项目涉及到的应该是无向图。

注2：图的各个顶点之间可以联通，也可能不联通，分别叫做联通图和非联通图，从后面题目看来，本案例的图指的是联通图。

Graphs are commonly represented using either an adjacency list or an adjacency matrix. (You can choose to represent a graph in any way that you deem appropriate.) All your implementation for concerning graphs should be in the cpen221.mp2.graph package.

图通常可用邻接表和邻接矩阵来表示。具体可以自行选择。所有的实现放在指定的包中。

注1：邻接表和邻接矩阵是两个维基的链接。

注2：邻接表和邻接矩阵是后面题目要求的代码，这里不展开解释，借用两张图，大家一看便懂。

添加图片注释，不超过 140 字（可选）

添加图片注释，不超过 140 字（可选）

You will start by implementing the IGraph interface using two concrete types: (i) ALGraph, which uses an adjacency list representation, and (2) AMGraph, which uses the adjacency matrix representation.

这里给你写了一个接口，提供了一些图的基本操作，让你分别用邻接表和邻接矩阵去实现。

You should strengthen the specifications for as many methods as possible in your implementation relative to the specifications in IGraph interface without breaking any of the provided skeleton code.

这段的意思是你可以增强功能，但是不要改他提供的代码。

Popular algorithms — such as Dijkstra's shortest path algorithm — require some specialized data structures but you can pick other data abstractions that are sufficient for solving the problem.

这里提到了迪杰特斯拉算法，但是他说你使用别的数据结构也可以实现该算法。

Dijkstra 算法，是Edsger Wybe Dijkstra 在1956年发现的算法，迪克斯特拉算法使用类似广度优先搜索的方法解决赋权图的单源最短路径问题。Dijkstra 算法原始版本仅适用于找到两个顶点之间的最短路径，后来更常见的变体固定了一个顶点作为源结点然后找到该顶点到图中所有其它结点的最短路径，产生一个最短路径树。本算法每次取出未访问结点中距离最小的，用该结点更新其他结点的距离。需要注意的是绝大多数的Dijkstra 算法不能有效处理带有负权边的图。

迪克斯特拉算法属于贪婪算法。

Dijkstra 算法的⼯作原理是逐个访问图中的顶点，同时跟踪记录从起始顶点到所有其他顶点的当前最短距离，并不断更新这些最短距离。更具体地说，该算法跟踪记录未访问的顶点并在任何时间点以最短的距离访问未访问的顶点，⾃然是从起始顶点开始。每当算法访问⼀个未访问的顶点时，它会查看其所有出站边，并尝试更新从起点到边中⽬的地的最短距离，使⽤到当前顶点的当前最短距离作为基础。⼀旦算法访问 了所有顶点并考虑了它们的所有边，就可以保证找到到每个顶点的最短路径。

Dijkstra 算法中最具挑战性的部分是确定如何有效地找到当前距离最短的顶点。

具体的做法可以是：创建一个数组，该数组可以存储起始顶点和所有其他顶点之间的最终最短距离，以及一个最小堆，该堆将保存所有未访问的顶点及其当前最短距离。对于最终距离数组和最小堆，初始化除起始节点外的所有顶点，使其具有无穷远的距离；开始节点的距离为0。接下来，编写一个循环，该循环将一直运行，直到最小堆为空。在循环的每次迭代中，从堆的顶部移除顶点（距离最短的顶点），循环通过其所有边，对于每条边，将目标顶点的最短距离更新为目标的当前最短距离和当前访问顶点的距离加上当前边的权重的最小值。一旦堆为空，所有顶点都将被访问，到所有顶点的最短距离将存储在距离数组中。代码实现可以参考附件。

Your graph implementation uses generics that allow for reuse. The Edge type has been implemented to give you some examples for working with generics.

这里告诉你可以用泛型来实现，他已经写好了Edge这个类，提供了一些例子供参考。

好了，这是项目背景，下一篇文章我们来讨论接口和具体的实现方案。

附：迪杰特斯拉算法参考实现：（算法摘抄至千锋教育数据结构和算法笔记）

package com.qf.algorithm;

import com.alibaba.fastjson.JSON;

import com.alibaba.fastjson.JSONArray;

import com.alibaba.fastjson.JSONObject;

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.*;

public class Dijkstra {

public static void main(String[] args) throws IOException {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

String input = br.readLine();

List<Object> data = parseData(input);

int start = (int) data.get(0);

int[][][] edges = (int[][][]) data.get(1);

int[] result = dijkstrasAlgorithm(start, edges);

System.out.println(Arrays.toString(result));

}

public static int[] dijkstrasAlgorithm(int start, int[][][] edges) {

int numberOfVertices = edges.length;

int[] minDistances = new int[numberOfVertices];

Arrays.fill(minDistances, Integer.MAX_VALUE);

minDistances[start] = 0;

List<Item> minDistancesPairs = new ArrayList<Item>();

for (int i = 0; i < numberOfVertices; i++) {

Item item = new Item(i, Integer.MAX_VALUE);

minDistancesPairs.add(item);

}

MinHeap minDistancesHeap = new MinHeap(minDistancesPairs);

minDistancesHeap.update(start, 0);

while (!minDistancesHeap.isEmpty()) {

Item heapItem = minDistancesHeap.remove();

int vertex = heapItem.vertex;

int currentMinDistance = heapItem.distance;

if (currentMinDistance == Integer.MAX_VALUE) {

break;

}

for (int[] edge : edges[vertex]) {

int destination = edge[0];

int distanceToDestination = edge[1];

int newPathDistance = currentMinDistance + distanceToDestination;

int currentDestinationDistance = minDistances[destination];

if (newPathDistance < currentDestinationDistance) {

minDistances[destination] = newPathDistance;

minDistancesHeap.update(destination, newPathDistance);

}

}

}

int[] finalDistances = new int[minDistances.length];

for (int i = 0; i < minDistances.length; i++) {

int distance = minDistances[i];

if (distance == Integer.MAX_VALUE) {

finalDistances[i] = -1;

} else {

finalDistances[i] = distance;

}

}

return finalDistances;

}

public static List<Object> parseData(String json) {

List<Object> data = new ArrayList<>();

JSONObject jsonObject = JSON.parseObject(json);

int size = jsonObject.getInteger("start");

data.add(size);

JSONArray jsonArray = jsonObject.getJSONArray("edges");

int[][][] edges = new int[jsonArray.size()][][];

for (int i = 0; i < jsonArray.size(); i++) {

JSONArray jsonArray2 = jsonArray.getJSONArray(i);

edges[i] = new int[jsonArray2.size()][];

for (int j = 0; j < jsonArray2.size(); j++) {

JSONArray jsonArray3 = jsonArray2.getJSONArray(j);

edges[i][j] = new int[jsonArray3.size()];

for (int k = 0; k < jsonArray3.size(); k++) {

edges[i][j][k] = jsonArray3.getInteger(k);

}

}

}

data.add(edges);

return data;

}

static class Item {

int vertex;

int distance;

public Item(int vertex, int distance) {

this.vertex = vertex;

this.distance = distance;

}

}

static class MinHeap {

Map<Integer, Integer> vertexMap = new HashMap<Integer, Integer>();

List<Item> heap = new ArrayList<Item>();

public MinHeap(List<Item> array) {

for (int i = 0; i < array.size(); i++) {

Item item = array.get(i);

vertexMap.put(item.vertex, item.vertex);

}

heap = buildHeap(array);

}

List<Item> buildHeap(List<Item> array) {

int firstParentIdx = (array.size() - 2) / 2;

for (int currentIdx = firstParentIdx + 1; currentIdx >= 0; currentIdx--) {

siftDown(currentIdx, array.size() - 1, array);

}

return array;

}

boolean isEmpty() {

return heap.size() == 0;

}

void siftDown(int currentIdx, int endIdx, List<Item> heap) {

int childOneIdx = currentIdx * 2 + 1;

while (childOneIdx <= endIdx) {

int childTwoIdx = currentIdx * 2 + 2 <= endIdx ? currentIdx * 2 + 2 : -1;

int idxToSwap;

if (childTwoIdx != -1 && heap.get(childTwoIdx).distance < heap.get(childOneIdx).distance) {

idxToSwap = childTwoIdx;

} else {

idxToSwap = childOneIdx;

}

if (heap.get(idxToSwap).distance < heap.get(currentIdx).distance) {

swap(currentIdx, idxToSwap);

currentIdx = idxToSwap;

childOneIdx = currentIdx * 2 + 1;

} else {

return;

}

}

}

void siftUp(int currentIdx) {

int parentIdx = (currentIdx - 1) / 2;

while (currentIdx > 0 && heap.get(currentIdx).distance < heap.get(parentIdx).distance) {

swap(currentIdx, parentIdx);

currentIdx = parentIdx;

parentIdx = (currentIdx - 1) / 2;

}

}

Item remove() {

if (isEmpty()) {

return null;

}

swap(0, heap.size() - 1);

Item lastItem = heap.get(heap.size() - 1);

int vertex = lastItem.vertex;

int distance = lastItem.distance;

heap.remove(heap.size() - 1);

vertexMap.remove(vertex);

siftDown(0, heap.size() - 1, heap);

return new Item(vertex, distance);

}

void update(int vertex, int value) {

heap.set(vertexMap.get(vertex), new Item(vertex, value));

siftUp(vertexMap.get(vertex));

}

void swap(int i, int j) {

vertexMap.put(heap.get(i).vertex, j);

vertexMap.put(heap.get(j).vertex, i);

Item temp = heap.get(i);

heap.set(i, heap.get(j));

heap.set(j, temp);

}

}

}