Graph图结构是一种比树结构更复杂的非线性结构。在树形结构中，节点之间存在分支的层次关系，每一层的节点最多只能与上一层的一个节点相关，但可能与下一层的多个节点相关。在图结构中，任意两个节点都可能相关，即节点之间的邻接关系可以是任意的。因此，图结构被用来描述各种复杂的数据对象，在自然科学、社会科学、人文科学等诸多领域都有非常广泛的应用。图结构在计算机科学、人工智能、电子电路分析、最短路径寻找、工程规划、化合物分析、统计力学、遗传学、控制论语言学和社会科学等方面都有不同程度的应用。可以说，图结构是所有数据结构中使用最广泛的。比如地铁站的线图：图的定义图是一种数据结构，其中一个节点可以有零个或多个相邻元素，两个节点的连接称为边，节点也称为在图结构中，从一个顶点到另一个顶点的路径称为路径。有3种图结构：无向图、有向图和带权图图：顶点A和顶点B之间的边是有向的，可以从A到B，但不能从B到A顶点A和顶点B有属性，比如A到B的距离。图有两种表达方式：邻接矩阵（使用二维数组）和邻接表（使用数组+链表）adjacencymatrixadjacencymatrix是到表示图中顶点之间的关系，矩阵的行和列对应于每个顶点，坐标位置处的值是为它们之间的关系，1是连通的，0是不连通的。在程序中，是用一个二维数组来实现的。邻接表邻接表只关心存在的边，不需要为不存在的边分配空间。因此，与邻接矩阵相比，避免了不必要的空间浪费。在程序中，以数组+链表的形式实现。数组存储对应的顶点，链表存储该顶点连接的所有顶点。图搜索算法图结构基本属性和方法下面的代码演示都是以邻接矩阵的形式实现的//图结构（邻接矩阵）classGraph{//存储图中所有的顶点privateListvertexes;//Graphics的结构体的邻接矩阵privateint[][]matrix;//每个顶点的访问状态，true表示访问过，false表示未访问privateboolean[]visited;/***根据传入的顶点信息生成矩阵*@params*/publicGraph(Strings[]){vertexes=newArrayList<>();for(Stringvertex:s){vertexes.add(vertex);}matrix=newint[s.length][s.length];}/***将两个Vertexconnection，即生成的边*@paramindex1顶点在set*@paramindex2*/publicvoidconnect(intindex1,intindex2){if(index1<0||index1>matrix.length||index2<0||index2中的索引>matrix.length){thrownewRuntimeException("顶点不存在");}//将新的邻接添加到邻接矩阵matrix[index1][index2]=1;matrix[index2][index1]=1;}/***显示邻接矩阵*/publicvoidshowGraphMatrix(){for(intarr[]:matrix){System.out.println(Arrays.toString(arr));}}/***获取邻接矩阵对应行中的顶点邻接顶点下标*@paramrow*@return有邻接顶点时返回邻接顶点下标，返回-1*/publicintgetFirstNeighbor(introw){for(inti=0;i");//设置当前顶点为visited[row]=true;//获取当前顶点的相邻顶点的下标intindex=getFirstNeighbor(row);//如果当前顶点有相邻顶点，则进行深度搜索while(index!=-1){//当相邻顶点未被访问时，递归遍历if(visited[index]!=true){dsf(visited,index);}//当相邻顶点已被访问时，再搜索另一个相邻顶点index=getNeighbor(row,index);}}widthfirstsearchwidth优先搜索算法（又称广度优先搜索）是最简单的图搜索算法之一，该算法也是许多重要图算法的原型。Dijkstra的单源最短路径算法和Prim的最小生成树算法都使用了类似广度优先搜索的思想。它的别名也叫BFS，属于一种盲目搜索的方法，目的是对图中的所有节点进行系统的扩展和检查，找到结果。换句话说，它会详尽地搜索整个图，直到找到结果，而不管结果可能在哪里。广度优先搜索算法类似于分层搜索过程。广度优先搜索算法需要一个队列来保持被访问顶点的顺序，以便按照这个顺序访问这些顶点的相邻顶点。思路：依次访问当前顶点的相邻顶点，将这些相邻的顶点按照访问的先后顺序存放到队列中。当当前顶点的所有相邻顶点都被访问时，从队列中弹出一个顶点，并以该顶点为当前顶点继续处理。步骤，直到所有的顶点都被访问过。依次访问当前顶点的所有相邻顶点，并将这些相邻的顶点按照访问的先后顺序存入队列中，虽然图中所有的顶点都被访问过，但是直到队列中的所有顶点都访问完，算法才会结束弹出访问];////广度优先搜索bfs(visited,0);}/***广度优先搜索*@paramvisited*@paramrow*/publicvoidbfs(boolean[]visited,introw){//创建一个队列来存储遍历相邻顶点的顺序LinkedListqueue=newLinkedList();//输出当前顶点System.out.print(vertexes.get(row)+"->");//反转当前顶点Setasvisited[row]=true;//将当前顶点加入队列queue.add(row);//当队列不为空时，有未搜索的相邻顶点，搜索while(!queue.isEmpty()){//从队列中依次弹出相邻顶点下标intlast=(Integer)queue.removeFirst();//获取出栈顶点的相邻顶点下标intindex=getFirstNeighbor(last);//当出栈顶点有相邻顶点时，执行广度搜索while(index!=-1){//当出栈顶点相邻顶点未被访问if(visited[index]!=true){//输出相邻顶点System.out.print(vertexes.get(index)+"->");//设置相邻顶点为已访问[index]=true;//将相邻顶点加入队列queue.addLast(iindex);}//继续搜索弹出一个顶点的另一个相邻顶点index=getNeighbor(last,index);}}}完整演示代码publicclassGraphDemo{publicstaticvoidmain(String[]args){String[]s={"t;A","B","C","D","E","F","G"};Graphgraph=newGraph(s);//A-BA-CA-GA-FF-DF-ED-EE-Ggraph.connect(0,1);graph.connect(0,2);graph.connect(0,6);graph.connect(0,5);graph.connect(5,3);graph.connect(5,4);graph.connect(3,4);graph.connect(4,6);graph.showGraphMatrix();graph.dsf();//A->B->C->F->D->E->G->System.out.println();graph.bfs();//A->B->C->F->G->D->E->}}//图结构classGraph{//存储图中的所有顶点privateListvertexes;//图结构的邻接矩阵privateint[][]matrix;//每个顶点的访问状态，true表示访问过，false表示unvisitedprivateboolean[]visited;/***根据传入的顶点信息生成矩阵*@params*/publicGraph(Strings[]){vertexes=newArrayList<>();for(Stringvertex:s){vertexes.add(vertex);}matrix=newint[s.length][s.length];}/***连接两个顶点，即在set*@paramindex2*/publicvoidconnect(intindex1,intindex2)中生成一个edge*@paramindex1顶点索引){if(index1<0||index1>matrix.length||index2<0||index2>matrix.length){thrownewRuntimeException("顶点不存在");}//Matrix[index1][index2]=1;matrix[index2][index1]=1;}/***显示邻接矩阵*/publicvoidshowGraphMatrix(){for(intarr[]:matrix){System.out.println(Arrays.toString(arr));}}publicvoiddsf(){visited=newboolean[vertexes.size()];//集合中对于下标为0的顶点,执行深度优先搜索dsf(visited,0);}/***深度优先搜索*@paramvisited*@paramrow*/publicvoiddsf(boolean[]visited,introw){//输出当前顶点System.out.print(vertexes.get(row)+"->");//设置当前顶点为visited[row]=true;//获取当前顶点的相邻顶点的下标intindex=getFirstNeighbor(row);//如果当前顶点有相邻顶点，进行深度搜索while(index!=-1){//当相邻顶点没有被访问时，递归遍历if(visited[index]!=true){dsf(visited,index);}//当相邻的顶点已经被访问过后，再寻找另一个相邻的顶点index=getNeighbor(row,index);}}publicvoidbfs(){visited=newboolean[vertexes.size()];////对集合中下标为0的顶点，进行广度优先搜索bfs(visited,0);}/***广度优先搜索*@paramvisited*@paramrow*/publicvoidbfs(boolean[]visited,introw){//创建队列，存储遍历相邻顶点的顺序Queuequeue=newArrayDeque();//输出当前顶点System.out.print(vertexes.get(row)+"->");//设置当前顶点为visited[row]=true;//将当前顶点加入队列queue.add(row);//当队列不为空，即有未搜索的相邻顶点时，搜索while(!queue.isEmpty()){//从队列中按顺序弹出相邻顶点intlast=(Integer)queue.poll();//获取弹出顶点的相邻顶点的下标intindex=getFirstNeighbor(last);//当弹出顶点有相邻顶点时，执行广度搜索while(index!=-1){//当相邻顶点未被访问时if(visited[index]!=true){//输出相邻顶点System.out.print(vertexes.get(index)+"->");//设置相邻顶点Visited[index]=true;//将相邻顶点加入队列queue.add(index);}//继续寻找弹出顶点的另一个相邻顶点index=getNeighbor(last,index);}}}/***获取邻接矩阵对应行中顶点的第一个邻接顶点的下标*@paramrow*@return有邻接时返回邻接顶点的下标顶点，或返回-1*/publicintgetFirstNeighbor(introw){for(inti=0;i
