【数据结构】判别以邻接表方式存储的有向图是否存在顶点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,返回对应的顶点对象
//如果顶点不存在,返回null
for(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;//该顶点指向的下一个顶点(即各顶点之间的弧)设为null
graph.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 = true
return;
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+"之间存在路径");
else
System.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+"之间存在路径");
else
System.out.println(graph.vertices[i].vername+"到"+graph.vertices[j].vername+"之间不存在路径");
}
}