2-1 图的分类
图是一个用线 或 边连接在一起的顶点的集合，可以说，图是有限 顶点V 和 边E 的有序对。顶点（Vertex），边（Edge）
图a中的边没有方向，称为无向图。图b中边存在方向称为有向图。
1.1(a)所示的图可以表示为 G1(V, E)。其中顶点集合 V(G1) = { 1, 2, 3, 4, 5, 6 }，集合
中的元素为顶点（用序号代表，在其他图中，顶点集合中的元素也可以是其他标识顶点的符号，
如字母 A、B、C 等）；
边的集合为：E(G1) = { (1, 2), (1, 3), (2, 3), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (4, 5) }
图 1.1(b)所示的图可以表示为 G2(V, E)，其中顶点集合 V(G2) = { 1, 2, 3, 4, 5, 6, 7 }，集合中的元素也为顶点的序号；
边的集合为：
E(G2) = { <1, 2>, <2, 3>, <2, 5>, <2, 6>, <3, 5>, <4, 3>, <5, 2>, <5, 4>, <6, 7> }。
在上述边的集合中，每个元素<u, v>为一对顶点构成的有序对（用尖括号括起来），
表示从点 u 到顶点 v 的有向边（directed Edge）
权值（weight）：某些图的边具有与它相关的数，称为权值。
下列图示分别表示：无向有权图，有向有权图
上图a中：所示的无向网可表示为 G1(V, E)，其中顶点集合 V(G1) = { 1, 2, 3, 4, 5, 6, 7 }；
边的集合为：
E(G1) = { (1, 2, 28), (1, 6, 10), (2, 3, 16), (2, 7, 14), (3, 4, 12), (4, 5, 22), (4, 7, 18), (5, 6, 25), (5, 7, 24) }。
在边的集合中，每个元素的第 3 个分量表示该边的权值。
所以依据图的有无方向和权值可以分为4类：
1.无向无权图
2.有向无权图
3.无向有权图
4.有向有权图
2-2 图的基本概念
顶点的度（degree）：对于无向图来说，一个顶点的度就是这个顶点的相邻的边的数量。如第一张图a中点1的度就是 2 。
简单图：没有自环边，没有平行边
子图：例如，图 1.8(a)、(b)所示的无向图都是图 1.1(a)所示的无向图 G1的子图
联通图和非联通图：
在无向图中，若从顶点 u 到 v 有路径，则称顶点 u 和 v是连通的（connected）。
如果无向图中任意一对顶点都是连通的，则称此图是连通图（connected graph）；
相反，如果一个无向图不是连通图，则称为非连通图（disconnected graph）。
如果一个无向图不是连通的，则其极大连通子图称为连通分量（connected component）
树是一种无环图，任意结点都可以看做是根节点。联通的无环图是树。
生成树（Spanning Tree）：一个无向连通图的生成树是它的包含所有顶点的极小连通子图，这里所谓的极小就是边的数目极小。
如果图中有 n 个顶点，则生成树有 n-1 条边。一个无向连通图可能有多个生成树。
图1.1(a) 所示的无向图 G1的一个生成树如图 1.9(a)所示。为了更形象地表示这个生成树，
在图 1.9 中，图(b)把它画成了以顶点 1 为根结点的树，图(c)把它画成了以顶点 3 为根结点的树。
2-3 图的基本表示：邻接矩阵
在邻接矩阵存储方法中，除了一个记录各个顶点信息的顶点数组外，还有一个表示各个顶点
之间关系的矩阵，称为邻接矩阵（adjacency matrix）。两顶点相邻则为1， 不相邻则为 0
其中 V = 7 表示顶点的数量， E = 9 表示边的数量
练习的是简单图，不包含自环边和平行边
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; // 邻接矩阵
public AdjMatrix(String filename) {
File file = new File(filename);
try {
// 读取文件
Scanner scanner = new Scanner(file);
V = scanner.nextInt();
// 判断顶点数量是否有误
if (V < 0) throw new IllegalArgumentException("V 必须是个不为负数的数值");
adj = new int[V][V]; // 创建二维矩阵
E = scanner.nextInt();
if (V < 0) throw new IllegalArgumentException("E 必须是个不为负数的数值");
for (int i = 0; i< E; i++) {
int a = scanner.nextInt();
validateVertex(a);
int b = scanner.nextInt();
validateVertex(b);
// 判断是否是自环边
if (a == b) throw new IllegalArgumentException("不允许存在自环边");
if (adj[a][b] == 1) throw new IllegalArgumentException("不允许存在平行边");
adj[a][b] = 1;
adj[b][a] = 1;
}
} catch (IOException e) {
e.printStackTrace();
}
}
private void validateVertex(int v) {
if (v < 0 || v > V) {
throw new IllegalArgumentException("输入的数值" + v +"不合法");
}
}
// 获取指定结点相邻的结点
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();
}
public int V() {
return V;
}
public int E() {
return E;
}
public boolean hasEdge(int x, int y) { // 依据两个顶点判断边是否存在
validateVertex(x);
validateVertex(y);
return adj[x][y] == 1;
}
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append(String.format("V = %d, E = %d
", V, E));
// 打印出矩阵
for (int i =0; i< V; i++) {
for (int j = 0; j < V; j++) {
stringBuilder.append(String.format("%d ", adj[i][j]));
}
stringBuilder.append("
");
}
return stringBuilder.toString();
}
public static void main(String[] args) {
AdjMatrix adjMatrix = new AdjMatrix("g.txt");
System.out.println(adjMatrix);
// V = 7, E = 9
// 0 1 0 1 0 0 0
// 1 0 1 0 0 0 1
// 0 1 0 1 0 1 0
// 1 0 1 0 1 0 0
// 0 0 0 1 0 1 0
// 0 0 1 0 1 0 1
// 0 1 0 0 0 1 0
System.out.println(adjMatrix.adj(2).toString());
System.out.println(adjMatrix.degree(2));
}
}
2-4 图的基本表示：邻接表
2-6 邻接表的实现
2-7 邻接表的问题和改进
2-8 实现邻接表的改进
2-9 图的基本表示的比较
待更新。。。。。。。。。。。。。