Java知识梳理之图及其应用（八）
部分代码的Github地址为：https://github.com/hzka/JavaBook02/tree/master/chap28
（一）基础知识点
1.图的应用：（1）可以用来找寻两个城市之间最小的飞行次数。或者称为寻找图中两个顶点之间的最短路径的问题；（2）哥尼斯堡七桥问题。参考链接：https://baike.baidu.com/item/%E4%B8%83%E6%A1%A5%E9%97%AE%E9%A2%98/2580504?fr=aladdin
2.图的基本术语：
2.1 图的描述：
图表示了真实世界中实体之间的关系。一个图包含了非空顶点以及一个链接顶点的边的集合；
2.2 有向图无向图权值：
有向图：每条边都有方向，可以使用有向图对父子关系进行建模；
无向图：可以在顶点之间双向移动。
权值：边可以是加权，也可以不加权。每条边都可能有一个权值。譬如：1（1）中的权值指的是飞行时间。
2.3 相邻和度
相邻：两个顶点被一条边链接，则这两个顶点称为相邻。顶点的度是指与这个顶点链接的边的条数。
度：与这个顶点连接的边的条数。有向图分入度和出度。
2.4环简单图完全图
环：一条将顶点链接到它自身的边。简单图：没有环和平行边的图。完全图：每一对节点都相连的图，譬如下面这幅。
2.5连通图回路：
连通图：任意两个顶点之间都存在一条路径，譬如上面的c图。回路是指始于一个顶点终于同一顶点的封闭路径。图的生成树是一个G的连通子图，包含所有顶点的树。
3.表示图：
3.1表示顶点
顶点可以存储在数组或线性表中。可以是String对象城市名，也可以是包含名字、人口、市长信息的实体，（P2801项目）
public class City {
public String cityname;
public int population;
public String mayor;//市长
public City(String cityname,int population,String mayor){
this.cityname = cityname;
this.population = population;
this.mayor = mayor;
}
public String getCityname() {
return cityname;
}
public void setCityname(String cityname) {
this.cityname = cityname;
}
public int getPopulation() {
return population;
}
public void setPopulation(int population) {
this.population = population;
}
public String getMayor() {
return mayor;
}
public void setMayor(String mayor) {
this.mayor = mayor;
}
}
City city0 = new City("Seattle", 608660, "Mike McGinn");
City city1 = new City("Houston", 2099451, "Annise Parker");
City[] cities = {city0, city1};3.2 表示边：边数组
可以用二维数组来表示边。
3.3表示边：Edge对象
表示边的方法是将边定义为对象，存储于ArrayList中。Edge类定义如下。这种方法适用于事先不知道所有边的情况。但3.2和3.3存在的问题都是处理效率不高，后面将介绍邻接矩阵和邻接表形式的图。
public class Edge {
int u;
int v;
public Edge(int u, int v){
this.u = u;
this.v =v;
}
@Override
public boolean equals(Object obj) {
return u==((Edge)obj).u && v==((Edge)obj).v;
}
}
ArrayList<Edge> list = new ArrayList<>();
list.add(new Edge(0,1));
list.add(new Edge(0,3));
list.add(new Edge(0,5));3.4表示边：邻接矩阵
二维数组存储，若有链接为1，无链接为0，无向图矩阵是对称的。
3.5表示边：临接线性表
可以使用数组、数组线性表或者链表来存储临接线性表。线性表较数组更容易扩充添加新的顶点。线性表较链表更高效，查找更快。故而使用线性表进行元素对象的存储。
代码实现：
List<ArrayList<Edge>> neighbours = new ArrayList<>();
neighbours.add(new ArrayList<Edge>());
neighbours.get(0).add(new Edge(0, 1));
neighbours.get(0).add(new Edge(0, 3));
neighbours.get(0).add(new Edge(0, 5));
neighbours.add(new ArrayList<Edge>());
neighbours.get(1).add(new Edge(11, 8));
neighbours.get(1).add(new Edge(11, 9));
neighbours.get(1).add(new Edge(11, 10)); 另外需要注意的是：稠密图使用邻接矩阵，稀疏图使用邻接表。使用邻接矩阵检查两定点相连只需要O(1)时间；使用临接表打印图中所有边只需要O(m)时间。m为边的个数。
4.图建模：
4.1 数据结构
我们定义Graph的接口来包含图的所有常用操作，AbstractGraph来部分实现接口，许多具体的图被添加进这一设计中。最后定义了unweightedGraph和weightedgraph。
4.2代码实现：（P2802项目，没有按照上述的UML实现，太复杂）
参考帖子：https://blog.****.net/tiantangdizhibuxiang/article/details/82057291
重点在图的构造:1.图的类型（0是无向图，1是有向图）2.顶点的数量3.边的数量4.保存顶点信息5.保存的权值。
import java.util.Scanner;
public class Main {
static final int MAXNUM = 5;//图的最大顶点数
static final int MAXVALUES = 65535;//最大值
public static void main(String[] args) {
// System.out.println("Hello World!");
GraphMaterix gm = new GraphMaterix();
creteGraph(gm);
outGraph(gm);
clearGraph(gm);
}
private static void clearGraph(GraphMaterix gm) {
for (int i = 0; i < gm.VertexNum; i++) {
for (int j = 0; j < gm.VertexNum; j++) {
gm.EdgeWeight[i][j] = 0;
}
}
}
private static void outGraph(GraphMaterix gm) {
for (int i = 0; i < gm.VertexNum; i++) {
System.out.printf("\t%c", gm.vertex[i]);//第一行输出顶点信息
}
System.out.println();
for (int i = 0; i < gm.VertexNum; i++) {
System.out.printf("%c", gm.vertex[i]);
for (int j = 0; j < gm.VertexNum; j++) {
System.out.println(gm.EdgeWeight[i][j]);
}
System.out.println();
}
}
private static void creteGraph(GraphMaterix gm) {
int i, j, k;
int weight;//权值
char startV, endV;//起始、终止顶点
System.out.println("输入顶点个数和边的个数:");
Scanner input = new Scanner(System.in);
gm.VertexNum = input.nextInt();
gm.EdgeNum = input.nextInt();
for (i = 0; i < gm.VertexNum; i++) {
System.out.println("第" + (i + 1) + "个顶点");
gm.vertex[i] = (input.next().toCharArray())[0];//保存到顶点数组中。
}
System.out.println("输入各边的顶点和权值");
for (k = 0; k < gm.EdgeNum; k++) {
System.out.println("第" + (k + 1) + "个顶点");
System.out.println("边的起点为:");
startV = input.next().charAt(0);
System.out.println("边的终点为:");
endV = input.next().charAt(0);
System.out.println("边的权值为:");
weight = input.nextInt();
for (i = 0; gm.vertex[i] != startV; i++) ;//在顶点数组中寻找起点位置
for (j = 0; gm.vertex[j] != endV; j++) ;//在顶点数组中寻找终点位置
gm.EdgeWeight[i][j] = weight;
if (gm.GType == 0) {
gm.EdgeWeight[j][i] = weight;
}
}
}
public static class GraphMaterix {
int GType;//图的类型（0是无向图，1是有向图）
int VertexNum;//顶点的数量
int EdgeNum;//边的数量
char[] vertex = new char[MAXNUM];//保存顶点信息
int[][] EdgeWeight = new int[MAXNUM][MAXNUM];//保存权值
}
}5.图的遍历
图的遍历是指访问且仅访问一次顶点过程。一般分为深度优先(DFS)和广度优先(BFS)。
参考帖子：https://blog.****.net/daijin888888/article/details/76609895
5.1深度优先遍历：
5.1.1 定义：首先访问根节点，然后递归的访问根节点的字数，尽可能搜索图中的“更深处”。可以使用递归来实现，也可以使用栈来实现。
5.1.2算法清单：
访问规则：a.如果可能，访问一个邻接的未访问顶点，标记它，并入栈。b.当不能执行a时（没有邻接的未访问顶点），如果栈不为空，就从栈中弹出一个顶点。c.如果不能执行规则a和b，就完成了整个搜索过程。
实现：(1)用peek()方法检查栈顶的顶点;(2)试图找到这个顶点还未访问的邻接点;(3)如果没有找到，出栈。(4)如果找到这样的顶点，访问并入栈。
5.2广度优先：
参考帖子：https://blog.****.net/daijin888888/article/details/76609895
5.2.1定义：逐层访问，先是根节点的所有孩子，接着是各节点的所有孙子节点，依此类推。确保每个节点访问且仅访问一次。
5.2.2算法清单：
访问规则：a.访问下一个未访问的邻接点（如果存在），这个顶点必须是当前顶点的邻接点，标记它，并入队列。b.如果因为已经没有未访问顶点而不能执行规则a，那么从队列头取一个顶点（如果存在），并使其成为当前顶点。 c.如果因为队列为空而不能执行规则b，则完成了整个搜索过程。（队头删除和访问，队尾添加）
5.3代码实现：（P2803项目）
public class Main {
private final int MAX_VERTS = 20;
private Vertex vertexList[];//顶点数组
private int adjMat[][];//邻接矩阵
private int nVerts = 0;//当前顶点总数
private StackX theStack;
private Queue theQueue;
public static void main(String[] args) {
Main theGraph = new Main();
theGraph.addVertex('A');
theGraph.addVertex('B');
theGraph.addVertex('C');
theGraph.addVertex('D');
theGraph.addVertex('E');
theGraph.addEdge(0, 1);
theGraph.addEdge(1, 2);
theGraph.addEdge(0, 3);
theGraph.addEdge(3, 4);
System.out.println("visits");
System.out.print("bfs:");
theGraph.bfs();
System.out.print("dfs:");
theGraph.dfs();
System.out.println();
// System.out.println("Hello World!");
}
public Main() {//构造图。
vertexList = new Vertex[MAX_VERTS];//顶点数组
adjMat = new int[MAX_VERTS][MAX_VERTS];//邻接矩阵
nVerts = 0;
for (int i = 0; i < MAX_VERTS; i++) {//邻接矩阵置零
for (int j = 0; j < MAX_VERTS; j++) {
adjMat[i][j] = 0;
}
}
theStack = new StackX();//初始化深度遍历所需的堆栈
theQueue = new Queue();//初始化广度遍历所需的队列
}
private void addVertex(char a) {//添加顶点
vertexList[nVerts++] = new Vertex(a);
}
private void addEdge(int start, int end) {//添加边
adjMat[start][end] = 1;
adjMat[end][start] = 1;
}
private void displayvertex(int v) {//打印v邻接的未访问的节点
System.out.print(vertexList[v].label + " ");
}
private int getAdjUnvisitedVertex(int v) {//获取和v邻接的未访问的顶点。
for (int i = 0; i < nVerts; i++) {
if (adjMat[v][i] == 1 && vertexList[i].wasVistited == false) {//在同一行且尚未访问过该节点。
return i;
}
}
return -1;
}
private void dfs() {//深度优先搜索遍历
vertexList[0].wasVistited = true;
displayvertex(0);
theStack.push(0);
while (!theStack.isEmpty()) {
int v = getAdjUnvisitedVertex(theStack.peek());
if (v == -1) {
theStack.pop();
} else {
vertexList[v].wasVistited = true;
displayvertex(v);
theStack.push(v);
}
}
for (int j = 0; j < nVerts; j++) {
vertexList[j].wasVistited = false;//重置，防止后面再次使用dfs。
}
}
private void bfs() {//广度优先搜索遍历
vertexList[0].wasVistited = true;
displayvertex(0);
theQueue.insert(0);
int v2;
while (!theQueue.isEmpty()) {
int v1 = theQueue.remove();
while ((v2 = getAdjUnvisitedVertex(v1)) != -1) {
vertexList[v2].wasVistited = true;
displayvertex(v2);
theQueue.insert(v2);
}
}
for (int j = 0; j < nVerts; j++) {
vertexList[j].wasVistited = false;//重置，防止后面再次使用dfs。
}
}
public class Vertex {//图的相关定义
public char label;//名字
public boolean wasVistited;//是否被访问
public Vertex(char label) {
this.label = label;
this.wasVistited = false;
}
}
public static class StackX {//自定义栈
private final int SIZE = 20;
private int[] st;
private int top;
public StackX() {
st = new int[SIZE];
top = -1;
}
public void push(int j) {
st[++top] = j;//先++再赋值。
}
public int pop() {
if (top == 0) {
top = -1;
return -1;
}
return st[--top];
}
public int peek() {
return st[top];
}
public boolean isEmpty() {
return (top == -1);
}
}
public class Queue {//自定义队列
private final int SIZE = 20;
private int[] queArray;
private int front;//队头删除和访问
private int rear;//队尾进行添加
public Queue() {
queArray = new int[SIZE];
front = 0;
rear = -1;
}
public void insert(int j) {//入队
if (rear == SIZE - 1) {
rear = -1;
}
queArray[++rear] = j;
}
public int remove() {//出队
if (!isEmpty()) {
return queArray[front++];
} else {
return -1;
}
}
public boolean isEmpty() {
return (rear + 1 == front);
}
}
}（二）总结：