package edu.xidian.graph; class MyStack { private final int SIZE = 20; private int[] st; private int top; public MyStack() { st = new int[SIZE]; top = -1; } public void push(int j) { st[++top] = j; } public int pop() { return st[top--]; } public int peek() { return st[top]; } public boolean isEmpty() { return (top == -1); } } class Vertex { public char label; public boolean wasVisited; public Vertex(char lab) { label = lab; wasVisited = false; } } public class Graph { private final int MAX_VERTS = 20; private Vertex vertexList[]; private int adjMat[][]; private int nVerts; private MyStack theStack; public Graph() { vertexList = new Vertex[MAX_VERTS]; adjMat = new int[MAX_VERTS][MAX_VERTS]; nVerts = 0; theStack = new MyStack(); } public void addVertex(char label) { vertexList[nVerts++] = new Vertex(label); } 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 void dfs() { vertexList[0].wasVisited = true; displayVertex(0); theStack.push(0); while (!theStack.isEmpty()) { int v = getAdjUnvisitedVertex(theStack.peek()); 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 int getAdjUnvisitedVertex(int v) { for (int j = 0; j < nVerts; j++) { if (adjMat[v][j] == 1 && vertexList[j].wasVisited == false) { return j; } } return -1; } public static void main(String[] args) { Graph theGraph = new Graph(); theGraph.addVertex('A'); // 0 (start for dfs) theGraph.addVertex('B'); // 1 theGraph.addVertex('C'); // 2 theGraph.addVertex('D'); // 3 theGraph.addVertex('E'); // 4 theGraph.addEdge(0, 1); // AB theGraph.addEdge(1, 2); // BC theGraph.addEdge(0, 3); // AD theGraph.addEdge(3, 4); // DE System.out.print("Visits: "); theGraph.dfs(); System.out.println(); } }
相关推荐
CREATE GRAPH WITH NEW TECHNOLOGY OF DRAWING
简易链表linux下实现单向链表的C语言实现程序,有详尽的链表操作函数,可以作为C语言学习的参考代码
C++实现图的邻接表、邻接矩阵存储方式并输出深度优先遍历和广度优先遍历并输出栈、队列中的变化情况 打印输出队列、栈中入队出队,入栈出栈的情况,可直接运行无编译错误
graph traversal using bfs and dfs strategy
Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root (selecting some node as the root in the graph case) and explores as far as...
图论编程,包含文件操作,建立图的邻接表,并实现深度优先搜索
Graph图DFS深度优先搜索题型套路【LeetCode刷题套路教程12】
超简洁的python版本 graph入门教程代码,step-by-step, 代码直接运行,小白专属 1.图表示 2.图可视化 3. 图BFS 4.图DFS 5.图拓扑排序 6.图全部路径 7.带节点属性的图 8.图配置文件 9.子图切分
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑...
资源来自pypi官网。 资源全名:graph-dfs-0.0.7.tar.gz
深度优先遍历,宽度优先遍历. 程序从图文本中读取图的矩阵。 矩阵包括有向图或无向图
学习的大部分基础数据结构和相关的算法 实现语言主要是C/C++ BST: 二分搜索树 BubbleSort: 冒泡排序 CircleLinkList: 循环链表 Expression: 表达式求值 Fibonacci: 斐波那契数列 ...graph_dfs: 图的深度遍历
邻接表存储图,然后进行深度优先遍历及广度优先遍历。
图Graph,_深度优先遍历(DFS),_广度优先遍历(BFS)【数据结构和算法入门9】
玩具图数据库 只是一个玩具图数据库,以便我们可以使用图算法 目的 我想以此测试的用例 使用DAG货币转换来查找如何通过进行快速货币转换来赚钱。又名给定货币转换网格,在少数货币之间找到了欧拉回路,该回路必须比...
如果我们只想检查测试是否正确执行,则可以在构建文件中输入ctest (在编译程序后可以运行)croup 5顶点的拓扑排序算法描述该算法适用于改进的DFS算法,该算法的编写方式使其能够记忆并返回到先前访问的顶点,当它...
//create new DFS graph var dfs = new DFS ( ) ; // or optionally pass map of edges var dfs = new DFS ( [ 'A' , 'B' ] ) ; //TODO //add edges to the graph dfs . addEdge ( from , to ) ; //return all paths...
boost_graph试图用Python包装C ++ Boost Graph库,提供了诸如广度优先搜索,DFS,最短路径,拓扑排序之类的图算法。 该项目已死(http://bayleshanks.com/pamv1)
graph是一个二维数组,其中graph[i][j]表示顶点i和j之间是否存在边。 深度优先搜索使用递归来实现。我们从指定的起始顶点开始,并将其标记为已访问。然后,对于起始顶点的每个邻居顶点,如果它尚未被访问过,则调用...
此类Graph无需删除即可实现简化的Graph ADT。可用于编写深度优先搜索(DFT)和广度优先搜索(BFT)的练习 节点(顶点)列表必须在构造函数中传递,但是可以在以后添加边。 仅用于教育目的! :) 用法 创建一个实例 ...