欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

java編程無向圖結構的存儲及DFS操作代碼詳解

 更新時間:2017年12月08日 10:20:59   作者:Sober_123  
這篇文章主要介紹了java編程無向圖結構的存儲及DFS操作代碼詳解,具有一定借鑒價值,需要的朋友可以了解下。

圖的概念

圖是算法中是樹的拓展,樹是從上向下的數據結構,結點都有一個父結點(根結點除外),從上向下排列。而圖沒有了父子結點的概念,圖中的結點都是平等關系,結果更加復雜。

無向圖                                                       有向圖

圖G=(V,E),其中V代表頂點Vertex,E代表邊edge,一條邊就是一個定點對(u,v),其中(u,v)∈V。

這兩天遇到一個關于圖的算法,在網上找了很久沒有找到java版的關于數據結構中圖的存儲及其相關操作。于是找了一本java版的數據結構書看了一下,以下是根據書上的講解整理的一個關于無向圖的存儲和對圖的深度優(yōu)先遍歷。不過這個遍歷只能遍歷連通圖,要想遍歷非連通圖,還需要修改。在這里分享一下代碼希望對有需要的人有幫助。

package com.homework;
/** 
 * 定義棧類 
 */
class StackX{
	private final int size = 20;
	private int[] st;
	private int top;
	//初始化棧 
	public StackX(){
		st = new int[size];
		top = -1;
	}
	//進棧 
	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é)點類 
 * @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é)點數組 
	private int adjMat[][];
	//節(jié)點矩陣 
	private int nVerts;
	//當前節(jié)點數 
	private StackX theStack;
	//定義一個棧 
	//初始化圖的結構 
	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é)點 
	public void addVertex(char lab){
		vertexList[nVerts++] = new Vertex(lab);
	}
	//添加某兩個節(jié)點之間的邊 
	public void addEdge(int start,int end){
		adjMat[start][end] = 1;
		adjMat[end][start] = 1;
	}
	//輸出某個節(jié)點 
	public void displayVertex(int v){
		System.out.print(vertexList[v].label);
	}
	//獲取未被訪問的幾點 
	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é)點 
			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();
		}
	}
}

程序運行的結果:

The order visited:ABCED

總結

以上就是本文關于java編程無向圖結構的存儲及DFS操作代碼詳解的全部內容,希望對大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站:

Java編程實現基于圖的深度優(yōu)先搜索和廣度優(yōu)先搜索完整代碼

深度優(yōu)先與廣度優(yōu)先Java實現代碼示例

java編程兩種樹形菜單結構的轉換代碼

如有不足之處,歡迎留言指出。感謝朋友們對本站的支持!

相關文章

  • java組件commons-fileupload文件上傳示例

    java組件commons-fileupload文件上傳示例

    這篇文章主要為大家詳細介紹了java組件commons-fileupload實現文件上傳,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2016-10-10
  • Java并發(fā)源碼分析ConcurrentHashMap線程集合

    Java并發(fā)源碼分析ConcurrentHashMap線程集合

    這篇文章主要為大家介紹了Java并發(fā)源碼分析ConcurrentHashMap線程集合,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪
    2023-02-02
  • Java?Web應用小案例之實現用戶登錄功能全過程

    Java?Web應用小案例之實現用戶登錄功能全過程

    在Java開發(fā)過程中實現用戶的注冊功能是最基本的,這篇文章主要給大家介紹了關于Java?Web應用小案例之實現用戶登錄功能的相關資料,文中通過圖文介紹的非常詳細,需要的朋友可以參考下
    2024-01-01
  • java關于持久層面試題目整理

    java關于持久層面試題目整理

    在本篇文章里小編給大家分享的是一篇關于java關于持久層面試題目整理內容,需要的朋友們可以學習下。
    2020-03-03
  • 解決springboot整合druid遇到的坑

    解決springboot整合druid遇到的坑

    這篇文章主要介紹了解決springboot整合druid遇到的坑,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2021-08-08
  • 詳解Java使用JMH進行基準性能測試

    詳解Java使用JMH進行基準性能測試

    本文主要介紹了Java使用JMH進行基準性能測試,文中通過示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2021-11-11
  • Spring框架對于Bean的管理詳解

    Spring框架對于Bean的管理詳解

    在實際開發(fā)中,我們往往要用到Spring容器為我們提供的諸多資源,例如想要獲取到容器中的配置、獲取到容器中的Bean等等。本文為大家詳細講講工具類如何獲取到Spring容器中的Bean,需要的可以參考一下
    2022-07-07
  • Java中零拷貝和深拷貝的原理及實現探究(代碼示例)

    Java中零拷貝和深拷貝的原理及實現探究(代碼示例)

    深拷貝和零拷貝是兩個在 Java 中廣泛使用的概念,它們分別用于對象復制和數據傳輸優(yōu)化,下面將詳細介紹這兩個概念的原理,并給出相應的 Java 代碼示例,感興趣的朋友一起看看吧
    2023-12-12
  • 詳解堆排序算法原理及Java版的代碼實現

    詳解堆排序算法原理及Java版的代碼實現

    如果將堆理解為二叉樹,那么樹中任一非葉結點的關鍵字均不大于(或不小于)其左右孩子(若存在)結點的關鍵字,堆排序的時間復雜度為O(N*logN),這里我們就來詳解堆排序算法原理及Java版的代碼實現
    2016-06-06
  • Spring Boot讀取配置屬性常用方法解析

    Spring Boot讀取配置屬性常用方法解析

    這篇文章主要介紹了Spring Boot讀取配置屬性常用方法解析,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
    2020-09-09

最新評論