时间:2021-05-19
图的概念
图是算法中是树的拓展,树是从上向下的数据结构,结点都有一个父结点(根结点除外),从上向下排列。而图没有了父子结点的概念,图中的结点都是平等关系,结果更加复杂。
无向图 有向图
图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(); } }}程序运行的结果:
总结
以上就是本文关于java编程无向图结构的存储及DFS操作代码详解的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站:
Java编程实现基于图的深度优先搜索和广度优先搜索完整代码
深度优先与广度优先Java实现代码示例
java编程两种树形菜单结构的转换代码
如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
C语言数据结构之图的遍历实例详解输入一组顶点,建立无向图的邻接矩阵。输入一组顶点,建立有向图的邻接表。分别对无向图和有向图进行DFS(深度优先遍历)和BFS(广
本文实例为大家分享了C语言求解无向图顶点之间的所有最短路径的具体代码,供大家参考,具体内容如下思路一:DFS,遇到终点之后进行记录辅助存储:std::vecto
java数据结构中栈和队列的实例详解栈和队列是两种重要的线性数据结构,都是在一个特定的范围的存储单元中的存储数据。与线性表相比,它们的插入和删除操作收到更多的约
Servlet中操作文件详解及实例因为Servlet本来就是一个.Java文件,因此servlet中操作文件和普通java文件操作文件是一样的。读取文件主要代码
Python调用Java实例详解前言:Python对服务器端编程不如Java所以这方面可能要调用Java代码前提:Linux环境1安装jpype1安装后测试代码