为什么在图前学线性表和树
线性表仅限于直接前驱和直接后续的关系
树只有一个直接的前体父节点
需要表示多对多的关系时，这里用了图
图是节点可以具有0个或多个相邻元素的数据结构。 两个节点之间的连接称为边。 节点也称为顶点
图的表示方法图的表示方法有两种。 二维数组表示(邻接矩阵)； 链表表示(相邻表)。
邻接矩阵
邻接矩阵是表示图形中顶点间邻接关系的矩阵，对于n个顶点的图，矩阵用row和col表示1…n个点
邻接表
邻接矩阵需要给每个顶点分配n个边的空间，但实际上不存在的边很多，会导致空间的一定损失。
邻桌的实现只关心存在的边，不关心不存在的边。 因此，没有浪费空间，邻接表由数组链表构成
图的编写代码实现图的快速入门案例
打包图形； import com.sun.org.Apache.BCEL.internal.generic.new； import java.util.ArrayList； import java.util.Arrays； 公共类图形{私有rayliststringvertexlist； //顶点集合private int[][]edges； //与内存映射对应的邻接矩阵private int numOfEdges； //表示边数的publicstaticvoidmain (字符串[ ] args ) /测试图是否成功绘制int n=5； //节点数String VertexValue[]={'A '、' b '、' c '、' d '、' E'}； 图形图形=new graph (n； 循环添加//顶点for (字符串vertex 3360 vertex value ) graph.insertvertex )； 添加//边//A-B A-C B-C B-D B-E //边的关系不能进行for循环，只能逐个添加graph.insert edge (0，1，1 )。 //a-b graph.insert edge (0，2，1 )； //graph.insert edge (1，2，1 )； //graph.insert edge (1，3，1 )； //graph.insert edge (1，4，1 )； //B-E //显示邻接矩阵graph.showGraph (； }公共图形(intn )//初始化矩阵和veertexlistedges=newint(n )； vertex list=newarrayliststring (n； numOfEdges=0； //图中常用的方法//返回节点数public int getNumOfVertex () { return vertexList.size； //得到的边数public int getNumOfEdges () { return numOfEdges； //与返回节点I (下标)相对应的数据，例如，当输入0时返回与a相对应的数据，当输入1时返回与b相对应的数据(公共画面专家组(inti ) ) returnvertexlyindex (//v1和v2权重publicintgetweight(intv1，int v2 ) { return edges[v1][v2]； //显示图对应的矩阵publicvoidshowgraph((for ) int[]link:edges )/)先取一行，然后(system.out.println ) arrays.tost riris //边添加//weight是与边对应值，V1是点的下标，即第几个顶点//@param v1是点的下标与第几个顶点' A'-'B'-0'B'-1/@paramV2的第二个顶点对应的下标
ges[v1][v2]=weight; edges[v2][v1]=weight;//因为是无向图，所以是一样的 numOfEdges++; }}结果
图的深度优先（DFS）算法图解图遍历介绍
所谓图的遍历，即是对结点的访问。一个图有那么多个结点，如何遍历这些结点，需要特定策略，一般有两种访问策略: (1)深度优先遍历 (2)广度优先遍历
深度优先遍历基本思想
图的深度优先搜索(Depth First Search) 。
深度优先遍历，从初始访问结点出发，初始访问结点可能有多个邻接结点，深度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点， 可以这样理解：每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。
我们可以看到，这样的访问策略是优先往纵向挖掘深入，而不是对一个结点的所有邻接结点进行横向访问。
显然，深度优先搜索是一个递归的过程
深度优先遍历算法步骤
1 访问初始结点v，并标记结点v为已访问（用变量）。
2 查找结点v的第一个邻接结点w。
3 若w存在，则继续执行4，如果w不存在，则回到第1步，将从v的下一个结点继续。
4 若w未被访问，对w进行深度优先遍历递归（即把w当做另一个v，然后进行步骤123）。
5 查找结点v的w邻接结点的下一个邻接结点，转到步骤3。
例子
访问顺序： A B C D E
图的深度优先（DFS）算法代码实现这里lhzdxl好像写复杂了，建议看看网上其他的方法
//得到第一个邻接节点的下标wpublic int getFirstNeighbor(int index)//传入当前节点的下标，返回第一个邻接节点的下标w{ for(int j=0;j<vertexList.size();j++) { if(edges[index][j]==0)//说明存在下一个邻接点 { return j; } } return -1;//没有找到下一个邻接节点就返回-1} //根据前一个邻接节点的下标获取下一个邻接节点 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 void dfs(boolean [] isaVisited,int i) {//整个过程中会判断节点是否被访问//i第一次是0首先我们输出该节点 System.out.print(getValueByIndex(i)+"->");//将节点设置为已经访问 isaVisited[i]=true; int w=getFirstNeighbor(i);//然后以i这个节点进行深度遍历while(w!=-1){ if(isVisited[w]=false) { dfs(isVisited,w); } //如果w节点已经被访问 w=getNextNeighbor(i,w);} } //对dfs 进行一个重载, 遍历我们所有的结点，并进行 dfs public void dfs() { isVisited = new boolean[vertexList.size()]; //遍历所有的结点，进行dfs[回溯] for(int i = 0; i < getNumOfVertex(); i++) { if(!isVisited[i]) { dfs(isVisited, i); } } } 图的广度优先（BFS）算法图解广度优先遍历基本思想
图的广度优先搜索(Broad First Search) 。
类似于一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序来访问这些结点的邻接结点
广度优先遍历算法步骤
1 访问初始结点v并标记结点v为已访问。
2 结点v入队列
3 当队列非空时，继续执行，否则算法结束。
4 出队列，取得队头结点u。
5 查找结点u的第一个邻接结点w。
6 若结点u的邻接结点w不存在，则转到步骤3；否则循环执行以下三个步骤：
6.1 若结点w尚未被访问，则访问结点w并标记为已访问。
6.2 结点w入队列
6.3 查找结点u的继w邻接结点后的下一个邻接结点w，转到步骤6。
广度优先举例说明
先访问A，再访问A的下一个邻接节点 B，如果是深度优先，则以B节点开始找B的下一个节点即C，广度优先则是A访问B之后再以A为起始节点访问C,再看A有没有其他邻接节点，看B有没有其他节点，B的C已经被访问了，那么访问E,再访问B的D，退出条件是所有节点都被访问
图的广度优先（BFS）算法代码实现注意加入我们现在通过A找到了B，下一个判断B的下一个节点C是否和A连接，因为就算C不是B的下一个节点，我们也是要先把与A有连接的节点都遍历一遍
//对一个结点进行广度优先遍历的方法private void bfs(boolean[] isVisited, int i) {int u ; // 表示队列的头结点对应下标int w ; // 邻接结点w//队列，记录结点访问的顺序LinkedList queue = new LinkedList();//访问结点，输出结点信息System.out.print(getValueByIndex(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(getValueByIndex(w) + "=>");//标记已经访问isVisited[w] = true;//入队queue.addLast(w);}//以u为前驱点，找w后面的下一个邻结点w = getNextNeighbor(u, w); //体现出我们的广度优先}}} //遍历所有的结点，都进行广度优先搜索public void bfs() {isVisited = new boolean[vertexList.size()];for(int i = 0; i < getNumOfVertex(); i++) {if(!isVisited[i]) {bfs(isVisited, i);}}} 图的深度优先和广度优先的区别深度优先遍历顺序为 1->2->4->8->5->3->6->7
广度优先算法的遍历顺序为：1->2->3->4->5->6->7->8 （层序遍历）
链接：https://pan.baidu.com/s/16iv9o-WpIaq_l5KTjD_KzQ
提取码：e6xd