圖的概念
圖是算法中是樹的拓展，樹是從上向下的數據結構，結點都有一個父結點（根結點除外），從上向下排列。而圖沒有了父子結點的概念，圖中的結點都是平等關係，結果更加複雜。
無向圖有向圖
圖G=(V,E)，其中V代表頂點Vertex，E代表邊edge，一條邊就是一個定點對(u,v)，其中(u,v)∈V。
這兩天遇到一個關於圖的算法，在網上找了很久沒有找到java版的關於數據結構中圖的存儲及其相關操作。於是找了一本java版的數據結構書看了一下，以下是根據書上的講解整理的一個關於無向圖的存儲和對圖的深度優先遍歷。不過這個遍歷只能遍歷連通圖，要想遍歷非連通圖，還需要修改。在這里分享一下代碼希望對有需要的人有幫助。
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);}}/** * 定義圖中的節點類* @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[];//圖中節點數組private int adjMat[][];//節點矩陣private int nVerts;//當前節點數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;}}//添加節點public void addVertex(char lab){vertexList[nVerts++] = new Vertex(lab);}//添加某兩個節點之間的邊public void addEdge(int start,int end){adjMat[start][end] = 1;adjMat[end][start] = 1;}//輸出某個節點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;}//深度優先遍歷（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)//若不存在該節點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操作代碼詳解的全部內容，希望對大家有所幫助。感興趣的朋友可以繼續參閱本站：
Java編程實現基於圖的深度優先搜索和廣度優先搜索完整代碼
深度優先與廣度優先Java實現代碼示例
java編程兩種樹形菜單結構的轉換代碼
如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！