Java实现邻接表的DFS和BFS

- 日理万妓 2022-04-13 14:12 170阅读 0赞

**顶点类**

public class Vertex {
    	String verName;
    	boolean visited;
    	Vertex nextVertex;
    }

**图类**

public class Graph extends Constent {
    	Vertex[] verList = new Vertex[MAX_VERTEX];
    	int VerNum;
    	int EdgeNum;
    }

**常量类**

public class Constent {
    	protected final int MAX_VERTEX = 100;
    }

**创建图和遍历**

import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Scanner;
    
    public class CreatGraph extends Graph{
    	
    	/**
    	 * 根据顶点名称返回图中顶点
    	 * @param g 需要寻找顶点的图
    	 * @param verName 寻找图中顶点的名称
    	 * @return	返回图中的顶点或者空(该顶点不存在图中)
    	 */
    	Vertex getVertex(Graph g,String verName) {
    		Vertex ver = new Vertex();
    		ver.verName = verName;
    		for(int i = 0;i<g.VerNum;i++) {
    			if(ver.verName.equals(g.verList[i].verName)) {
    				ver = g.verList[i];
    				return ver;					
    			}
    		}	
    		return null;
    	}
    	/**
    	 * 根据顶点下标返回图中顶点
    	 * @param g 需要查找的图
    	 * @param i 需要索引的位置
    	 * @return 返回图中第i个顶点
    	 */
    	Vertex IndexVertex(Graph g,int i) {	
    		return g.verList[i];	
    	}
    	/**
    	 * 初始化图
    	 * @param g 需要初始化的图
    	 */
    	void InitGraph(Graph g) {
    		System.out.println("输入顶点数和边数：");
    		int VerNum,EdgeNum;
    		Scanner sc = new Scanner(System.in);
    		VerNum = sc.nextInt();
    		EdgeNum = sc.nextInt();
    		g.VerNum = VerNum;
    		g.EdgeNum = EdgeNum;
    		System.out.println("依次输入顶点名称：");
    		//先将各顶点存入
    		for(int i = 0;i<VerNum;i++) {
    			Vertex v = new Vertex();
    			v.verName = sc.next();
    			v.nextVertex = null;
    			v.visited = false;
    			g.verList[i] = v;
    		}
    		System.out.println("输入图的各条边(eg:v0 v1)：");
    		//将图的边存入
    		for(int i = 0;i<EdgeNum;i++) {
    			String preVer = sc.next();
    			String lasVer = sc.next();
    			Vertex v = getVertex(g,preVer);
    			if(v==null) {
    				System.out.println("This Vertex is not in the Graph");
    			}
    			else {
    				Vertex v2 = new Vertex();
    					v2.verName = lasVer;
    					v2.nextVertex = v.nextVertex;
    					v.nextVertex = v2;			//keep v2 follow the v
    			}
    		}
    		sc.close();
    	}
    	/**
    	 * 以领接表的方式输出该图
    	 * @param g 需要输出的图
    	 */
    	void OutputGraph(Graph g) {
    		System.out.println("The output Adj list is:");
    		for(int i = 0;i<g.VerNum;i++) {
    			Vertex v1 = g.verList[i];
    			System.out.print(v1.verName);
    			while(v1.nextVertex!=null) {
    				Vertex temp = v1.nextVertex;
    				System.out.print("->"+temp.verName);
    				v1 = temp;
    			}
    			System.out.println();
    		}
    	}
    	/**
    	 * 根据DFS遍历输出图
    	 * @param g 需要遍历的图
    	 */
    	void TraverseGraph(Graph g) {
    		System.out.println("DFS output is:");
    		for(int i = 0;i < g.VerNum;i++) {
    			if(g.verList[i].visited == false)
    				DFS(g,g.verList[i]);
    		}
    	}
    	
    	void DFS(Graph gra,Vertex v) {
    		Graph g= new Graph();
    		g = gra;
    		if(v.visited == false) {
    			visit(v);
    			System.out.print("->" );
    			biaoji(g,v);			
    		}
    		Vertex p = v.nextVertex;
    		while(p!=null) {
    			Vertex verNow = getVertex(g,p.verName);
    			if(verNow.visited == false)
    				DFS(g,verNow);
    			p = p.nextVertex;
    		}
    	}
    	/**
    	 * 访问某个顶点
    	 * @param v 被访问的顶点
    	 */
    	void visit(Vertex v) {
    		if(v!=null)
    			System.out.print( v.verName);
    	}
    	/**
    	 * 将图中的某个顶点全部标记为已访问
    	 * @param g 该图
    	 * @param ver 该顶点
    	 */
    	void biaoji(Graph g,Vertex ver) {
    		for(int i = 0;i<g.VerNum;i++) {
    			for(Vertex v = g.verList[i];v!=null;v = v.nextVertex) {
    				if(v.verName.equals(ver.verName))
    					v.visited = true;
    			}
    		}
    	}
    	/**
    	 * BFS访问图并输出
    	 * @param g 需要访问的图
    	 */
    	void BFS(Graph g) {
    		//初始化图
    		for(int i = 0;i<g.VerNum;i++) {
    			for(Vertex v = g.verList[i];v!=null;v = v.nextVertex) {
    					v.visited = false;
    			}
    		}
    		System.out.println("The Graph of BFS is:");
    		visit(g.verList[0]);
    		biaoji(g,g.verList[0]);
    		Queue<Vertex> Q = new LinkedList<Vertex>();
    		Q.add(g.verList[0]);
    		while(!Q.isEmpty()) {
    			Vertex ver = Q.poll(); //队首元素出列
    			Vertex current = ver.nextVertex;
    				while(current!=null) {
    					if(current.visited == false) {
    						System.out.print("->" );
    						visit(current);
    						biaoji(g,current);
    						Vertex newVer = getVertex(g,current.verName);
    						Q.add(newVer);
    						current = current.nextVertex;//访问其他邻接点
    					}
    					else if(current.nextVertex == null)
    						break;
    					
    				}
    		}			 
    		System.out.println();
    }
    	
    	public static void main(String[] args) {
    		Graph g = new Graph();
    		CreatGraph cg = new CreatGraph();
    		cg.InitGraph(g);
    		cg.OutputGraph(g);
    		cg.TraverseGraph(g);
    		cg.BFS(g);
    		return;
    	}
    	/*
    	 * output：
    	 输入顶点数和边数：
    	9 10
    	依次输入顶点名称：
    	A B C D E F G H I
    	输入图的各条边(eg:v0 v1)：
    	A B
    	A E
    	A D
    	B D
    	B C
    	C F
    	E G
    	D G
    	G H
    	H I
    	The output Adj list is:
    	A->D->E->B
    	B->C->D
    	C->F
    	D->G
    	E->G
    	F
    	G->H
    	H->I
    	I
    	DFS output is:
    	A->D->G->H->I->E->B->C->F->
    	The Graph of BFS is:
    	A->D->E->B->G->C->H->F->I
    	 */
    }