快捷導(dǎo)航

java編程無(wú)向圖結(jié)構(gòu)的存儲(chǔ)及DFS操作代碼詳解

更新時(shí)間：2017年12月08日 10:20:59 作者：Sober_123

這篇文章主要介紹了java編程無(wú)向圖結(jié)構(gòu)的存儲(chǔ)及DFS操作代碼詳解，具有一定借鑒價(jià)值，需要的朋友可以了解下。

圖的概念

圖是算法中是樹(shù)的拓展，樹(shù)是從上向下的數(shù)據(jù)結(jié)構(gòu)，結(jié)點(diǎn)都有一個(gè)父結(jié)點(diǎn)（根結(jié)點(diǎn)除外），從上向下排列。而圖沒(méi)有了父子結(jié)點(diǎn)的概念，圖中的結(jié)點(diǎn)都是平等關(guān)系，結(jié)果更加復(fù)雜。

無(wú)向圖有向圖

圖G=(V,E)，其中V代表頂點(diǎn)Vertex，E代表邊edge，一條邊就是一個(gè)定點(diǎn)對(duì)(u,v)，其中(u,v)∈V。

這兩天遇到一個(gè)關(guān)于圖的算法，在網(wǎng)上找了很久沒(méi)有找到j(luò)ava版的關(guān)于數(shù)據(jù)結(jié)構(gòu)中圖的存儲(chǔ)及其相關(guān)操作。于是找了一本java版的數(shù)據(jù)結(jié)構(gòu)書(shū)看了一下，以下是根據(jù)書(shū)上的講解整理的一個(gè)關(guān)于無(wú)向圖的存儲(chǔ)和對(duì)圖的深度優(yōu)先遍歷。不過(guò)這個(gè)遍歷只能遍歷連通圖，要想遍歷非連通圖，還需要修改。在這里分享一下代碼希望對(duì)有需要的人有幫助。

package com.homework;
/** 
 * 定義棧類 
 */
class StackX{
	private final int size = 20;
	private int[] st;
	private int top;
	//初始化棧 
	public StackX(){
		st = new int[size];
		top = -1;
	}
	//進(jìn)棧 
	public void push(int j){
		st[++top] = j;
	}
	//出棧 
	public int pop(){
		return st[top--];
	}
	//返回棧頂元素 
	public int peak(){
		return st[top];
	}
	//判斷棧是否為空 
	public Boolean isEmpty(){
		return (top==-1);
	}
}
/** 
 * 定義圖中的節(jié)點(diǎn)類 
 * @author Administrator 
 * 
 */
class Vertex{
	public char label;
	public Boolean wasVisited;
	public Vertex(char lab){
		label = lab;
		wasVisited = false;
	}
}
/** 
 * 定義圖類 
 * @author Administrator 
 * 
 */
class Graph{
	private final int num = 20;
	private Vertex vertexList[];
	//圖中節(jié)點(diǎn)數(shù)組 
	private int adjMat[][];
	//節(jié)點(diǎn)矩陣 
	private int nVerts;
	//當(dāng)前節(jié)點(diǎn)數(shù) 
	private StackX theStack;
	//定義一個(gè)棧 
	//初始化圖的結(jié)構(gòu) 
	public Graph(){
		vertexList = new Vertex[num];
		adjMat = new int[num][num];
		nVerts = 0;
		for (int i=0; i<num; i++){
			for (int j=0; j<num; j++) 
			        adjMat[i][j] = 0;
		}
	}
	//添加節(jié)點(diǎn) 
	public void addVertex(char lab){
		vertexList[nVerts++] = new Vertex(lab);
	}
	//添加某兩個(gè)節(jié)點(diǎn)之間的邊 
	public void addEdge(int start,int end){
		adjMat[start][end] = 1;
		adjMat[end][start] = 1;
	}
	//輸出某個(gè)節(jié)點(diǎn) 
	public void displayVertex(int v){
		System.out.print(vertexList[v].label);
	}
	//獲取未被訪問(wèn)的幾點(diǎn) 
	public int getAdjUnvisitedVertex(int v){
		for (int j=0; j<nVerts; j++){
			if(adjMat[v][j]==1 && vertexList[j].wasVisited==false) 
			        return j;
		}
		return -1;
	}
	//深度優(yōu)先遍歷（DFS） 
	public void dfs(){
		vertexList[0].wasVisited=true;
		displayVertex(0);
		theStack= new StackX();
		theStack.push(0);
		while(!theStack.isEmpty()){
			int v = getAdjUnvisitedVertex(theStack.peak());
			if(v==-1)//若不存在該節(jié)點(diǎn) 
			theStack.pop(); else 
			      {
				vertexList[v].wasVisited = true;
				displayVertex(v);
				theStack.push(v);
			}
		}
		for (int j=0; j<nVerts; j++) 
		      vertexList[j].wasVisited = false;
	}
}
public class GraphConnect {
	public static void main(String[] args){
		{
			Graph theGraph = new Graph();
			theGraph.addVertex('A');
			theGraph.addVertex('B');
			theGraph.addVertex('C');
			theGraph.addVertex('D');
			theGraph.addVertex('E');
			theGraph.addEdge(0, 1);
			//AB 
			theGraph.addEdge(1, 2);
			//BC 
			theGraph.addEdge(0, 3);
			//AD 
			theGraph.addEdge(3, 4);
			//DE 
			theGraph.addEdge(2, 4);
			//CE 
			System.out.print("The order visited:");
			theGraph.dfs();
			System.out.println();
		}
	}
}

程序運(yùn)行的結(jié)果：