1. 代碼倉(cāng)庫(kù)

https://github.com/Chufeng-Jiang/Graph-Theory/tree/main/src/Chapt01_Adjacency

2. 圖的基本表示的比較

3. 鄰接矩陣：Array和TreeSet

3.1 圖示

3.2 Array主要代碼解析

代碼有刪減

public AdjMatrix(String filename){File file = new File(filename);try(Scanner scanner = new Scanner(file)){       V = scanner.nextInt(); //讀取第一行第一個(gè)數(shù),代表圖中的頂點(diǎn)數(shù)//構(gòu)造鄰接矩陣adj = new int[V][V]; E = scanner.nextInt(); //讀取第一行第二個(gè)數(shù)，代表圖中邊的數(shù)量// E是邊的數(shù)量，在g.txt中表示為第二行開始的E行for (int i = 0; i < E; i++) {int a = scanner.nextInt(); //讀取邊的一個(gè)頂點(diǎn)int b = scanner.nextInt(); //讀取邊的另一個(gè)頂點(diǎn)adj[a][b] = 1; //存在邊則設(shè)置為1adj[b][a] = 1;}}
}

3.3 測(cè)試輸出

3.4 使用TreeSet的代碼

代碼有刪減
只需要改動(dòng)一行

adj = new TreeSet[V]; //構(gòu)造鄰接表, V行，V個(gè)LinkedList

4. 鄰接表：LinkedList

4.1 圖示

4.2 LinkedList主要代碼解析

代碼有刪減

public class AdjList {private int V;private int E;private LinkedList<Integer>[] adj;public AdjList(String filename){File file = new File(filename);try(Scanner scanner = new Scanner(file)){V = scanner.nextInt();/*構(gòu)造鄰接表, V行，V個(gè)LinkedList*/adj = new LinkedList[V]; for (int i = 0; i < V; i++) {adj[i] = new LinkedList<Integer>();}E = scanner.nextInt(); //讀取第一行第二個(gè)數(shù)// E是邊的數(shù)量，在g.txt中表示為第二行開始的E行for (int i = 0; i < E; i++) {int a = scanner.nextInt(); //讀取邊的一個(gè)頂點(diǎn)int b = scanner.nextInt(); //讀取邊的另一個(gè)頂點(diǎn)adj[a].add(b);adj[b].add(a);}}}

4.3 測(cè)試輸出

5. 完整代碼

5.1 鄰接表 - Array

package Chapt01_Adjacency;import java.io.File;
import java.io.IOException;
import java.util.LinkedList;
import java.util.Scanner;public class AdjList {private int V;private int E;private LinkedList<Integer>[] adj;public AdjList(String filename){File file = new File(filename);try(Scanner scanner = new Scanner(file)){V = scanner.nextInt();if(V < 0) throw new IllegalArgumentException("V must be non-negative");adj = new LinkedList[V]; //構(gòu)造鄰接表, V行，V個(gè)LinkedListfor (int i = 0; i < V; i++) {adj[i] = new LinkedList<Integer>();}E = scanner.nextInt(); //讀取第一行第二個(gè)數(shù)if(E < 0) throw new IllegalArgumentException("E must be non-negative");// E是邊的數(shù)量，在g.txt中表示為第二行開始的E行for (int i = 0; i < E; i++) {int a = scanner.nextInt(); //讀取邊的一個(gè)頂點(diǎn)validateVertex(a);int b = scanner.nextInt(); //讀取邊的另一個(gè)頂點(diǎn)validateVertex(b);if(a == b) throw new IllegalArgumentException("Self Loop is Detected"); //判斷是夠存在自環(huán)邊if(adj[a].contains(b)) throw new IllegalArgumentException("Parallel Edges are Detected"); //判斷是夠存在平行l(wèi)邊adj[a].add(b);adj[b].add(a);}}catch (IOException e){e.printStackTrace();}}private void validateVertex(int v){if(v < 0 || v >= V)throw new IllegalArgumentException("vertex" + v + "is invalid");}public int V(){return V;}public int E(){return E;}public boolean hasEdge(int v, int w){validateVertex(v);validateVertex(w);return adj[v].contains(w);}public LinkedList<Integer> adj(int v){validateVertex(v);return adj[v];}public int degree(int v){return adj(v).size();}@Overridepublic String toString(){StringBuilder sb = new StringBuilder();sb.append(String.format("V = %d, E = %d\n", V, E));for (int i = 0; i < V; i++) {sb.append(String.format("%d:",i));for (int w: adj[i]) {sb.append(String.format("%d ",w));}sb.append('\n');}return sb.toString();}public static void main(String[] args){AdjList adjList = new AdjList("g1.txt"); //新建鄰接矩陣，并從文件內(nèi)容初始化System.out.println(adjList);}
}

5.2 鄰接表-TreeSet

package Chapt01_Adjacency;import java.io.File;
import java.io.IOException;
import java.util.Scanner;
import java.util.TreeSet;public class AdjSet {private int V;private int E;private TreeSet<Integer>[] adj;public AdjSet(String filename){File file = new File(filename);try(Scanner scanner = new Scanner(file)){V = scanner.nextInt();if(V < 0) throw new IllegalArgumentException("V must be non-negative");adj = new TreeSet[V]; //構(gòu)造鄰接表, V行，V個(gè)LinkedListfor (int i = 0; i < V; i++) {adj[i] = new TreeSet<Integer>();}E = scanner.nextInt(); //讀取第一行第二個(gè)數(shù)if(E < 0) throw new IllegalArgumentException("E must be non-negative");// E是邊的數(shù)量，在g.txt中表示為第二行開始的E行for (int i = 0; i < E; i++) {int a = scanner.nextInt(); //讀取邊的一個(gè)頂點(diǎn)validateVertex(a);int b = scanner.nextInt(); //讀取邊的另一個(gè)頂點(diǎn)validateVertex(b);if(a == b) throw new IllegalArgumentException("Self Loop is Detected"); //判斷是夠存在自環(huán)邊if(adj[a].contains(b)) throw new IllegalArgumentException("Parallel Edges are Detected"); //判斷是夠存在平行l(wèi)邊adj[a].add(b);adj[b].add(a);}}catch (IOException e){e.printStackTrace();}}private void validateVertex(int v){if(v < 0 || v >= V)throw new IllegalArgumentException("vertex" + v + "is invalid");}public int V(){return V;}public int E(){return E;}public boolean hasEdge(int v, int w){validateVertex(v);validateVertex(w);return adj[v].contains(w);}public Iterable<Integer> adj(int v){ // 可以是TreeSet，但是數(shù)組、鏈表、紅黑樹都是實(shí)現(xiàn)了Iterable的接口，因此可以統(tǒng)一寫成這樣validateVertex(v);return adj[v];}public int degree(int v){validateVertex(v);return adj[v].size(); // Iterable沒有size()方法}@Overridepublic String toString(){StringBuilder sb = new StringBuilder();sb.append(String.format("V = %d, E = %d\n", V, E));for (int i = 0; i < V; i++) {sb.append(String.format("%d:",i));for (int w: adj[i]) {sb.append(String.format("%d ",w));}sb.append('\n');}return sb.toString();}public static void main(String[] args){AdjSet adjSet = new AdjSet("g1.txt"); //新建鄰接矩陣，并從文件內(nèi)容初始化System.out.println(adjSet);}
}

5.3 鄰接矩陣-LinkedList

package Chapt01_Adjacency;import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;public class AdjMatrix {private int V;private int E;private int[][] adj;// 構(gòu)造函數(shù)，從文件內(nèi)容初始化鄰接矩陣public AdjMatrix(String filename){File file = new File(filename);try(Scanner scanner = new Scanner(file)){V = scanner.nextInt(); //讀取第一行第一個(gè)數(shù),代表圖中的頂點(diǎn)數(shù)if(V < 0) throw new IllegalArgumentException("V must be non-negative");adj = new int[V][V]; //構(gòu)造鄰接矩陣E = scanner.nextInt(); //讀取第一行第二個(gè)數(shù)，代表圖中邊的數(shù)量if(E < 0) throw new IllegalArgumentException("E must be non-negative");// E是邊的數(shù)量，在g.txt中表示為第二行開始的E行for (int i = 0; i < E; i++) {int a = scanner.nextInt(); //讀取邊的一個(gè)頂點(diǎn)validateVertex(a);int b = scanner.nextInt(); //讀取邊的另一個(gè)頂點(diǎn)validateVertex(b);if(a == b) throw new IllegalArgumentException("Self Loop is Detected"); //判斷是夠存在自環(huán)邊if(adj[a][b] == 1) throw new IllegalArgumentException("Parallel Edges are Detected"); //判斷是否存在平行l(wèi)邊adj[a][b] = 1; //存在邊則設(shè)置為1adj[b][a] = 1;}}catch (IOException e){e.printStackTrace();}}private void validateVertex(int v){if(v < 0 || v >= V)throw new IllegalArgumentException("vertex" + v + "is invalid");}public int V(){return V;}public int E(){return E;}public boolean hasEdge(int v, int w){validateVertex(v);validateVertex(w);return adj[v][w] == 1;}public ArrayList<Integer> adj(int v){validateVertex(v);ArrayList<Integer> res = new ArrayList<>();for (int i = 0; i < V; i++) {if(adj[v][i] == 1) res.add(i);}return res;}public int degree(int v){return adj(v).size(); //adj(v)是上方的adj方法，size()是ArrayList的接口}// 用于在控制臺(tái)打印該臨接矩陣@Overridepublic String toString(){StringBuilder sb = new StringBuilder();sb.append(String.format("V = %d, E = %d\n", V, E)); //打印頂點(diǎn)數(shù)和邊的數(shù)量for (int i = 0; i < V; i++) { //行for (int j = 0; j < V; j++) { //列sb.append(String.format("%d",adj[i][j])); //讀取矩陣的值}sb.append('\n'); //行尾換行}return sb.toString(); //返回該鄰接矩陣}public static void main(String[] args){AdjMatrix adjMatrix = new AdjMatrix("g1.txt"); //新建鄰接矩陣，并從文件內(nèi)容初始化System.out.println(adjMatrix);}
}

5.4 輸入文件

7 9
0 1
0 3
1 2
1 6
2 3
2 5
3 4
4 5
5 6