java編程無(wú)向圖結(jié)構(gòu)的存儲(chǔ)及DFS操作代碼詳解
圖的概念
圖是算法中是樹(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é)果:
The order visited:ABCED
總結(jié)
以上就是本文關(guān)于java編程無(wú)向圖結(jié)構(gòu)的存儲(chǔ)及DFS操作代碼詳解的全部?jī)?nèi)容,希望對(duì)大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站:
Java編程實(shí)現(xiàn)基于圖的深度優(yōu)先搜索和廣度優(yōu)先搜索完整代碼
深度優(yōu)先與廣度優(yōu)先Java實(shí)現(xiàn)代碼示例
java編程兩種樹(shù)形菜單結(jié)構(gòu)的轉(zhuǎn)換代碼
如有不足之處,歡迎留言指出。感謝朋友們對(duì)本站的支持!
相關(guān)文章
java組件commons-fileupload文件上傳示例
這篇文章主要為大家詳細(xì)介紹了java組件commons-fileupload實(shí)現(xiàn)文件上傳,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2016-10-10Java并發(fā)源碼分析ConcurrentHashMap線程集合
這篇文章主要為大家介紹了Java并發(fā)源碼分析ConcurrentHashMap線程集合,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-02-02Java?Web應(yīng)用小案例之實(shí)現(xiàn)用戶登錄功能全過(guò)程
在Java開(kāi)發(fā)過(guò)程中實(shí)現(xiàn)用戶的注冊(cè)功能是最基本的,這篇文章主要給大家介紹了關(guān)于Java?Web應(yīng)用小案例之實(shí)現(xiàn)用戶登錄功能的相關(guān)資料,文中通過(guò)圖文介紹的非常詳細(xì),需要的朋友可以參考下2024-01-01詳解Java使用JMH進(jìn)行基準(zhǔn)性能測(cè)試
本文主要介紹了Java使用JMH進(jìn)行基準(zhǔn)性能測(cè)試,文中通過(guò)示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-11-11Java中零拷貝和深拷貝的原理及實(shí)現(xiàn)探究(代碼示例)
深拷貝和零拷貝是兩個(gè)在 Java 中廣泛使用的概念,它們分別用于對(duì)象復(fù)制和數(shù)據(jù)傳輸優(yōu)化,下面將詳細(xì)介紹這兩個(gè)概念的原理,并給出相應(yīng)的 Java 代碼示例,感興趣的朋友一起看看吧2023-12-12詳解堆排序算法原理及Java版的代碼實(shí)現(xiàn)
如果將堆理解為二叉樹(shù),那么樹(shù)中任一非葉結(jié)點(diǎn)的關(guān)鍵字均不大于(或不小于)其左右孩子(若存在)結(jié)點(diǎn)的關(guān)鍵字,堆排序的時(shí)間復(fù)雜度為O(N*logN),這里我們就來(lái)詳解堆排序算法原理及Java版的代碼實(shí)現(xiàn)2016-06-06