【数据结构】判别以邻接表方式存储的有向图是否存在顶点Vi到Vj的路径

代码实现：

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;/*** Created by IntelliJ IDEA** @author manzuo* @date 2018/12/14 23:52* 以邻接表的作为存储方式，分别以广度优先和深度优先的算法判别有向图G是否存在顶点Vi到定点Vj的路径*/
public class AdjacencyList {public static void main(String[] args) {Scanner in  = new Scanner(System.in);CreateGraph createGraph = new CreateGraph();createGraph.initGraph();createGraph.outputGraph();int i,j;System.out.println("输入i，j 的值");i = in.nextInt();j = in.nextInt();createGraph.DFSTravel(i,j);createGraph.BFSTravel(i,j);}
}
class Vertex{ //顶点类String vername;//顶点的名称Vertex nextNode;//下一个顶点
}
class Graph{ //图类Vertex[] vertices;//顶点数组，存放所有顶点int verNum = 0;//顶点数量int edgeNum = 0;//边的数量
}
class CreateGraph{Scanner in = new Scanner(System.in);static private Graph graph = new Graph();//创建一个没有顶点的空图static private boolean[] visited;//遍历辅助数组，标记该顶点是否访问过static private boolean flag;//标记是否有Vi到Vj的路径public Vertex getVertex(String str){//根据指定的顶点名称str，返回对应的顶点对象//如果顶点不存在，返回nullfor(int i = 1;i<=graph.verNum;i++){if(graph.vertices[i].vername.equals(str))return  graph.vertices[i];}return  null;}public  int find(Vertex node){//在顶点数组里找到对应的顶点，并返回该顶点在数组中的位置for (int i =1;i<=graph.vertices.length;i++)if (graph.vertices[i].vername.equals(node.vername)==true)return i;return -1;}public void initGraph(){//根据键盘输入的数据，构建具体的图System.out.println("输入顶点的数量");graph.verNum = in.nextInt(); //获得顶点的数量graph.vertices = new Vertex[graph.verNum+1];//动态建立顶点数组，vertices[0]不用visited = new boolean[graph.verNum+1];//动态建立遍历辅助数组System.out.println("输入弧的数量");graph.edgeNum = in.nextInt();//获得弧的数量System.out.println("请输入各个顶点的名称:");for (int i=1;i<=graph.verNum;i++){//从键盘读取各个顶点的名称，构建顶点数组Vertex vertex = new Vertex(); //新建一个顶点类对象vertex.vername = in.next();//获取顶点的名称vertex.nextNode = null;//该顶点指向的下一个顶点（即各顶点之间的弧）设为nullgraph.vertices[i] = vertex;}System.out.println("请依次输入有向图的各条弧的两个顶点的名称：");for (int i=1;i<=graph.edgeNum;i++) {//构建邻接表String v1 = in.next(); //读取的两个顶点的名称String v2 = in.next();Vertex vertex1 = getVertex(v1);//根据两个顶点的名称在顶点数组里找到对应的顶点Vertex vertex2 = getVertex(v2);if (vertex1 == null) { //检查是否输入错误//输入的顶点名称不存在System.out.println(v1 + "不是图中的一个顶点，请重新输入");i--;continue;//} else if (vertex2 == null) {System.out.println(v2 + "不是图中的一个顶点，请重新输入");i--;continue;} else {//输入正确的情况下，//新建顶点，并插入到邻接表中Vertex newVex = new Vertex();//新建一个顶点newVex.vername = vertex2.vername;//把新建的顶点名称设置为弧头顶点的名称//把新顶点插到弧尾顶点之后newVex.nextNode = vertex1.nextNode;vertex1.nextNode = newVex;}}}public void outputGraph(){ //输出图的邻接链表System.out.println("输入的有向图图的邻接链表为：");for(int i=1;i<=graph.verNum;i++){//依次遍历每个顶点Vertex vertex=graph.vertices[i];System.out.print(vertex.vername);//打印当前顶点的名称Vertex current=vertex.nextNode;//读取下一个顶点while(current!=null){ //如果存在下一个顶点System.out.print("-->"+current.vername);current=current.nextNode;}System.out.println();}}public void DFS(int i,int j){//深度搜索int w;for (Vertex current = graph.vertices[i];current!=null;current = current.nextNode){if (flag) //flag = truereturn;w = find(current);//当前顶点在顶点数组中位置if(!visited[w]){//当前顶点没有访问过visited[w]=true;if (w==j)//w==j的时候，代表存在有Vi到Vj的路径flag=true;else  //还没找到DFS(w,j);//尝试从Vw到Vj的路径}}}public void DFSTravel(int i,int j){//深搜辅助函数if (i==j)System.out.println("参数错误，i不能等于j");for (int v=1;v <=graph.verNum;v++)//将visited重置visited[v]=false;visited[i]=true;//i位置已经访问flag = false;//全局变量，标记Vi到Vj之间是否存在路径DFS(i,j);System.out.println("广度搜索：");if (flag)System.out.println(graph.vertices[i].vername+"到"+graph.vertices[j].vername+"之间存在路径");elseSystem.out.println(graph.vertices[i].vername+"到"+graph.vertices[j].vername+"之间不存在路径");}public void BFS(int i,int j){ //广度搜索Queue<Integer> queue = new LinkedList<>();//辅助队列，放置访问过的结点的位置queue.offer(i);//将v放入队列中int w;while (!queue.isEmpty()){i = queue.poll();//出队for (Vertex current = graph.vertices[i];current!=null;current = current.nextNode){w = find(current);if (!visited[w]){visited[w]=true;if (w==j){flag = true;return;}queue.offer(w);}}}}public void BFSTravel(int i,int j){//广度搜索辅助函数if (i==j)System.out.println("参数错误，i不能等于j");for (int v=1;v <=graph.verNum;v++)//将visited重置visited[v]=false;visited[i]=true;//i位置已经访问flag = false;//全局变量，标记Vi到Vj之间是否存在路径System.out.println("广度搜索：");BFS(i,j);if (flag)System.out.println(graph.vertices[i].vername+"到"+graph.vertices[j].vername+"之间存在路径");elseSystem.out.println(graph.vertices[i].vername+"到"+graph.vertices[j].vername+"之间不存在路径");}
}