数据结构与算法--图的实现（邻接表、邻接矩阵、边的数组）
应该用哪种数据结构实现图呢？主要有如下三种：
邻接矩阵
对一个拥有V个顶点的图，建立一个V*V的布尔数组，如果顶点i到j之间有边连接，则定义i行j列的元素值为true，否则为false，如果是带有权值的图，那么将true改成相应的权值，false改成一个不太可能出现的值比如Integer.MAX_VALUE。还可以专门用一个数组或者表，用来存放顶点信息，因为我们直接用0~N - 1的值代表了每个顶点，但这些数值具体指代了什么意思可以去顶点信息数组查找。不过邻接矩阵表示对于顶点数目很多（比如上百万）的图，N*N个值的空间是不能满足的。
如上，左边的无向图可以转换成右边的邻接矩阵。顶点0~3的信息存在顶点信息数组里。由于这里用的是大话数据结构（C语言）中的图，0其实就是false，1就是true。顶点v0和v1有边相连，所以在矩阵中a[0][1]和a[1][0]的值为true，而v1和v3之间没有边相连所以a[1][3]和a[3][1]为false。仔细观察可以发现主对角线的值全是0，这是因为我们讨论的是简单图，暂时不考虑自环的情况。以主对角线为对称轴，矩阵左下a[i][j]和对应右上的a[j][i]值是一样的，这其实是一个对称矩阵。通过邻接矩阵，我们还可以获得一些其他信息。
- 某个顶点i的度其实就是矩阵中
a[i]那行中true的个数。 - 与顶点i相邻的顶点就是矩阵中
a[i]那行中所有值为true的列下标。
邻接矩阵对于有向图也适用，只是矩阵不再是对称矩阵了。
如图v0到v3有路径，所以a[0][3]为true，但是v3到v0不存在路径，所以a[3][0]为false。在有向图中我们说到度，一般区分出度和入度。这些信息也可以从矩阵中看出。
- 顶点i的出度是矩阵
a[i]那行中值为true的个数。 - 顶点i的入度是矩阵
a[][i]那列中值为true的个数。
如果图的边是带有权值的（加权图），邻接矩阵可以使用一个二维int数组，如果两个顶点之间存在路径就用该边的权值代替原布尔数组中的true，如果两个顶点间没不存在路径就用一个不大可能出现的值代替false，由于权值可能为负数，我们选用Integer.MAX_VALUE。
图中的“无穷”符号，就是我们选用的Integer的最大值。主对角线依然全是0，因为某个顶点到自身并不需要花费什么代价（可以理解为权值为0）。
虽然邻接矩阵在顶点数巨大的时候，所用空间令人发指，而且它还存了那么多没用的值——两个顶点不存在路径也存入了false或者一个不太可能出现的大值。但是无向图、有向图、加权无向图、加权有向图它都能实现，所以还是有必要动手敲一敲。
package Chap7;
import java.util.ArrayList;
import java.util.List;
/**
* 无向图 -- 邻接矩阵
* @param <Item> 顶点类型
*/
public class AdjMatrixGraph<Item> {
private int vertexNum;
private int edgeNum;
// 邻接矩阵
private boolean[][] adj;
// 存放所有顶点信息
private Item[] vertexInfo;
// 初始化有V个顶点的图，还未加边
public AdjMatrixGraph(Item[] vertexInfo) {
this.vertexNum = vertexInfo.length;
this.vertexInfo = vertexInfo;
adj = new boolean[vertexNum][vertexNum];
}
public AdjMatrixGraph(Item[] vertexInfo, int[][] edges) {
this(vertexInfo);
for (int[] twoVertex : edges) {
addEdge(twoVertex[0], twoVertex[1]);
}
}
public AdjMatrixGraph(int vertexNum) {
this.vertexNum = vertexNum;
adj = new boolean[vertexNum][vertexNum];
}
public AdjMatrixGraph(int vertexNum,int[][] edges) {
this(vertexNum);
for (int[] twoVertex : edges) {
addEdge(twoVertex[0], twoVertex[1]);
}
}
public void addEdge(int i, int j) {
// 对称矩阵，所以a[i][j] = a[j][i]
adj[i][j] = true;
adj[j][i] = true;
edgeNum++;
}
public int vertexNum() {
return vertexNum;
}
public int edgenum() {
return edgeNum;
}
public Item getVertexInfo(int i) {
return vertexInfo[i];
}
// 求某顶点的所有邻接顶点
public List<Integer> adj(int i) {
List<Integer> vertexAdj = new ArrayList<>();
for (int j = 0; j < adj[i].length; j++) {
if (adj[i][j]) {
vertexAdj.add(j);
}
}
return vertexAdj;
}
// 某顶点的度
public int degree(int i) {
int degree = 0;
for (int j = 0; j < adj[i].length; j++) {
if (adj[i][j]) {
degree++;
}
}
return degree;
}
// 求图的最大度数
public int maxDegree() {
int max = 0;
for (int i = 0; i < vertexNum; i++) {
if (degree(i) > max) {
max = degree(i);
}
}
return max;
}
// 求图的平均度数
// 边的条数 = 顶点度之和的一半 因为一条边对应两个顶点，这两个顶点的度数之和为2，所以边的数量是度之和的一半这样的关系
// edgeNum = sum / 2, 则sum = 2 * edgeNum, 于是avgDegree = sum / vertexNum
public double avgDegree() {
return 2.0 * edgeNum / vertexNum;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append(vertexNum).append("个顶点, ").append(edgeNum).append("条边。\n");
for (int i = 0; i < vertexNum; i++) {
sb.append(i).append(": ").append(adj(i)).append("\n");
}
return sb.toString();
}
public static void main(String[] args) {
String[] vertexInfo = {"v0", "v1", "v2", "v3", "v4"};
int[][] edges = {{0, 1}, {0, 2}, {0, 3},
{1, 3}, {1, 4},
{2, 4}};
AdjMatrixGraph<String> graph = new AdjMatrixGraph<>(vertexInfo,edges);
System.out.println("顶点3的度为" + graph.degree(3));
System.out.println("顶点3的邻接点为"+graph.adj(3));
System.out.println("该图的最大度数为" + graph.maxDegree());
System.out.println("该图的平均度数为" + graph.avgDegree());
System.out.println("邻接矩阵如下:\n" + graph);
}
}
/* Outputs
顶点3的度为2
顶点3的邻接点为[0, 1]
该图的最大度数为3
该图的平均度数为2.4
邻接矩阵如下:
5个顶点, 6条边。
0: [1, 2, 3]
1: [0, 3, 4]
2: [0, 4]
3: [0, 1]
4: [1, 2]
*/
我们的实现中有两个构造器，其中一个接收一个参数，传入顶点信息数组，以顶点信息个数作为图的顶点数。另外一个还可以接收表示所有相邻顶点的二维数组，比如edges[0] = {0, 1}表示顶点0和顶点1相邻，由于addEdge方法中已经考虑了对称矩阵，所以这里传参的时候就用不着传入{0， 1}后再传入{1, 0}了，只要保证前一个数比后一个数小就可以避免重复添加。
这里重点说一下求图的平均度数的方法avgDegree，我们有一个结论：图的边的条数 = 顶点度之和的一半，这是因为每一条边对应着两个顶点，而这两个顶点对于这条边，度之和为2。所以边的条数是所有顶点度之和的一半，即edgeNum = sum / 2，则sum = 2 * edgeNum， 于是avgDegree = sum / vertexNum
邻接表
邻接数组的缺点是所用空间太多，而且存放的信息很多是多余——顶点没有相邻也非得用一个false值或者不太可能出现的大值去填补数组中的位置，为何不直接留下相邻顶点就行了？比如上例中的a[0]，可以从矩阵中看出与顶点0相邻的有顶点1、2、3
0 1 2 3 4 5
0 false true true true false false
为什么不直接存储为a[0] = [1, 2, 3]（就像上面打印的一样），这不是直观了很多嘛。由于每个顶点拥有的邻接点数目不同，使用数组实现就浪费空间了。所以存放某个顶点所有邻接点的容器，使用可变容量的表是个不错的选择，这里我就用链表了。回想树的孩子表示法，和这是一个道理，只是孩子表示法中存放的是结点对象(Node)，这里存放的是用整数表示的顶点。邻接表不像邻接矩阵那样容量固定，如果某幅图要添加、删除某个顶点或某条边是相当方便的。所以在之后的实现中，如果没有特殊需求，将会一直使用邻接表。
package Chap6;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
/**
* 无向图
* @param <Item>
*/
public class UndiGraph<Item> {
private int vertexNum;
private int edgeNum;
// 邻接表
private List<List<Integer>> adj;
// 顶点信息
private List<Item> vertexInfo;
public UndiGraph(List<Item> vertexInfo) {
this.vertexInfo = vertexInfo;
this.vertexNum = vertexInfo.size();
adj = new ArrayList<>();
for (int i = 0; i < vertexNum; i++) {
adj.add(new LinkedList<>());
}
}
public UndiGraph(List<Item> vertexInfo, int[][] edges) {
this(vertexInfo);
for (int[] twoVertex : edges) {
addEdge(twoVertex[0], twoVertex[1]);
}
}
public int vertexNum() {
return vertexNum;
}
public int edgeNum() {
return edgeNum;
}
public void addEdge(int i, int j) {
adj.get(i).add(j);
adj.get(j).add(i);
edgeNum++;
}
// 不需要set，所以不用返回List，返回可迭代对象就够了
public Iterable<Integer> adj(int i) {
return adj.get(i);
}
public Item getVertexInfo(int i) {
return vertexInfo.get(i);
}
public int degree(int i) {
return adj.get(i).size();
}
public int maxDegree() {
int max = 0;
for (int i = 0;i < vertexNum;i++) {
if (degree(i) > max) {
max = degree(i);
}
}
return max;
}
public double avgDegree() {
return 2.0 * edgeNum / vertexNum;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append(vertexNum).append("个顶点, ").append(edgeNum).append("条边。\n");
for (int i = 0; i < vertexNum; i++) {
sb.append(i).append(": ").append(adj.get(i)).append("\n");
}
return sb.toString();
}
public static void main(String[] args) {
List<String> vertexInfo = Arrays.asList("v0", "v1", "v2", "v3", "v4");
int[][] edges = {{0, 1}, {0, 2}, {0, 3},
{1, 3}, {1, 4},
{2, 4}};
UndiGraph<String> graph = new UndiGraph<>(vertexInfo, edges);
System.out.println("顶点3的度为" + graph.degree(3));
System.out.println("顶点3的邻接点为"+graph.adj(3));
System.out.println("该图的最大度数为" + graph.maxDegree());
System.out.println("该图的平均度数为" + graph.avgDegree());
System.out.println("邻接表如下:\n" + graph);
}
}
程序输出和上面邻接矩阵实现的输出完全一样。各个方法的实现其思想和邻接矩阵实现类似，比较简单就不解释了。
顺便把有向图也用邻接表实现了。
package Chap7;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
/**
* 无向图
*
* @param <Item>
*/
public class DiGraph<Item> {
private int vertexNum;
private int edgeNum;
// 邻接表
private List<List<Integer>> adj;
// 顶点信息
private List<Item> vertexInfo;
public DiGraph(List<Item> vertexInfo) {
this.vertexInfo = vertexInfo;
this.vertexNum = vertexInfo.size();
adj = new ArrayList<>();
for (int i = 0; i < vertexNum; i++) {
adj.add(new LinkedList<>());
}
}
public DiGraph(List<Item> vertexInfo, int[][] edges) {
this(vertexInfo);
for (int[] twoVertex : edges) {
addEdge(twoVertex[0], twoVertex[1]);
}
}
public DiGraph(int vertexNum) {
this.vertexNum = vertexNum;
adj = new ArrayList<>();
for (int i = 0; i < vertexNum; i++) {
adj.add(new LinkedList<>());
}
}
public DiGraph(int vertexNum, int[][] edges) {
this(vertexNum);
for (int[] twoVertex : edges) {
addEdge(twoVertex[0], twoVertex[1]);
}
}
public int vertexNum() {
return vertexNum;
}
public int edgeNum() {
return edgeNum;
}
public void addEdge(int i, int j) {
adj.get(i).add(j);
edgeNum++;
}
// 不需要set，所以不用返回List，返回可迭代对象就够了
public Iterable<Integer> adj(int i) {
return adj.get(i);
}
public DiGraph<Item> reverse() {
DiGraph<Item> R = new DiGraph<>(vertexNum);
for (int v = 0; v < vertexNum; v++) {
for (int w: adj(v)) {
R.addEdge(w, v);
}
}
return R;
}
public Item getVertexInfo(int i) {
return vertexInfo.get(i);
}
public int degree(int i) {
return adj.get(i).size();
}
public int maxDegree() {
int max = 0;
for (int i = 0; i < vertexNum; i++) {
if (degree(i) > max) {
max = degree(i);
}
}
return max;
}
public double avgDegree() {
return 2.0 * edgeNum / vertexNum;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append(vertexNum).append("个顶点, ").append(edgeNum).append("条边。\n");
for (int i = 0; i < vertexNum; i++) {
sb.append(i).append(": ").append(adj.get(i)).append("\n");
}
return sb.toString();
}
public static void main(String[] args) {
List<String> vertexInfo = Arrays.asList("v0", "v1", "v2", "v3", "v4");
int[][] edges = {{0, 1}, {0, 2}, {0, 3},
{1, 3}, {1, 4},
{2, 4}};
DiGraph<String> graph = new DiGraph<>(vertexInfo, edges);
System.out.println("顶点3的度为" + graph.degree(3));
System.out.println("顶点3的邻接点为" + graph.adj(3));
System.out.println("该图的最大度数为" + graph.maxDegree());
System.out.println("该图的平均度数为" + graph.avgDegree());
System.out.println("邻接表如下:\n" + graph);
}
}
addEdge方法少了一行，有向图嘛，边也是有方向的，i -> j有边不一定j -> i有边。另外新增了一个反向图的reverse方法，改变了所有边的方向，并返回原图的反向图。代码中主要做的是对每个顶点v，以及v的所有邻接顶点w，本来是v -> w的方向，现在新图中调用addEdge(w, v)，将方向变成w -> v，实现反向。
至于其他方法，和无向图完全一样。
边的数组
这种方法实现起来很简单，顾名思义它更关注边，我们可以用一个Edge来抽象边，它有两个int成员表示该边的两个顶点，如果是加权图，再多一个int型的weight成员就行了。将所有边存放到一个列表List<Edge>中，就是我们所说的边的数组了。
package Chap7;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class EdgeGraph<Item> {
public static class Edge {
private int either;
private int other;
public int either() {
return either;
}
public int other() {
return other;
}
public Edge(int either, int other) {
this.either = either;
this.other = other;
}
@Override
public String toString() {
return "Edge{" +
"either=" + either +
", other=" + other +
'}';
}
}
private int vertexNum;
private int edgeNum;
private List<Item> vertexInfo;
private List<Edge> edges;
public EdgeGraph(List<Item> vertexInfo) {
this.edges = new ArrayList<>();
this.vertexInfo = vertexInfo;
this.vertexNum = vertexInfo.size();
}
public EdgeGraph(List<Item> vertexInfo, int[][] edges) {
this(vertexInfo);
for (int[] twoVertex : edges) {
addEdge(twoVertex[0], twoVertex[1]);
}
}
public EdgeGraph(int vertexNum) {
this.edges = new ArrayList<>();
this.vertexNum = vertexNum;
}
public EdgeGraph(int vertexNum, int[][] edges) {
this(vertexNum);
for (int[] twoVertex : edges) {
addEdge(twoVertex[0], twoVertex[1]);
}
}
public void addEdge(int i, int j) {
Edge edge = new Edge(i, j);
this.edges.add(edge);
edgeNum++;
}
public List<Integer> adj(int i) {
List<Integer> adj = new ArrayList<>();
for (Edge edge : edges) {
if (edge.either == i) {
adj.add(edge.other);
} else if (edge.other == i) {
adj.add(edge.either);
}
}
return adj;
}
public int degree(int i) {
return adj(i).size();
}
public int maxDegree() {
int max = 0;
for (int i = 0; i < vertexNum; i++) {
if (degree(i) > max) {
max = degree(i);
}
}
return max;
}
public double avgDegree() {
return 2.0 * edgeNum / vertexNum;
}
public Item getVertexInfo(int i) {
return vertexInfo.get(i);
}
public int vertexNum() {
return vertexNum;
}
public int edgeNum() {
return edgeNum;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append(vertexNum).append("个顶点, ").append(edgeNum).append("条边。\n");
for (int i = 0; i < vertexNum; i++) {
sb.append(i).append(": ").append(adj(i)).append("\n");
}
return sb.toString();
}
public static void main(String[] args) {
List<String> vertexInfo = Arrays.asList("v0", "v1", "v2", "v3", "v4");
int[][] edges = {{0, 1}, {0, 2}, {0, 3},
{1, 3}, {1, 4},
{2, 4}};
EdgeGraph<String> graph = new EdgeGraph<>(vertexInfo, edges);
System.out.println("顶点3的度为" + graph.degree(3));
System.out.println("顶点3的邻接点为" + graph.adj(3));
System.out.println("该图的最大度数为" + graph.maxDegree());
System.out.println("该图的平均度数为" + graph.avgDegree());
System.out.println("邻接表如下:\n" + graph);
}
}
自然输出和前面都一样。
只说addEdge(int i, int j)方法和adj(int i)方法。前者给图中两个顶点添加一条边，传入两个顶点，紧接着就new一个对应Edge，再将其存入边的列表即可。后者获取某个顶点所有邻接点，遍历边的列表，因为不知道边中哪个顶点和i相等，所以需要判断一下，只要有一个顶点和i相等，就将另一个存入待返回的列表中。
现在也知道了该实现有个缺陷：要知道某个顶点的所有邻接点，必须遍历整个边数组，效率不是很高。如果我们经常进行对顶点的操作，可以说获取某顶点所有邻接点是非常频繁的，边的数组不太适合经常对图的顶点进行操作的场合，更适合经常对边进行依次操作的场合。
在后面加权图的实现中，我们会用到边的数组的思想，因为权值在边上嘛，邻接矩阵实现起倒是简单，但是对于邻接表来说，由上面可以知道它定义为List<List<Integer>>，内层列表存放的是顶点的所有邻接点，那么权值存在哪里？这时候我们就需要一个Edge类了。差不多像下面这样。
public class Edge {
private int either;
private int other;
private int weight;
}
邻接表随之也变成了List<List<Edge>>。这里只是稍微提一下，以后学到加权图的时候再具体来说。
by @sunhaiyu
2017.9.17
