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)先搜索完整代碼
如有不足之處,歡迎留言指出。感謝朋友們對本站的支持!
相關文章
java組件commons-fileupload文件上傳示例
這篇文章主要為大家詳細介紹了java組件commons-fileupload實現文件上傳,具有一定的參考價值,感興趣的小伙伴們可以參考一下2016-10-10Java并發(fā)源碼分析ConcurrentHashMap線程集合
這篇文章主要為大家介紹了Java并發(fā)源碼分析ConcurrentHashMap線程集合,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-02-02