图论算法-求(有向)图中任意两点间所有路径

求（有向）图中任意两点间所有路径1建图：图类中包括如下信息：顶点集合，邻接矩阵。节点类中包括如下信息：是否被访问过，节点的名称，从这个节点访问到下一个节点的集合

<!--[endif]-->图1

<!--[endif]-->图22算法思路A将始点设置为已访问，将其入栈B查看栈顶节点V在图中，有没有可以到达、且没有入栈、且没有从这个节点V出发访问过的节点C如果有，则将找到的这个节点入栈D如果没有，则将节点V访问到下一个节点的集合中每个元素赋值为零，V出栈E当栈顶元素为终点时，设置终点没有被访问过，打印栈中元素，弹出栈顶节点F重复执行B–E,直到栈中元素为空Java代码packageutil;publicclassGraph{privateVertexvertexList[];//listofverticesprivateintadjMat[][];//adjacencymatrixprivateintnVerts;privatestaticintMAX_VERTS=7;//n个点inti=0;intj=0;publicVertex[]getVertexList(){returnvertexList;}publicint[][]getAdjMat(){returnadjMat;}publicintgetN(){returnMAX_VERTS;}publicGraph(intindex){adjMat=newint[MAX_VERTS][MAX_VERTS];//邻接矩阵vertexList=newVertex[MAX_VERTS];//顶点数组nVerts=0;for(i=0;i<MAX_VERTS;i++){for(j=0;j<MAX_VERTS;j++){adjMat[i][j]=0;}}addVertex('A');addVertex('B');addVertex('C');addVertex('D');addVertex('E');addVertex('F');addVertex('G');addEdge(0,1);addEdge(0,2);addEdge(1,4);addEdge(2,0);addEdge(2,5);addEdge(3,0);addEdge(3,2);addEdge(3,3);addEdge(4,1);addEdge(4,2);addEdge(5,6);addEdge(6,3);switch(index){case0:break;case1:delEdge(4,2);break;default:break;}}privatevoiddelEdge(intstart,intend){adjMat[start][end]=0;}privatevoidaddEdge(intstart,intend){//有向图，添加边adjMat[start][end]=1;//adjMat[end][start]=1;}publicvoidaddVertex(charlab){vertexList[nVerts++]=newVertex(lab);//添加点}publicchardisplayVertex(inti){returnvertexList[i].getLabel();}publicbooleandisplayVertexVisited(inti){returnvertexList[i].WasVisited();}publicvoidprintGraph(){for(i=0;i<MAX_VERTS;i++){System.out.print("第"+displayVertex(i)+"个节点:"+"");for(j=0;j<MAX_VERTS;j++){System.out.print(displayVertex(i)+"-"+displayVertex(j)+"："+adjMat[i][j]+"");}System.out.println();}}}packageutil;Java代码importjava.util.ArrayList;publicclassVertex{booleanwasVisited;//是否遍历过publiccharlabel;//节点名称ArrayList<Integer>allVisitedList;//节点已访问过的顶点publicvoidsetAllVisitedList(ArrayList<Integer>allVisitedList){this.allVisitedList=allVisitedList;}publicArrayList<Integer>getAllVisitedList(){returnallVisitedList;}publicbooleanWasVisited(){returnwasVisited;}publicvoidsetWasVisited(booleanwasVisited){this.wasVisited=wasVisited;}publicchargetLabel(){returnlabel;}publicvoidsetLabel(charlabel){this.label=label;}publicVertex(charlab)//constructor{label=lab;wasVisited=false;}publicvoidsetVisited(intj){allVisitedList.set(j,1);}}packageutil;Java代码importjava.util.ArrayList;importjava.util.Stack;publicclassAF{booleanisAF=true;Graphgraph;intn;intstart,end;Stack<Integer>theStack;privateArrayList<Integer>tempList;privateStringcounterexample;publicAF(Graphgraph,intstart,intend){this.graph=graph;this.start=start;this.end=end;}publicbooleangetResult(){graph.printGraph();n=graph.getN();theStack=newStack<Integer>();if(!isConnectable(start,end)){isAF=false;counterexample="节点之间没有通路";}else{for(intj=0;j<n;j++){tempList=newArrayList<Integer>();for(inti=0;i<n;i++){tempList.add(0);}graph.getVertexList()[j].setAllVisitedList(tempList);}isAF=af(start,end);}returnisAF;}privatebooleanaf(intstart,intend){graph.getVertexList()[start].setWasVisited(true);//markittheStack.push(start);//pushitwhile(!theStack.isEmpty()){intv=getAdjUnvisitedVertex(theStack.peek());if(v==-1)//ifnosuchvertex,{tempList=newArrayList<Integer>();for(intj=0;j<n;j++){tempList.add(0);}graph.getVertexList()[theStack.peek()].setAllVisitedList(tempList);//把栈顶节点访问过的节点链表清空theStack.pop();}else//ifitexists,{theStack.push(v);//pushit}if(!theStack.isEmpty()&&end==theStack.peek()){graph.getVertexList()[end].setWasVisited(false);//markitprintTheStack(theStack);System.out.println();theStack.pop();}}returnisAF;}//判断连个节点是否能连通privatebooleanisConnectable(intstart,intend){ArrayList<Integer>queue=newArrayList<Integer>();ArrayList<Integer>visited=newArrayList<Integer>();queue.add(start);while(!queue.isEmpty()){for(intj=0;j<n;j++){if(graph.getAdjMat()[start][j]==1&&!visited.contains(j)){queue.add(j);}}if(queue.contains(end)){returntrue;}else{visited.add(queue.get(0));queue.remove(0);if(!queue.isEmpty()){start=queue.get(0);}}}returnfalse;}publicStringcounterexample(){for(Integerinteger:theStack){counterexample+=graph.displayVertex(integer);if(integer!=theStack.peek()){counterexample+="-->";}}returncounterexample;}//与节点v相邻，并且这个节点没有被访问到，并且这个节点不在栈中publicintgetAdjUnvisitedVertex(intv){ArrayList<Integer>arrayList=graph.getVertexList()[v].getAllVisitedList();for(intj=0;j<n;j++){if(graph.getAdjMat()[v][j]==1&&arrayList.get(j)==0&&!theStack.contains(j)){graph.getVertexList()[v].setVisited(j);returnj;}}return-1;}//endgetAdjUnvisitedVertex()publicvoidprintTheStack(Stack<Integer>theStack2){for(Integerinteger:theStack2){System.out.print(graph.displayVertex(integer));if(integer!=theStack2.peek()){System.out.print("-