Java图算法之基础

基础：

图结构接触的也是比较多的，基础部分网上到处都是，这里就长话短说，存储图的两种方式，一种是邻接表，一种是邻接矩阵；

举例说明吧，如下图，我们该怎么构建邻接表和邻接矩阵；（抄袭网上的图）

邻接表：

邻接矩阵

基于邻接表的图的构造如下所示：

顶点类：（其实无论是顶点类，边类，还是图类，他们含有的成员变量，成员方法都是不固定，根据需要可以适当的添加，现在我以最基本的要求构造图类）

class Vertex{
//不规范的全局变量（为了容易理解，不把篇幅搞的太长哈）
//顶点名称
	public String name;
//为了构造邻接表
public LinkedList<Vertex> li;
//用于广度遍历和深度遍历
	public boolean status;
	public Vertex(String name){
		this.name = name;
		li = new LinkedList<Vertex>();
		status = false;
	}	
}

边类：

class Edge{
	public Vertex source;
	public Vertex dest;
	public double cost;
	public Edge(Vertex s,Vertex d,double c){
		source = s;
		dest = d;
		cost =c;
	}
}

图类:

public class Graph {
	//为了存储所有的顶点	
HashSet<Vertex> al;
	public Graph(){
		al = new HashSet<Vertex>();
	}
	//每次增加一条边，将两个顶点加入到hashSet中，我们都知道hashSet不支持重复的元素；同时构建邻接表
	public void addEdge(Edge e){
		al.add(e.source);	
		al.add(e.dest);
		Vertex ver;
		e.source.li.add(e.dest);
	}
	
	//设置所有的顶点状态为初始状态；
	public void resetAllVertex(){
		Iterator it = al.iterator();
		while(it.hasNext()){
			((Vertex)it.next()).status =false;
		}
	}
}

对于图，有两种基本的遍历方法，广度遍历和深度遍历；

广度遍历：

顾名思义，如果对图中的A点进行广度遍历，指的就是先遍历跟A有关的所有的节点，然后再依次遍历其它节点；

对A节点的广度遍历的过程是什么样子呢？我们用队列来实现，边看邻接表，边理解；

步骤1,A->B->C （这个过程在队列中存放了B，C节点，到达尽头，那么按照fifo的原则，以B为起始点）

步骤2,B->E （这个过程在队列中存放了E节点，到达尽头，那么按照fifo的原则，以C为起始点）；

步骤3，C->D (因为B节点已经遍历过了，所以跳过，这个过程在队列中存放了D节点，到达尽头，那么按照fifo的原则，以E为起始点)

步骤4，队列中取出E，但找不到未访问点节点，继续从队列中取出D，也没发现，

队列中的元素为空，那么广度遍历到此结束了；

代码如下所示：

//广度遍历；
	public Iterator BFSTraverse(Vertex ver){
		//用来顺序存放遍历的元素
		LinkedList bfsList = new LinkedList();
//全部设置为未访问状态	
		resetAllVertex();
		BFS(ver, bfsList);//从ver点出发广度优先搜索
		return bfsList.iterator();
	}

private void BFS(Vertex ver, LinkedList bfsList) {
		// TODO Auto-generated method stub
		//new一个队列来辅助实现，
	LinkedList<Vertex> tempList = new LinkedList<Vertex>();
		tempList.add(ver);
		//因为只要是队列中的元素，就代表他必然是已经被访问过了
		ver.status = true;
		bfsList.add(ver);
		Vertex tempVer;
		while(tempList.size()>0){
			tempVer = tempList.remove();
			Iterator<Vertex> it = tempVer.li.iterator();
			//对某一个节点访问所有的相关的节点
			while(it.hasNext()){
				Vertex vert = it.next();
				if(!vert.status){
					vert.status = true;
					//只有之前未被访问的节点才有资格进入队列哈
					tempList.add(vert);
					bfsList.add(vert);
				}
			}
		}
	}	
}

深度遍历

：顾名思义，如果对图中的A点进行深度遍历，指的就是从A节点开始沿着某条路径访问到底，如果不能继续的话，那么再退回到倒数第二个访问的点继续访问到底，显然他是后进先出的原则，我们可以借助Stack帮助我们实现这个操作；

对A节点的深度遍历的过程是什么样子呢？我们用队列来实现，边看邻接表，边理解；

步骤1,A->B->E->D （这个过程在堆栈中依次存放了A，B，E，D节点，到达尽头，那么按照Lifo的原则，回退到E点，但是在E点找不到可以访问的点，又回退到B点，在回退到A点）

步骤2,A->C （这个过程在堆栈中存放了C节点,此时堆栈还有A和C两个节点，可能有人会奇怪，为什么A节点仍然存在，因为只有回退到A点且发现没有可以到达的未访问点时才去除A点）；

代码如下：

//深度遍历
	public Iterator DFSTraverse(Vertex sourceVer) {
//顺序存放遍历的数据
		LinkedList<Vertex> tempList = new LinkedList<Vertex>();
		resetAllVertex();
		DFSRecursion(sourceVer,tempList);
		return tempList.iterator();
	}
	
	private void DFSRecursion(Vertex sourceVer, LinkedList list){
		Stack<Vertex> stack = new Stack<Vertex>();
		stack.push(sourceVer);
		list.add(sourceVer);
		sourceVer.status = true;

		boolean flag = false;
		while(stack.size()>0){
//只有当发现vert顶点没有可以直接访问的数才remove
			Vertex vert = stack.peek();
//这个大循环是一个节点访问到底的循环，到尽头 break，从堆栈中取数
			while(true){
//表示从来没有切换过节点
				flag = false;
				Iterator<Vertex> it = vert.li.iterator();
//这个循环是切换节点的，每次找到一个节点就切换到该节点寻找
				while(it.hasNext()){
					Vertex vertemp = it.next();
					if(!vertemp.status){
						vertemp.status = true;	
						stack.push(vertemp);
						list.add(vertemp);
						vert = vertemp;
						flag = true;
						break;
					}
				}
				if(!flag){
					stack.pop();
					break;
				}	
			}	
		}
	}
}

整个图类的总体代码如下所示（包含测试代码）：

public class Graph {
	HashSet<Vertex> al;
	
	public Graph(){
		al = new HashSet<Vertex>();
	}
	
	public void addEdge(Edge e){
		
		al.add(e.source);	
		al.add(e.dest);
		
		Vertex ver;
		e.source.li.add(e.dest);
	}
	
	//设置所有的顶点状态为初始状态；
	public void resetAllVertex(){
		Iterator it = al.iterator();
		while(it.hasNext()){
			((Vertex)it.next()).status =false;
		}
	}
	

	//广度遍历；
	public Iterator BFSTraverse(Vertex ver){
		LinkedList bfsList = new LinkedList();
		resetAllVertex();
		BFS(ver, bfsList);//从v点出发广度优先搜索
		return bfsList.iterator();
	}

	private void BFS(Vertex ver, LinkedList bfsList) {
		// TODO Auto-generated method stub
		//new一个队列来存储完成递归
		LinkedList<Vertex> tempList = new LinkedList<Vertex>();
		tempList.add(ver);
		
		ver.status = true;
		bfsList.add(ver);
		
		Vertex tempVer;
		
		while(tempList.size()>0){
			tempVer = tempList.remove();
			
			Iterator<Vertex> it = tempVer.li.iterator();
			while(it.hasNext()){
				Vertex vert = it.next();
				if(!vert.status){
					vert.status = true;
					tempList.add(vert);
					bfsList.add(vert);
				}
			}
		}
		
	}
	
	//深度遍历
	public Iterator DFSTraverse(Vertex sourceVer) {
		LinkedList<Vertex> tempList = new LinkedList<Vertex>();
		resetAllVertex();
		DFSRecursion(sourceVer,tempList);
		return tempList.iterator();
	}
	
	private void DFSRecursion(Vertex sourceVer, LinkedList list){
		Stack<Vertex> stack = new Stack<Vertex>();
		stack.push(sourceVer);
		list.add(sourceVer);
		sourceVer.status = true;

		boolean flag = false;
		while(stack.size()>0){
			Vertex vert = stack.peek();
			
			while(true){
				flag = false;
				Iterator<Vertex> it = vert.li.iterator();
				while(it.hasNext()){
					Vertex vertemp = it.next();
					if(!vertemp.status){
						vertemp.status = true;	
						stack.push(vertemp);
						list.add(vertemp);
						vert = vertemp;
						flag = true;
						break;
					}
				}
				if(!flag){
					stack.pop();
					break;
				}	
			}	
		}
	}
	
	public static void main(String[] args) {
		Vertex A = new Vertex("A");
		Vertex B = new Vertex("B");
		Vertex C = new Vertex("C");
		Vertex D = new Vertex("D");
		Vertex E = new Vertex("E");
		Edge e1 = new Edge(A,B,0);
		Edge e2 = new Edge(A,C,0);
		Edge e3 = new Edge(B,E,0);
		Edge e4 = new Edge(B,D,0);
		Edge e5 = new Edge(E,B,0);
		Edge e6 = new Edge(D,E,0);
		
		Graph g =new Graph();
		g.addEdge(e1);
		g.addEdge(e2);
		g.addEdge(e3);
		g.addEdge(e4);
		g.addEdge(e5);
		g.addEdge(e6);
		Iterator it = g.BFSTraverse(A);
		while(it.hasNext()){
			System.out.println(((Vertex)it.next()).name);
		}
		Iterator its = g.DFSTraverse(A);
		while(its.hasNext()){
			System.out.println(((Vertex)its.next()).name);
		}
	}
	
	
}

class Vertex{
	public String name;
	public LinkedList<Vertex> li;
	public boolean status;
	
	public Vertex(String name){
		this.name = name;
		li = new LinkedList<Vertex>();
		status = false;
	}	
}

class Edge{
	public Vertex source;
	public Vertex dest;
	public double cost;
	
	public Edge(Vertex s,Vertex d,double c){
		source = s;
		dest = d;
		cost =c;
	}
}

邻接矩阵存储数据的方式：

对于一个N个顶点的图，我们可以定义g[n][n]来存储图；

同时定义status[N]来标记是否被访问过。

于是java代码可以为：（写的相对简单点，没有定义顶点类哈，如果有需要还是需要定义顶点信息的哈）

package algorithm;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Stack;

public class Graph {

	private int[][] g;
	private boolean[] status;

	public Graph(int n) {
		g = new int[n][n];
		status = new boolean[n];
		resetAllVertex();
	}

	public void addEdge(char start, char end) {
		int startInt = start - 'A';
		int endInt = end - 'A';
		g[startInt][endInt] = 1;
	}

	private void resetAllVertex() {
		// TODO Auto-generated method stub

		Arrays.fill(status, false);
	}

	// 广度遍历
	public Iterator BFSTraverse(char start) {
		LinkedList<Character> bfsList = new LinkedList<Character>();
		resetAllVertex();
		BFS(start, bfsList);// 从v点出发广度优先搜索
		return bfsList.iterator();
	}

	private void BFS(char start, LinkedList<Character> bfsList) {
		// TODO Auto-generated method stub
		LinkedList<Integer> liListTemp = new LinkedList<Integer>();
		bfsList.add(start);
		int startInt = start - 'A';
		status[startInt] = true;
		liListTemp.add(startInt);

		while (liListTemp.size() > 0) {
			int verter = liListTemp.remove();
			for (int i = 0; i < g.length; i++) {
				if (g[verter][i] == 1 && !status[i]) {
					liListTemp.add(i);
					status[i] = true;
					bfsList.add((char) (i + 'A'));
				}
			}
		}
	}

	// 深度遍历
	public Iterator DFSTraverse(char start) {
		LinkedList<Character> DFSList = new LinkedList<Character>();
		resetAllVertex();
		DFSRecursion(start, DFSList);
		return DFSList.iterator();
	}

	private void DFSRecursion(char start, LinkedList<Character> dFSList) {
		// TODO Auto-generated method stub
		Stack<Integer> st = new Stack<Integer>();
		dFSList.add(start);
		int startInt = start - 'A';
		status[startInt] = true;
		st.add(startInt);
		boolean flag;
		while (st.size() > 0) {
			int verter = st.peek();
			
			while (true) {
				flag = false;
				for (int i = 0; i < g.length; i++) {
					if (g[verter][i] == 1 && !status[i]) {
						st.add(i);
						status[i] = true;
						dFSList.add((char) (i + 'A'));
						verter = i;
						flag = true;
						break;
					}
				}
				if (!flag) {
					st.pop();
					break;
				}
			}
		}
	}

	public static void main(String[] args) {
		Graph g = new Graph(5);
		g.addEdge('A', 'B');
		g.addEdge('A', 'C');
		g.addEdge('B', 'E');
		g.addEdge('B', 'D');
		g.addEdge('E', 'B');
		g.addEdge('D', 'E');
		Iterator i = g.BFSTraverse('A');
		while (i.hasNext()) {
			System.out.println((char) (i.next()));
		}
		
		Iterator i1 = g.DFSTraverse('A');
		while (i1.hasNext()) {
			System.out.println((char) (i1.next()));
		}
	}

}

图的单源无权最短路径：

利用广度优先搜索，从源出发，分别给可以直达的点赋值1，然后依次从队列中取出值，依次给可以直达的点赋值，依此类推：

//无权最短路径问题代码如下（很简单，懒得写了，抄网上的）

void unweighted( Vertex s ){
			//一个队列
			Queue<Vertex> q = new Queue<Vertex>( );
			//每个顶点初始距离为INFINITY
			for each Vertex v
				v.dist = INFINITY;
			//s初始距离为0		
			s.dist = 0;
			q.enqueue( s );
			
			while( !q.isEmpty( ) ){
				Vertex v = q.dequeue( );
				//遍历v的邻接顶点
				for each Vertex w adjacent to v
					//如果dist是INFINITY说明没有处理过
					if( w.dist == INFINITY ){
						w.dist = v.dist + 1;
						w.path = v;
						q.enqueue( w );
					}
			}
		}

原文链接：https://blog.csdn.net/haizi8888/article/details/22828735

你可能也喜欢