1. 为什么需要图数据结构
我们前面学习的链表和树都不能满足多对多的关系。所以需要图这种数据结构，来实现节点之间的多对多关系
2. 图的介绍
图的节点可以具有零个或多个相邻元素。两个节点之间的连接称为边(edge)。 节点也可称为顶点(vertex)。如下所示：
图的说明：
- 路径：比如从D -> C的路径有D->B->C和D->A->B->C
- 无向图：上面的图就是一个无向图。顶点之间的连接没有方向
- 有向图：顶点之间的连接有方向。比如A -> B，只能是A -> B，不能是B -> A
- 带权图：边具有权值，比如距离大小。带权图也叫网
3. 图的表示方式
图的表示方式有两种：二维数组表示(邻接矩阵)、链表表示(邻接表)
邻接矩阵:
邻接矩阵是表示图形中顶点之间相邻关系的矩阵，对于n个顶点的图而言，矩阵是由n*n的二维矩阵表示。如下所示：
邻接表：
邻接矩阵需要为每个顶点都分配n个边的空间，其实有很多边都是不存在的, 会造成空间的一定损失
邻接表的实现只关心存在的边，不关心不存在的边。因此没有空间浪费，邻接表由数组 + 链表组成
如下所示。标号为0的节点的相关联的节点为1、2、3、4，其它的类似
4. 图的遍历
4.1 深度优先遍历
深度优先遍历也叫深度优先搜索(Depth First Search)
- 从初始访问节点出发，首先访问第一个邻接节点，然后再以这个被访问的邻接节点作为初始节点，访问它的第一个邻接节点， 依次类推
- 策略是优先往纵向挖掘深入，而不是对一个节点的所有邻接节点进行横向访问。深度优先搜索是一个递归的过程
深度优先遍历算法步骤：
- 访问初始节点v，并标记节点v为已访问
- 查找节点v的第一个邻接节点w
- 如果w不存在，则把v节点的下一个节点当作另一个v，转到步骤1
4.1 如果w存在，且未被访问，则把w当做另一个v，然后转到步骤1
4.2 此时w存在，且一定被访问过，再从v节点的w邻接节点的下一个邻接节点继续，转到步骤3
4.2 广度优先遍历
广度优先遍历也叫广度优先搜索(Broad First Search)
- 类似于一个分层搜索的过程，广度优先遍历需要使用一个队列以顺序保持访问过的节点index，然后按照这个顺序一层层的访问这些节点的邻接节点
- 策略是优先往横向挖掘，对一个节点的所有邻接节点进行横向访问。广度优先搜索是一个迭代的过程
广度优先遍历算法步骤：
- 访问初始节点v，并标记节点v为已访问，再将节点v入队列
- 当队列为空时，则把v节点的下一个节点当作另一个v，转到步骤1
- 当队列非空时，取队列头节点u，查找节点u的第一个邻接节点w
- 如果w不存在，则转到步骤2
5.1 如果w存在，且未被访问，则访问节点w，并标记节点w为已访问，再将节点w入队列
5.2 此时w存在，且一定被访问过，再从v节点的w邻接节点的下一个邻接节点继续，转到步骤4
5. 使用邻接矩阵实现图、图的深度优先遍历 + 广度优先遍历实现
程序如下：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
public class Graph {
// 顶点集合
private ArrayList<String> vertexList;
// 储存图对应的邻接矩阵
private int[][] edges;
// 边的数目
private int numOfEdges;
// 记录每个节点是否被遍历过
private boolean[] isVisited;
public static void main(String[] args) {
// 创建图对象
int vertexNum = 8;
Graph graph = new Graph(vertexNum);
//循环的添加顶点
String[] vertexs = {"A", "B", "C", "D", "E"};
for (String vertex : vertexs) {
graph.addVertex(vertex);
}
// 添加边
// A-B、A-C、B-C、B-D、B-E
graph.addEdge(0, 1, 1);
graph.addEdge(0, 2, 1);
graph.addEdge(1, 2, 1);
graph.addEdge(1, 3, 1);
graph.addEdge(1, 4, 1);
// 显示邻结矩阵
graph.showGraphEdges();
// 深度遍历测试
System.out.println("深度遍历：");
graph.dfs();
System.out.println();
// 广度遍历测试
System.out.println("广度遍历：");
graph.bfs();
System.out.println();
}
public Graph(int vertexNum) {
vertexList = new ArrayList<String>(vertexNum);
edges = new int[vertexNum][vertexNum];
numOfEdges = 0;
}
// 插入节点
public void addVertex(String vertex) {
vertexList.add(vertex);
}
// 添加边
// vertex1Index: 顶点1的index
// vertex2Index：顶点2的index
// isConnectValue：两个顶点是否连接。0表示两个顶点未连接，1表示两个顶点连接
public void addEdge(int vertex1Index, int vertex2Index, int isConnectValue) {
edges[vertex1Index][vertex2Index] = isConnectValue;
edges[vertex2Index][vertex1Index] = isConnectValue;
numOfEdges++;
}
// 获取节点的个数
public int getNumOfVertex() {
return vertexList.size();
}
// 获取边的数目
public int getNumOfEdges() {
return numOfEdges;
}
// 根据传递的index，获取顶点的值
public String getVertexValueByIndex(int vertexIndex) {
return vertexList.get(vertexIndex);
}
// 根据vertex1Index和vertex2Index，获取两个顶点是否连接的值
public int getIsConnectValue(int vertex1Index, int vertex2Index) {
return edges[vertex1Index][vertex2Index];
}
// 显示图对应的邻接矩阵
public void showGraphEdges() {
for (int[] line : edges) {
System.out.println(Arrays.toString(line));
}
}
// 根据一个节点的index，查询它的第一个邻接节点的index。查询不到则返回-1
public int getFirstNeighborIndex(int vertexIndex) {
for (int i = 0; i < vertexList.size(); i++) {
if (edges[vertexIndex][i] > 0) {
return i;
}
}
return -1;
}
// 获取一个节点的邻接节点的下一个邻接节点的index
public int getNextNeighborIndex(int vertexIndex, int neighborIndex) {
for (int i = neighborIndex + 1; i < vertexList.size(); i++) {
if (edges[vertexIndex][i] > 0) {
return i;
}
}
return -1;
}
// 深度优先遍历。打印所有顶点的信息，每个顶点只打印一次
public void dfs() {
isVisited = new boolean[vertexList.size()];
// 如果w不存在，则把v节点的下一个节点当作另一个v，转到步骤1
for (int vertexIndex = 0; vertexIndex < getNumOfVertex(); vertexIndex++) {
if (!isVisited[vertexIndex]) {
dfs(isVisited, vertexIndex);
}
}
}
// 深度优先遍历算法实现。其中vertexIndex为顶点的index
private void dfs(boolean[] isVisited, int vertexIndex) {
// 访问初始节点v，并标记节点v为已访问
System.out.print("->" + getVertexValueByIndex(vertexIndex));
isVisited[vertexIndex] = true;
// 查找节点v的第一个邻接节点w
int w = getFirstNeighborIndex(vertexIndex);
while (w != -1) {
// 如果w存在，且未被访问，则把w当做另一个v，然后转到步骤1
if (!isVisited[w]) {
dfs(isVisited, w);
}
// 此时w存在，且一定被访问过，再从v节点的w邻接节点的下一个邻接节点继续，转到步骤3
w = getNextNeighborIndex(vertexIndex, w);
}
}
// 广度优先遍历。打印所有顶点的信息，每个顶点只打印一次
public void bfs() {
isVisited = new boolean[vertexList.size()];
// 当队列为空时，则把v节点的下一个节点当作另一个v，转到步骤1
for (int vertexIndex = 0; vertexIndex < getNumOfVertex(); vertexIndex++) {
if (!isVisited[vertexIndex]) {
bfs(isVisited, vertexIndex);
}
}
}
// 广度优先遍历算法实现。其中vertexIndex为顶点的index
private void bfs(boolean[] isVisited, int vertexIndex) {
// 表示队列头节点对应的index
int u;
// 当前处理节点的一个邻接节点的index
int w;
// 使用队列顺序保持访问过的节点index
LinkedList<Integer> queue = new LinkedList();
// 访问初始节点v，并标记节点v为已访问，再将节点v入队列
System.out.print("->" + getVertexValueByIndex(vertexIndex));
isVisited[vertexIndex] = true;
queue.addLast(vertexIndex);
while (!queue.isEmpty()) {
// 当队列非空时，取队列头节点u，查找节点u的第一个邻接节点w
u = queue.removeFirst();
w = getFirstNeighborIndex(u);
while (w != -1) {
if (!isVisited[w]) {
// 如果w存在，且未被访问，则访问节点w，并标记节点w为已访问，再将节点w入队列
System.out.print("->" + getVertexValueByIndex(w));
isVisited[w] = true;
queue.addLast(w);
}
// 此时w存在，且一定被访问过，再从v节点的w邻接节点的下一个邻接节点继续，转到步骤4
// 广度优先和深度优先的关键区别在这里。访问了当前节点和当前节点的一个邻接节点，
// 然后继续访问当前节点的后面所有邻接节点
w = getNextNeighborIndex(u, w);
}
}
}
}
运行程序，结果如下：
[0, 1, 1, 0, 0, 0, 0, 0]
[1, 0, 1, 1, 1, 0, 0, 0]
[1, 1, 0, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0]
深度遍历：
->A->B->C->D->E
广度遍历：
->A->B->C->D->E