數(shù)據(jù)結(jié)構(gòu)與算法--圖的實現(xiàn)（鄰接表、鄰接矩陣先誉、邊的數(shù)組）
應(yīng)該用哪種數(shù)據(jù)結(jié)構(gòu)實現(xiàn)圖呢湿刽？主要有如下三種：
鄰接矩陣
對一個擁有V個頂點(diǎn)的圖，建立一個V*V的布爾數(shù)組谆膳，如果頂點(diǎn)i到j(luò)之間有邊連接叭爱，則定義i行j列的元素值為true，否則為false漱病，如果是帶有權(quán)值的圖买雾，那么將true改成相應(yīng)的權(quán)值，false改成一個不太可能出現(xiàn)的值比如Integer.MAX_VALUE杨帽。還可以專門用一個數(shù)組或者表漓穿，用來存放頂點(diǎn)信息，因為我們直接用0~N - 1的值代表了每個頂點(diǎn)注盈，但這些數(shù)值具體指代了什么意思可以去頂點(diǎn)信息數(shù)組查找晃危。不過鄰接矩陣表示對于頂點(diǎn)數(shù)目很多（比如上百萬）的圖，N*N個值的空間是不能滿足的。
如上僚饭，左邊的無向圖可以轉(zhuǎn)換成右邊的鄰接矩陣震叮。頂點(diǎn)0~3的信息存在頂點(diǎn)信息數(shù)組里。由于這里用的是大話數(shù)據(jù)結(jié)構(gòu)（C語言）中的圖鳍鸵，0其實就是false史飞，1就是true篷角。頂點(diǎn)v0和v1有邊相連摊沉，所以在矩陣中a[0][1]和a[1][0]的值為true摩钙，而v1和v3之間沒有邊相連所以a[1][3]和a[3][1]為false。仔細(xì)觀察可以發(fā)現(xiàn)主對角線的值全是0贪薪，這是因為我們討論的是簡單圖媳禁，暫時不考慮自環(huán)的情況。以主對角線為對稱軸画切，矩陣左下a[i][j]和對應(yīng)右上的a[j][i]值是一樣的竣稽，這其實是一個對稱矩陣。通過鄰接矩陣槽唾，我們還可以獲得一些其他信息丧枪。
- 某個頂點(diǎn)i的度其實就是矩陣中
a[i]那行中true的個數(shù)。 - 與頂點(diǎn)i相鄰的頂點(diǎn)就是矩陣中
a[i]那行中所有值為true的列下標(biāo)庞萍。
鄰接矩陣對于有向圖也適用拧烦，只是矩陣不再是對稱矩陣了。
如圖v0到v3有路徑钝计，所以a[0][3]為true恋博，但是v3到v0不存在路徑，所以a[3][0]為false私恬。在有向圖中我們說到度债沮，一般區(qū)分出度和入度。這些信息也可以從矩陣中看出本鸣。
- 頂點(diǎn)i的出度是矩陣
a[i]那行中值為true的個數(shù)疫衩。 - 頂點(diǎn)i的入度是矩陣
a[][i]那列中值為true的個數(shù)。
如果圖的邊是帶有權(quán)值的（加權(quán)圖）荣德，鄰接矩陣可以使用一個二維int數(shù)組闷煤，如果兩個頂點(diǎn)之間存在路徑就用該邊的權(quán)值代替原布爾數(shù)組中的true，如果兩個頂點(diǎn)間沒不存在路徑就用一個不大可能出現(xiàn)的值代替false涮瞻，由于權(quán)值可能為負(fù)數(shù)鲤拿，我們選用Integer.MAX_VALUE。
圖中的“無窮”符號署咽，就是我們選用的Integer的最大值近顷。主對角線依然全是0，因為某個頂點(diǎn)到自身并不需要花費(fèi)什么代價（可以理解為權(quán)值為0）。
雖然鄰接矩陣在頂點(diǎn)數(shù)巨大的時候窒升，所用空間令人發(fā)指缀遍，而且它還存了那么多沒用的值——兩個頂點(diǎn)不存在路徑也存入了false或者一個不太可能出現(xiàn)的大值。但是無向圖饱须、有向圖瑟由、加權(quán)無向圖、加權(quán)有向圖它都能實現(xiàn)冤寿，所以還是有必要動手敲一敲。
package Chap7;
import java.util.ArrayList;
import java.util.List;
/**
* 無向圖 -- 鄰接矩陣
* @param <Item> 頂點(diǎn)類型
*/
public class AdjMatrixGraph<Item> {
private int vertexNum;
private int edgeNum;
// 鄰接矩陣
private boolean[][] adj;
// 存放所有頂點(diǎn)信息
private Item[] vertexInfo;
// 初始化有V個頂點(diǎn)的圖青伤，還未加邊
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];
}
// 求某頂點(diǎn)的所有鄰接頂點(diǎn)
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;
}
// 某頂點(diǎn)的度
public int degree(int i) {
int degree = 0;
for (int j = 0; j < adj[i].length; j++) {
if (adj[i][j]) {
degree++;
}
}
return degree;
}
// 求圖的最大度數(shù)
public int maxDegree() {
int max = 0;
for (int i = 0; i < vertexNum; i++) {
if (degree(i) > max) {
max = degree(i);
}
}
return max;
}
// 求圖的平均度數(shù)
// 邊的條數(shù) = 頂點(diǎn)度之和的一半 因為一條邊對應(yīng)兩個頂點(diǎn)，這兩個頂點(diǎn)的度數(shù)之和為2狠角，所以邊的數(shù)量是度之和的一半這樣的關(guān)系
// 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("個頂點(diǎn), ").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("頂點(diǎn)3的度為" + graph.degree(3));
System.out.println("頂點(diǎn)3的鄰接點(diǎn)為"+graph.adj(3));
System.out.println("該圖的最大度數(shù)為" + graph.maxDegree());
System.out.println("該圖的平均度數(shù)為" + graph.avgDegree());
System.out.println("鄰接矩陣如下:\n" + graph);
}
}
/* Outputs
頂點(diǎn)3的度為2
頂點(diǎn)3的鄰接點(diǎn)為[0, 1]
該圖的最大度數(shù)為3
該圖的平均度數(shù)為2.4
鄰接矩陣如下:
5個頂點(diǎn), 6條邊。
0: [1, 2, 3]
1: [0, 3, 4]
2: [0, 4]
3: [0, 1]
4: [1, 2]
*/
我們的實現(xiàn)中有兩個構(gòu)造器丰歌，其中一個接收一個參數(shù)姨蟋，傳入頂點(diǎn)信息數(shù)組，以頂點(diǎn)信息個數(shù)作為圖的頂點(diǎn)數(shù)立帖。另外一個還可以接收表示所有相鄰頂點(diǎn)的二維數(shù)組眼溶，比如edges[0] = {0, 1}表示頂點(diǎn)0和頂點(diǎn)1相鄰，由于addEdge方法中已經(jīng)考慮了對稱矩陣晓勇，所以這里傳參的時候就用不著傳入{0堂飞， 1}后再傳入{1, 0}了，只要保證前一個數(shù)比后一個數(shù)小就可以避免重復(fù)添加绑咱。
這里重點(diǎn)說一下求圖的平均度數(shù)的方法avgDegree绰筛，我們有一個結(jié)論：圖的邊的條數(shù) = 頂點(diǎn)度之和的一半，這是因為每一條邊對應(yīng)著兩個頂點(diǎn)描融，而這兩個頂點(diǎn)對于這條邊铝噩，度之和為2。所以邊的條數(shù)是所有頂點(diǎn)度之和的一半窿克，即edgeNum = sum / 2骏庸，則sum = 2 * edgeNum， 于是avgDegree = sum / vertexNum
鄰接表
鄰接數(shù)組的缺點(diǎn)是所用空間太多让歼，而且存放的信息很多是多余——頂點(diǎn)沒有相鄰也非得用一個false值或者不太可能出現(xiàn)的大值去填補(bǔ)數(shù)組中的位置敞恋，為何不直接留下相鄰頂點(diǎn)就行了？比如上例中的a[0]谋右，可以從矩陣中看出與頂點(diǎn)0相鄰的有頂點(diǎn)1硬猫、2、3
0 1 2 3 4 5
0 false true true true false false
為什么不直接存儲為a[0] = [1, 2, 3]（就像上面打印的一樣），這不是直觀了很多嘛啸蜜。由于每個頂點(diǎn)擁有的鄰接點(diǎn)數(shù)目不同坑雅，使用數(shù)組實現(xiàn)就浪費(fèi)空間了。所以存放某個頂點(diǎn)所有鄰接點(diǎn)的容器衬横，使用可變?nèi)萘康谋硎莻€不錯的選擇裹粤，這里我就用鏈表了》淞郑回想樹的孩子表示法遥诉，和這是一個道理，只是孩子表示法中存放的是結(jié)點(diǎn)對象(Node)噪叙，這里存放的是用整數(shù)表示的頂點(diǎn)矮锈。鄰接表不像鄰接矩陣那樣容量固定，如果某幅圖要添加睁蕾、刪除某個頂點(diǎn)或某條邊是相當(dāng)方便的苞笨。所以在之后的實現(xiàn)中，如果沒有特殊需求子眶，將會一直使用鄰接表瀑凝。
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;
// 頂點(diǎn)信息
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("個頂點(diǎn), ").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("頂點(diǎn)3的度為" + graph.degree(3));
System.out.println("頂點(diǎn)3的鄰接點(diǎn)為"+graph.adj(3));
System.out.println("該圖的最大度數(shù)為" + graph.maxDegree());
System.out.println("該圖的平均度數(shù)為" + graph.avgDegree());
System.out.println("鄰接表如下:\n" + graph);
}
}
程序輸出和上面鄰接矩陣實現(xiàn)的輸出完全一樣。各個方法的實現(xiàn)其思想和鄰接矩陣實現(xiàn)類似硅卢，比較簡單就不解釋了射窒。
順便把有向圖也用鄰接表實現(xiàn)了。
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;
// 頂點(diǎn)信息
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("個頂點(diǎn), ").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("頂點(diǎn)3的度為" + graph.degree(3));
System.out.println("頂點(diǎn)3的鄰接點(diǎn)為" + graph.adj(3));
System.out.println("該圖的最大度數(shù)為" + graph.maxDegree());
System.out.println("該圖的平均度數(shù)為" + graph.avgDegree());
System.out.println("鄰接表如下:\n" + graph);
}
}
addEdge方法少了一行点寥，有向圖嘛艾疟，邊也是有方向的，i -> j有邊不一定j -> i有邊敢辩。另外新增了一個反向圖的reverse方法蔽莱，改變了所有邊的方向，并返回原圖的反向圖戚长。代碼中主要做的是對每個頂點(diǎn)v盗冷，以及v的所有鄰接頂點(diǎn)w，本來是v -> w的方向同廉，現(xiàn)在新圖中調(diào)用addEdge(w, v)仪糖，將方向變成w -> v柑司，實現(xiàn)反向。
至于其他方法锅劝，和無向圖完全一樣攒驰。
邊的數(shù)組
這種方法實現(xiàn)起來很簡單，顧名思義它更關(guān)注邊故爵，我們可以用一個Edge來抽象邊玻粪，它有兩個int成員表示該邊的兩個頂點(diǎn)，如果是加權(quán)圖诬垂，再多一個int型的weight成員就行了劲室。將所有邊存放到一個列表List<Edge>中，就是我們所說的邊的數(shù)組了结窘。
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("個頂點(diǎn), ").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("頂點(diǎn)3的度為" + graph.degree(3));
System.out.println("頂點(diǎn)3的鄰接點(diǎn)為" + graph.adj(3));
System.out.println("該圖的最大度數(shù)為" + graph.maxDegree());
System.out.println("該圖的平均度數(shù)為" + graph.avgDegree());
System.out.println("鄰接表如下:\n" + graph);
}
}
自然輸出和前面都一樣。
只說addEdge(int i, int j)方法和adj(int i)方法晦鞋。前者給圖中兩個頂點(diǎn)添加一條邊，傳入兩個頂點(diǎn)棺克，緊接著就new一個對應(yīng)Edge悠垛，再將其存入邊的列表即可。后者獲取某個頂點(diǎn)所有鄰接點(diǎn)娜谊，遍歷邊的列表确买，因為不知道邊中哪個頂點(diǎn)和i相等，所以需要判斷一下纱皆，只要有一個頂點(diǎn)和i相等湾趾，就將另一個存入待返回的列表中。
現(xiàn)在也知道了該實現(xiàn)有個缺陷：要知道某個頂點(diǎn)的所有鄰接點(diǎn)派草，必須遍歷整個邊數(shù)組搀缠，效率不是很高。如果我們經(jīng)常進(jìn)行對頂點(diǎn)的操作近迁，可以說獲取某頂點(diǎn)所有鄰接點(diǎn)是非常頻繁的艺普，邊的數(shù)組不太適合經(jīng)常對圖的頂點(diǎn)進(jìn)行操作的場合，更適合經(jīng)常對邊進(jìn)行依次操作的場合鉴竭。
在后面加權(quán)圖的實現(xiàn)中歧譬，我們會用到邊的數(shù)組的思想，因為權(quán)值在邊上嘛搏存，鄰接矩陣實現(xiàn)起倒是簡單瑰步，但是對于鄰接表來說，由上面可以知道它定義為List<List<Integer>>璧眠，內(nèi)層列表存放的是頂點(diǎn)的所有鄰接點(diǎn)缩焦，那么權(quán)值存在哪里读虏？這時候我們就需要一個Edge類了。差不多像下面這樣舌界。
public class Edge {
private int either;
private int other;
private int weight;
}
鄰接表隨之也變成了List<List<Edge>>掘譬。這里只是稍微提一下，以后學(xué)到加權(quán)圖的時候再具體來說呻拌。
by @sunhaiyu
2017.9.17
