前言
后面介绍各种树的一些状况，明天聊一种非凡的数据结构：图
为什么要有图？
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 ->