共计 6523 个字符，预计需要花费 17 分钟才能阅读完成。
前言
后面介绍各种树的一些状况，明天聊一种非凡的数据结构：图
为什么要有图？
1、后面咱们学习到的线性表与树
2、线性表局限一个间接前驱和一个间接后续的关系
3、树也只能有一个间接前驱、也就是父节点
4、咱们须要多对多的关系的时候，就须要应用到图
一、什么是图
图的根本介绍
图是一种数据结构，其中结点能够具备零个或多个相邻元素，两个节点之间的连贯称为边、结点也能够称为顶点
图的罕用常识概念
图的常见表达方式
图的表达方式有两种：二维数组示意（领接矩阵）；链表示意（邻接表）
顶点 0 -> 顶点 1、2、3、4、5、时，若能连通则是 1，否则 0 示意
二、通过示例意识图
图的疾速入门案例
依据如图所示，应用邻接矩阵展现连贯成果，1 示意能连贯 0- 示意不能连贯
思路剖析
1. 应用汇合的形式存储节点信息
2. 应用二维数组[][] 保留矩阵信息
3. 初始化节点个数 n 时，汇合长度为 n，二维码数组长度为 n * n
4. 增加两个节点之间的连贯时，须要记录两个节点的下标
public class Graph {
private ArrayList<String > vertexList;// 存储顶点的汇合
private int[][] edges;// 存储顶点对应图的邻接矩阵
private int numOfEdges;// 示意边的数目
// 结构器
public Graph(int n){edges = new int[n][n];
vertexList = new ArrayList<String>(n);
numOfEdges = 0;
}
// 插入节点
public void insertVertex(String vertex){vertexList.add(vertex);
}
// 增加边
public void insertEdge(int v1,int v2,int weight){edges[v1][v2] = weight;
edges[v2][v1] = weight;
numOfEdges++;
}
// 返回目前的节点个数
public int getNumOfVertex(){return vertexList.size();
}
// 失去目前边的个数
public int getNumOfEdges(){return numOfEdges;}
// 返回下标对应节点数据
public String getValueByIndex(int i){return vertexList.get(i);
}
// 返回两个节点之间的权值
public int getWeight(int v1,int v2){return edges[v1][v2];
}
// 显示图对应的矩阵
public void showGraph(){for(int[] link :edges){System.out.println(Arrays.toString(link));
}
}
}接下来咱们依照图所示，将节点：A、B、C、D、E 增加进 demo 看看
public static void main(String[] args) {
// 节点的数组
String[] arr = {"A","B","C","D","E"};
// 创立图对象
Graph graph = new Graph(arr.length);
// 循环增加顶点项
for(String data :arr){graph.insertVertex(data);
}
graph.showGraph();}
运行后果如下：[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/B-A、A-C/C-A、B-C/C-B、B-E/E-B、B-D/D-B
public static void main(String[] args) {
// 节点的数组
String[] arr = {"A","B","C","D","E"};
// 创立图对象
Graph graph = new Graph(arr.length);
// 循环增加顶点项
for(String data :arr){graph.insertVertex(data);
}
//graph.showGraph();
// 增加边 //`A-B/B-A、A-C/C-A、B-C/C-B、B-E/E-B、B-D/D-B`
graph.insertEdge(0,1,1);//`A-B
graph.insertEdge(0,2,1);//`A-C
graph.insertEdge(1,2,1);//`B-C
graph.insertEdge(1,4,1);//`B-E
graph.insertEdge(1,3,1);//`B-D
graph.showGraph();}
运行后果如下：[0, 1, 1, 0, 0]
[1, 0, 1, 1, 1]
[1, 1, 0, 0, 0]
[0, 1, 0, 0, 0]
[0, 1, 0, 0, 0]咱们能够比照一下下面的图，是否正确关联起来
图遍历介绍
所谓的图遍历，即是对结点的拜访。
一个图有那么多个结点，如何遍历这些结点？
须要特定策略，个别有两种拜访策略: (1)深度优先遍历 (2) 广度优先遍历
三、图的深度优先遍历介绍
图的深度优先搜寻(Depth First Search)
1. 首先拜访第一个邻接结点，而后 再以这个被拜访的邻接结点 作为 初始结点 ，拜访 它的第一个邻接结点
（每次都在拜访完以后结点后，再以之前拜访的以后结点的第一个邻接结点）
2. 这样的拜访策略是优先往纵向开掘深刻，而不是对一个结点的所有邻接结点进行横向拜访
深度优先遍历算法步骤
1. 拜访 初始结点 v ，并 标记结点 v 为已拜访
2. 查找 结点 v 的 第一个邻接结点 w
3. 若 w 存在，则继续执行 4，如果 w 不存在，则回到第 1 步，将 从 v 的下一个结点 持续
4. 若 w 未被拜访，对 w 进行深度优先遍历递归（即把 w 当做另一个 v，而后进行步骤 123）
5. 查找结点 v 的 w 邻接结点的下一个邻接结点，转到步骤 3
以下面创立的图，进行一个示例深度优先遍历的图解剖析，假如初始点：A
援用示例图解剖析算法步骤
第一步：拜访初始结点 v，并标记结点 v 为已拜访
第二步：查找结点 v 的第一个邻接结点 w
第三步：若 w 存在，则继续执行，查看若 w 是否未被拜访，则对 w 进行深度优先遍历递归（即把 w 当做另一个 v，而后进行步骤 123），如果 w 不存在，则回到第 1 步，将 从 v 的下一个结点 持续，
第四步：将 w 节点当做另一个 v，执行步骤 1 -2-3
第五步：C 的邻接节点不存在，返回上一层，即是 B 节点，从下一个节点持续
第六步：D 的邻接节点不存在，返回上一层，即是 B 节点，从下一个节点持续
深度优先搜寻代码实现
1. 咱们须要记录某个节点是否被拜访
2. 咱们查找节点 V 的邻接节点 W，须要晓得 w 的下标，所以需要求出 w 的下标
依据咱们后面的二维数组以及遍历思路，A 的下一邻接节点 B，就是[A][B] >0
// 失去领接节点的下标
public int getFirstNeighbor(int index){for (int j =0; j<vertexList.size() ; j++){if(edges[index][j] > 0){return j;}
}
return -1;
}3. 咱们查找新节点 V 的邻接节点 W，须要依据前一个邻接节点的下标获取
咱们须要 C 的节点邻接节点 W，就须要前一个邻接节点 C 的下标
// 依据前一个邻接节点的下标获取下一个领接节点
public int getNextNeighbor(int v1,int v2){for (int j = v2 +1 ;j<vertexList.size();j++){if(edges[v1][j] >0){return j;}
}
return -1;
}那么依照图解思路，咱们的算法办法代码（有缺点，只能拜访一次）就是
public class Graph {
// 省略之前要害代码
private boolean[] isVisited;// 记录某个节点是否被拜访
// 结构器
public Graph(int n){edges = new int[n][n];
vertexList = new ArrayList<String>(n);
numOfEdges = 0;
isVisited = new boolean[n];
}
// 深度优先遍历办法
public void dfs(boolean [] isVisited,int i ){
// 输入节点进行拜访
System.out.print(getValueByIndex(i) + "- >");
// 标记已拜访
isVisited[i] = true;
// 查找以后节点 i 的邻接节点 w
int w = getFirstNeighbor(i);
while(w != -1){
// 邻接节点 w 未被拜访
if(!isVisited[w]){dfs(isVisited,w);
}
// 如果 w 被拜访过了
w = getNextNeighbor(i,w);
}
}
public void dfs(){for(int j=0; j< getNumOfVertex(); j++){if(!isVisited[j]){dfs(isVisited,j);
}
}
}咱们依据之前增加的 demo 测试遍历输入看看
public static void main(String[] args) {
// 节点的数组
String[] arr = {"A","B","C","D","E"};
// 创立图对象
Graph graph = new Graph(arr.length);
// 循环增加顶点项
for(String data :arr){graph.insertVertex(data);
}
//graph.showGraph();
// 增加边
//`A-B/B-A、A-C/C-A、B-C/C-B、B-E/E-B、B-D/D-B`
graph.insertEdge(0,1,1);//`A-B
graph.insertEdge(0,2,1);//`A-C
graph.insertEdge(1,2,1);//`B-C
graph.insertEdge(1,4,1);//`B-E
graph.insertEdge(1,3,1);//`B-D
graph.showGraph();
graph.dfs();}
运行后果如下：[0, 1, 1, 0, 0]
[1, 0, 1, 1, 1]
[1, 1, 0, 0, 0]
[0, 1, 0, 0, 0]
[0, 1, 0, 0, 0]
A - >B - >C - >D - >E - >四、图的广度优先遍历介绍
图的广度优先搜寻(Broad First Search)
1. 相似于一个分层搜寻的过程
2. 广度优先遍历须要应用一个队列以放弃拜访过的结点的程序，以便按这个程序来拜访这些结点的邻接结点
广度优先遍历算法步骤
1. 拜访 初始结点 v 并 标记 结点 v 为 已拜访 。
2. 结点 v 入队列
3. 当队列 非空时继续执行 ，否则 初始结点 v 的算法 完结。
4. 出队列，获得 队列头结点 u 。
5. 查找 结点 u 的 第一个邻接结点 w 。
6. 若结点 u 的 邻接结点 w 不存在 ，则转到 步骤 3 ；
否则循环执行以下三个步骤：
6.1 若结点 w 尚 未被拜访 ，则拜访结点 w 并 标记为已拜访 。
6.2 把 结点 w 入队列
6.3 接着查找结点 u 的 继 w 邻接结点后 的下一个邻接结点，当做 w 转到步骤 6。
以下面创立的图，进行一个示例广度优先遍历的图解剖析，假如初始点：A
援用示例图解剖析算法步骤
第一步：拜访初始结点 v，并标记结点 v 为已拜访，并将节点 v 入队列
第二步：此时出队列，获取队列头结点 u，查结点 u 的第一个邻接结点 w
第三步：如果 w 不存在，则回到第二步，查问结点 u 的继 w 的下一个 邻接节点结点 持续。若 w 存在，则查看 w 是否未被拜访，未拜访则对 w 进行标记拜访，并且 入队列 ，且持续查找 继 w 邻接节点后的下一个节点 当做 w，接着判断
第四步: 接着查找结点 u 的 继 w 邻接结点后 的下一个邻接结点，当做结点 w
第五步：如果 w 不存在，则回到第二步，查问结点 u 的继 w 的下一个 邻接节点结点 持续。若 w 存在，则查看 w 是否未被拜访，未拜访则对 w 进行标记拜访，并且 入队列 ，且持续查找 继 w 邻接节点后的下一个节点 当做 w，接着判断
第六步: 接着查找结点 u 的 继 w 邻接结点后 的下一个邻接结点，当做结点 w
第七步：如果 w 不存在，则回到第二步，查问结点 u 的继 w 的下一个 邻接节点结点 持续，直至完结回到思路的第二步，代表结点 u（A）完结
第八步：出队列，获得队列头结点 U、进行查找邻接结点 w
第九步：如果 w 不存在，则回到第二步，查问结点 u 的继 w 的下一个 邻接节点结点 持续。若 w 存在，则查看 w 是否未被拜访，未拜访则对 w 进行标记拜访，并且 入队列 ，且持续查找 继 w 邻接节点后的下一个节点 当做 w，接着判断
第十步：接着查找结点 u 的 继 w 邻接结点后 的下一个邻接结点，当做结点 w
第十一步：如果 w 不存在，则回到第二步，查问结点 u 的继 w 的下一个 邻接节点结点 持续。若 w 存在，则查看 w 是否未被拜访，未拜访则对 w 进行标记拜访，并且 入队列 ，且持续查找 继 w 邻接节点后的下一个节点 当做 w，接着判断
第十二步：如果 w 不存在，则回到第二步，查问结点 u 的继 w 的下一个 邻接节点结点 持续，直至完结回到思路的第二步，代表结点 u（B）完结
广度优先搜寻代码实现
1. 咱们能够先一个节点的广度优先方法，其次其余节点循环调用即可
// 对一个节点进行广度优先遍历办法
public void bfs(boolean[] isVisited,int i ){
int u;// 示意队列头节点的下标
int w;// 示意邻接节点的下标
// 须要一个队列记录拜访的程序
LinkedList queue = new LinkedList();
// 拜访节点，输入节点信息
System.out.print(getValueByIndex(i) + "->");
isVisited[i] = true;
// 将节点退出队列，记录拜访程序
// 队列尾部增加，头部取
queue.addLast(i);
while (!queue.isEmpty()){
// 取出队列的头结点，删掉
u = (Integer) queue.removeFirst();
// 查找头结点 u 的邻接节点
w = getFirstNeighbor(u);
//w != -1 代表找到邻接节点
while(w!= -1){
// 判断是否拜访过
if(!isVisited[w]){
// 若没有拜访过，则输入并标记已拜访
System.out.print(getValueByIndex(i) + "->");
isVisited[w] = true;
// 将节点入队列，代表拜访过
queue.addLast(w);
}
// 以 u 为终点，查找 w 邻接结点的下一个邻接结点
w = getNextNeighbor(u,w);
}
}
}2. 接下来则遍历所有节点进行广度优先搜寻
// 广度优先遍历办法
public void bfs(){for(int j=0; j< getNumOfVertex(); j++){
// 没有被拜访过才进行广度优先搜寻
if(!isVisited[j]){bfs(isVisited,j);
}
}
}咱们依据之前增加的 demo 测试遍历输入看看
public static void main(String[] args) {
// 节点的数组
String[] arr = {"A","B","C","D","E"};
// 创立图对象
Graph graph = new Graph(arr.length);
// 循环增加顶点项
for(String data :arr){graph.insertVertex(data);
}
//graph.showGraph();
// 增加边
//`A-B/B-A、A-C/C-A、B-C/C-B、B-E/E-B、B-D/D-B`
graph.insertEdge(0,1,1);//`A-B
graph.insertEdge(0,2,1);//`A-C
graph.insertEdge(1,2,1);//`B-C
graph.insertEdge(1,4,1);//`B-E
graph.insertEdge(1,3,1);//`B-D
graph.showGraph();
//graph.dfs();
graph.bfs();}
运算后果如下：[0, 1, 1, 0, 0]
[1, 0, 1, 1, 1]
[1, 1, 0, 0, 0]
[0, 1, 0, 0, 0]
[0, 1, 0, 0, 0]
A ->B ->C ->D ->E ->
