图1：图的表示与存储
在图论中，图 (graph) 是一个二元组 G=(V(G), E(G))。其中 V(G) 是非空集，称为 点集 (vertex set)，对于 V 中的每个元素，我们称其为 顶点 (vertex) 或 节点 (node)，简称 点；E(G)为 V(G) 各结点之间边的集合，称为 边集 (edge set)。常用 G=(V,E) 表示图。
图（Graph）是一种由顶点（vertex）和边（edge）组成的非线性数据结构。
在图中，元素被称为顶点，元素与元素之间的关系可以连线表示，被称为边。图中每个顶点和其他顶点连接的边的数量，被称为这个顶点的度（degree）。
边是可以由方向的，边有方向的图被称为有向图，边没有方向的图被称为无向图。这就好比微信的好友关系，对方在你的好友列表，而对方可能已经把你拉黑了，这个好友关系是有方向的。
在有向图中，度分为入度（in-degree）和出度（out-degree）。顶点的入度，表示有多少条边指向这个顶点；顶点的出度，表示有多少条边是以这个顶点为起点指向其他顶点。对应到微博的例子，入度就表示有多少粉丝，出度就表示关注了多少人。
边也是可以权重（weight）的，在Soul这个陌生人社交软件中，随着你们互动的增多，点亮的字母也会越来越多，也就是说亲密度越来越高。边带有权重的图称为带权图（weighted graph）或者加权图。
图中顶点的数量被称为阶（Order）。由顶点A到B所经过的顶点序列，被称为路径（Path），如果路径中第一个顶点和最后一个顶点相同，则此路径称为回路（circuit），有时也称为环（cycle）。若一张图的边数远小于其点数的平方，那么它是一张 稀疏图 (sparse graph)。若一张图的边数接近其点数的平方，那么它是一张 稠密图 (dense graph)。
为了方便实现图，定义接口如下：
package cn.lishiyuan.algorithm.graph;
/**
* 图
* @param <V>
*/
public interface Graph<V> extends GraphSearch<V>{
/**
* 图类型
*/
enum GraphType{
// 无向图
GRAPH,
// 有向图
DIGRAPH,
}
/**
* 添加一条边
* @param from
* @param to
* @param weight
*/
void addEdge(V from, V to, int weight);
/**
* 添加一条边
* @param from
* @param to
*/
void addEdge(V from, V to);
/**
* 移除一条边
* @param from
* @param to
*/
void removeEdge(V from, V to);
/**
* 获取从from到to的边的权重
* @param from
* @param to
* @return
*/
int getWeight(V from, V to);
/**
* 检查边是否存在
* @param from
* @param to
* @return
*/
boolean existsEdge(V from, V to);
/**
* 顶点的入度
* @param vertex
* @return
*/
int getInDegree(V vertex);
/**
* 顶点的出度
* @param vertex
* @return
*/
int getOutDegree(V vertex);
/**
* 获取顶点的数量
* @return
*/
int getVertexCount();
/**
* 获取边的数量
* @return
*/
int getEdgeCount();
}邻接矩阵
图的表示和存储最直接的方式是使用邻接矩阵（Adjacency Matrix）。
邻接矩阵底层依赖一个二维数组存储顶点之间的边，比如下面就表示一个有10个顶点组成的图的边：
[[1,0,1,1,1,1,1,1,1,1],
[1,1,1,1,1,1,1,1,1,1],
[1,0,1,1,1,1,1,1,1,1],
[1,0,1,1,1,1,1,1,1,1],
[1,0,1,1,1,1,1,1,1,1],
[1,0,1,1,1,1,1,1,1,1],
[1,0,1,1,1,1,1,1,1,1],
[1,0,1,1,1,1,1,1,1,1],
[1,0,1,1,1,1,1,1,1,1],
[1,0,1,1,1,1,1,1,1,1]]对于无向图，如果顶点i和j之间存在边，则将G[i][j]和G[j][i]的值设置为1，如果没有则设置为0。对于有向图，如果顶点 i 朝向 j 有边，而j朝向i没有边，则将G[i][j]设置为1，将G[j][i] 设置为0。对于带权图，则将对应的边设置为其权重，比如G[i][j]设置为5。
从上面的图中可以看出就index=1这个顶点朝向所有其他顶点有边，而其他顶点朝向index=1这个顶点都没有边。可以看出来这是一个有向图。
实现如下：
package cn.lishiyuan.algorithm.graph;
import java.util.*;
/**
* 邻接矩阵
*
*/public class AdjacencyMatrix<V> implements Graph<V>{
/**
* 顶点,可以使用 Map 存储元素与index的关系
*/
private V[] vertices;
/**
* 边
*/
private int[][] edges;
private GraphType type;
public AdjacencyMatrix(V[] vertices,GraphType type) {
if (vertices==null || vertices.length == 0){
throw new IllegalArgumentException("vertices is null or empty");
}
if (type == null){
throw new IllegalArgumentException("type is null");
}
for (V vertex : vertices) {
if (vertex == null) throw new IllegalArgumentException("vertex is null");
}
this.vertices = vertices;
this.edges = new int[vertices.length][vertices.length];
for (int i=0;i<this.vertices.length;i++){
for (int j=0;j<this.vertices.length;j++){
edges[i][j] = 0;
}
}
this.type = type;
}
@Override
public void addEdge(V from, V to, int weight) {
// 查找对应元素的位置
if (weight <= 0){
throw new IllegalArgumentException("权重不能小于0");
}
int fromIndex = indexOfVertex(from);
int toIndex = indexOfVertex(to);
if (fromIndex == -1 || toIndex == -1){
throw new IllegalArgumentException("顶点不存在");
}
if(type == GraphType.GRAPH){
// 无向图
edges[fromIndex][toIndex] = weight;
edges[toIndex][fromIndex] = weight;
}else {
// 有向图
edges[fromIndex][toIndex] = weight;
}
}
@Override
public void addEdge(V from, V to) {
addEdge(from, to, 1);
}
@Override
public void removeEdge(V from, V to) {
int fromIndex = indexOfVertex(from);
int toIndex = indexOfVertex(to);
if (fromIndex == -1 || toIndex == -1){
throw new IllegalArgumentException("顶点不存在");
}
if(type == GraphType.GRAPH){
// 无向图
edges[fromIndex][toIndex] = 0;
edges[toIndex][fromIndex] = 0;
}else {
// 有向图
edges[fromIndex][toIndex] = 0;
}
}
@Override
public int getWeight(V from, V to) {
int fromIndex = indexOfVertex(from);
int toIndex = indexOfVertex(to);
if (fromIndex == -1 || toIndex == -1){
throw new IllegalArgumentException("顶点不存在");
}
return edges[fromIndex][toIndex];
}
@Override
public boolean existsEdge(V from, V to) {
int fromIndex = indexOfVertex(from);
int toIndex = indexOfVertex(to);
if (fromIndex == -1 || toIndex == -1){
throw new IllegalArgumentException("顶点不存在");
}
return edges[fromIndex][toIndex] != 0;
}
@Override
public int getInDegree(V vertex) {
int index = indexOfVertex(vertex);
if (index == -1){
throw new IllegalArgumentException("顶点不存在");
}
int degree = 0;
for (int i=0;i<vertices.length;i++){
if(i!=index && edges[i][index] > 0){
degree++;
}
}
return degree;
}
@Override
public int getOutDegree(V vertex) {
int index = indexOfVertex(vertex);
if (index == -1){
throw new IllegalArgumentException("顶点不存在");
}
int degree = 0;
for (int i=0;i<vertices.length;i++){
if(i!=index && edges[index][i] > 0){
degree++;
}
}
return degree;
}
@Override
public int getVertexCount() {
return vertices.length;
}
@Override
public int getEdgeCount() {
int edgeCount = 0;
for (int i=0;i<vertices.length;i++){
for (int j=0;j<vertices.length;j++){
if (i!=j && edges[i][j] > 0){
edgeCount++;
}
}
}
if (type == GraphType.GRAPH){
// 一半
edgeCount = edgeCount / 2;
}
return edgeCount;
}
@Override
public List<V> search(V from, V to) {
if(Objects.isNull(from) || Objects.isNull(to)){
throw new IllegalArgumentException("顶点不能为空");
}
int fromIndex = indexOfVertex(from);
int toIndex = indexOfVertex(to);
if (fromIndex == -1 || toIndex == -1){
throw new IllegalArgumentException("顶点不存在");
}
if(Objects.equals(from,to)){
return Collections.singletonList(from);
}
List<V> result = new ArrayList<>();
if (type == GraphType.GRAPH){
// 只要有连接就行
}else {
}
return result;
}
// 深度优先搜索
private void dfs(int from, int to,List<Integer> path){
for (int i = 0;i < vertices.length;i++){
}
}
/**
* 转换成邻接表
* @return
*/
public AdjacencyList<V> transfer(){
Set<V> data = new HashSet<>(Arrays.asList(vertices));
AdjacencyList<V> adjacencyList = new AdjacencyList<>(data,type);
for (V v : data) {
int i = indexOfVertex(v);
for (int j = 0;j < vertices.length;j++){
if(i != j && edges[i][j] > 0){
V to = vertices[j];
adjacencyList.addEdge(v, to, edges[i][j]);
}
}
}
return adjacencyList;
}
private int indexOfVertex(V v){
for(int i=0;i<vertices.length;i++){
if(v.equals(vertices[i])){
return i;
}
}
return -1;
}
}邻接矩阵的优点是特别直观，结构也比较简单，在需要做矩阵运算的时候十分方便。但是空间复杂度比较高，一个由于n个顶点的图，需要构建一个n²的二维表，在存储稀疏矩阵也就是稀疏图的时候会浪费大量的空间。
邻接表
为了解决邻接矩阵的诸多问题，我们可以只存储有关系的边，类似一个哈希表结构。
实现如下：
package cn.lishiyuan.algorithm.graph;
import java.util.*;
/**
* 邻接表
*/
public class AdjacencyList<V> implements Graph<V> {
// 顶点
private Set<V> vertices;
// 边
private Map<V,Map<V,Integer>> edges;
private GraphType type;
public AdjacencyList(Set<V> nodes,GraphType type) {
if (nodes == null || nodes.isEmpty()){
throw new IllegalArgumentException("nodes is null or empty");
}
if (type == null){
throw new IllegalArgumentException("type is null");
}
this.type = type;
this.vertices = new HashSet<>(nodes);
this.edges = new HashMap<>();
}
@Override
public void addEdge(V from, V to, int weight) {
boolean fromExists = this.vertices.contains(from);
boolean toExists = this.vertices.contains(to);
if (!fromExists || !toExists){
throw new IllegalArgumentException("顶点不存在");
}
// 有向图
Map<V,Integer> toEdges = this.edges.getOrDefault(from,new HashMap<>());
toEdges.put(to,weight);
this.edges.put(from,toEdges);
if(type == GraphType.GRAPH){
// 无向图
Map<V, Integer> fromEdges = this.edges.getOrDefault(to, new HashMap<>());
fromEdges.put(from,weight);
this.edges.put(to,fromEdges);
}
}
@Override
public void addEdge(V from, V to) {
addEdge(from, to, 1);
}
@Override
public void removeEdge(V from, V to) {
boolean fromExists = this.vertices.contains(from);
boolean toExists = this.vertices.contains(to);
if (!fromExists || !toExists){
throw new IllegalArgumentException("顶点不存在");
}
// 有向图
Map<V,Integer> toEdges = this.edges.getOrDefault(from,new HashMap<>());
toEdges.remove(to);
this.edges.put(from,toEdges);
if(type == GraphType.GRAPH){
// 无向图
Map<V, Integer> fromEdges = this.edges.getOrDefault(to, new HashMap<>());
fromEdges.remove(from);
this.edges.put(to,fromEdges);
}
}
@Override
public int getWeight(V from, V to) {
boolean fromExists = this.vertices.contains(from);
boolean toExists = this.vertices.contains(to);
if (!fromExists || !toExists){
throw new IllegalArgumentException("顶点不存在");
}
Map<V,Integer> toEdges = this.edges.getOrDefault(from,new HashMap<>());
return toEdges.getOrDefault(to, 0);
}
@Override
public boolean existsEdge(V from, V to) {
return getWeight(from,to) > 0;
}
@Override
public int getInDegree(V vertex) {
if (!this.vertices.contains(vertex)){
return 0;
}
int degree = 0;
if (type == GraphType.GRAPH){
Map<V, Integer> toEdges = edges.getOrDefault(vertex, new HashMap<>());
degree = toEdges.size();
}else {
for (V v : vertices) {
if (v.equals(vertex)){
continue;
}
Map<V,Integer> edgeSet = edges.getOrDefault(v, new HashMap<>());
if (edgeSet.containsKey(vertex)){
degree ++;
}
}
}
return degree;
}
@Override
public int getOutDegree(V vertex) {
if (!this.vertices.contains(vertex)){
return 0;
}
Map<V,Integer> edgeSet = edges.getOrDefault(vertex, new HashMap<>());
return edgeSet.size();
}
@Override
public int getVertexCount() {
return vertices.size();
}
@Override
public int getEdgeCount() {
int edgeCount = 0;
for (Map<V,Integer> edgeSet : edges.values()){
edgeCount += edgeSet.size();
}
// 无向图边除以2
if (type == GraphType.GRAPH){
edgeCount = edgeCount / 2;
}
return edgeCount;
}
@Override
public List<V> search(V from, V to) {
return List.of();
}
// 广度优先搜索
private void bfs(V from, V to,List<V> path){
}
/**
* 转换成邻接矩阵
* @return
*/
public AdjacencyMatrix<V> transfer(){
V[] data = vertices.toArray((V[]) new Object[0]);
AdjacencyMatrix<V> adjacencyMatrix = new AdjacencyMatrix<V>(data,type);
for (V v : data) {
Map<V,Integer> edgeSet = edges.getOrDefault(v, new HashMap<>());
for (Map.Entry<V, Integer> entry : edgeSet.entrySet()) {
adjacencyMatrix.addEdge(v,entry.getKey(),entry.getValue());
}
}
return adjacencyMatrix;
}
}这里我使用一个Map存储边，key是顶点，value是一个Map，其key是关联的节点，其value是权重。由于邻接表只存储出方向的边信息，大多是时候可以为了提高效率，可以构建一个逆向邻接表用来存储入方向的边信息。