图的引出:我之前学了线性表和树。 线性表仅限于直接前驱和直接后续关系； 树只有一个直接的前体，也就是父节点。 但是，如果需要表示多对多的关系，则需要如图所示的数据结构。
图的表示方法有两种。 http://www.Sina.com/http://www.Sina.com /
在邻接矩阵中，两个顶点相连则为1，不相连则为零。
二维数组表示（邻接矩阵）
有两种策略。 1，http://www.Sina.com/2，http://www.Sina.com /
链表表示（邻接表）深度优先遍历是图的遍历的思想。 思想首先访问当前顶点，然后以该顶点为初始顶点访问该顶点的第一个相邻顶点。 每次访问当前顶点，可以理解首先访问当前顶点的第一个相邻顶点。 此类访问策略为深度优先遍历（Depth First Search）由此可见，广度优先遍历（Broad First Search）
深度优先遍历思想:宽度优先遍历类似于分层搜索的过程。 宽度优先遍历需要使用队列来按此顺序访问这些节点的相邻节点，以维护访问的节点的顺序。
接下来举一个例子，论述深度优先扫描的思想
接下来还是用同样的例子来阐述广度优先的扫描思想：
纵向切入(深度优先应遍历到底； 广度优先就像网络，一步一步地扫描。
这是两者最大的区别
优先往纵向挖掘深入，而不是对一个结点的所有邻接结点进行横向访问
访问初始节点v，将节点v标记为已访问。 查找节点v的第一个相邻节点w。 如果w存在，则继续4；如果w不存在，则返回步骤1，从v的下一个节点继续。 如果w没有被接入，则优先地使w递归(即，把w视为另一个v，步骤123 )，寻找节点v的w相邻节点的下一个相邻节点，步骤3. 需要通过递归来实现深度优先遍历)
访问初始节点v，将节点v标记为已访问。 如果节点v进入队列且队列不为空，则继续执行，否则该算法终止。 退出队列，获取队列的第一个节点u。 查找节点u的第一个相邻节点w。 如果不存在与节点u相邻节点w，则处理进行到步骤3； 否则，循环执行三个步骤：如果6.1节点w还未被接入，则接入节点w标记为已接入。
6.2节点w排队。
找到与6.3节点u的w相邻节点后续的下一个相邻节点w，并进入步骤6。
要实现具体的代码添加，可以通过代码仔细领悟。
package com.liu.chart； import java.util.ArrayList； import java.util.LinkedList；/* * @ authorliuweixin * @ create 2021-09-208:50 *//图publicclassvertexchart {阵列列表字符串}
VertexList; int[][] edges;//用来储存顶点之间的关系 int numOfEdges;//表示边的个数 public static void main(String[] args) {// String[] data = new String[]{"A", "B", "C", "D", "E"}; String[] data = new String[]{"1", "2", "3", "4", "5", "6", "7", "8"}; VertexChart vertexChart = new VertexChart(data.length); for (String value : data) { vertexChart.addVertex(value); }// vertexChart.addEdge(0,1,1);// vertexChart.addEdge(0,2,1);// vertexChart.addEdge(1,2,1);// vertexChart.addEdge(1,3,1);// vertexChart.addEdge(1,4,1); vertexChart.addEdge(0, 1, 1); vertexChart.addEdge(0, 2, 1); vertexChart.addEdge(1, 3, 1); vertexChart.addEdge(1, 4, 1); vertexChart.addEdge(2, 5, 1); vertexChart.addEdge(2, 6, 1); vertexChart.addEdge(3, 7, 1); vertexChart.addEdge(4, 7, 1); vertexChart.addEdge(5, 6, 1); vertexChart.show(); System.out.println(); vertexChart.dfs();//深度优先遍历:1-2-4-8-5-3-6-7 System.out.println(); vertexChart.bfs();//广度优先遍历:1-2-3-4-5-6-7-8 } public VertexChart(int VertexCount) { edges = new int[VertexCount][VertexCount]; VertexList = new ArrayList<String>(VertexCount); numOfEdges = 0; } /** * 对广度优先方法的封装 */ public void bfs(){ boolean[] isVisited = new boolean[VertexList.size()]; //添加该循环的原因在于，有可能数据是分布在两张图甚至多张图上的，所以我们需要对所有的数据实现广度优先遍历 //如果数据都分布在单一的一张图上，则不需要加此循环 for (int i = 0; i < VertexList.size(); i++) {//对所有数据进行广度优先遍历 if(!isVisited[i]){//判断是否访问过 bfs(isVisited,i);//进行广度优先遍历 } } } /** *广度优先 * @param isVisited 是否被访问 * @param i 初始结点 */ public void bfs(boolean[] isVisited, int i){ int u;//表示队列的头结点对应的下标 int w;//邻接结点w //队列，记录结点访问的顺序 LinkedList queue = new LinkedList(); //访问结点，输出结点信息 System.out.print(VertexList.get(i)+ " "); //标记为已访问 isVisited[i]=true; //将结点加入队列 queue.addLast(i); while (!queue.isEmpty()){ //取出队列的头结点下标 u=(Integer)queue.removeFirst(); //得到第一个邻接结点的下标w w=getFirstNeighbor(u); while (w!=-1){//找到 //是否访问过 if(!isVisited[w]){ System.out.print(VertexList.get(w)+" "); //标记已经访问 isVisited[w]=true; //入队 queue.addLast(w); } //以u为前驱点，找w后面的下一个邻接点 w=getNextNeighbor(u,w);//体现出广度优先. } } } //对深度优先遍历方法进行封装 public void dfs() { boolean[] isVisited = new boolean[VertexList.size()]; //添加该循环的原因在于，有可能数据是分布在两张图甚至多张图上的，所以我们需要对所有的数据实现深度优先遍历 //如果数据都分布在单一的一张图上，则不需要加此循环 for (int i = 0; i < VertexList.size(); i++) {//对所有数据进行深度优先遍历 if(!isVisited[i]){//判断是否访问过 dfs(isVisited, 0);//进行深度优先 } } } /** * 深度优先遍历 * * @param isVisited 是否被访问 * @param i 初始结点 */ public void dfs(boolean[] isVisited, int i) { System.out.print(VertexList.get(i) + " "); isVisited[i] = true;//设置该点已被访问过 //获取该结点的第一个邻接结点的下标 int index = getFirstNeighbor(i); while (index != -1) {//如果循环能进来，此时表明有下一个邻接结点 if (!isVisited[index]) {//如果该结点未被访问过 //进行递归遍历+回溯 dfs(isVisited, index); } //如果该结点已被访问过 index = getNextNeighbor(i, index); } } /** * 根据前一个结点的邻接结点的下标获取下一个邻接结点 * * @param v1 * @param v2 * @return */ public int getNextNeighbor(int v1, int v2) { for (int i = v2 + 1; i < VertexList.size(); i++) { if (edges[v1][i] > 0) { return i; } } return -1; } /** * 得到该下标的第一个邻接结点 * * @param index * @return 如果找到，则返回该下标值，如果找不到，返回-1 */ public int getFirstNeighbor(int index) { for (int i = 0; i < VertexList.size(); i++) { if (edges[index][i] == 1) { return i; } } return -1; } /** * 显示图的邻接矩阵 */ public void show() { for (int[] arr : edges) { for (int data : arr) { System.out.print(data + " "); } System.out.println(); } } /** * 获取顶点的个数 * * @return 返回顶点的个数 */ public int getVexCount() { return VertexList.size(); } /** * 获取边的个数 * * @return 返回边的个数 */ public int getNumOfEdges() { return numOfEdges; } /** * 返回对应的两个顶点之间的关系 * * @param v1 第一个顶点的下标 * @param v2 第二个顶点的下标 * @return 如果返回1，则表示其可以连通；如果返回0，则表示其不连通 */ public int getWeight(int v1, int v2) { return edges[v1][v2]; } /** * 获取对应下标的顶点值 * * @param index 对应下标 * @return 返回该顶点值 */ public String getVertex(int index) { return VertexList.get(index); } /** * 把顶点的数据存储到List中 * * @param data */ public void addVertex(String data) { VertexList.add(data); } /** * 将顶点之间的关系进行表示 * * @param v1 表示点的下标，即第几个顶点 * @param v2 第二个顶点对应的下边 * @param weight 两者的关系。如果为1，则表示两者连通；如果为0，则表示两者不连通。 */ public void addEdge(int v1, int v2, int weight) { edges[v1][v2] = weight; edges[v2][v1] = weight; numOfEdges++; }}