说几句题外话,我的书架总摆着几本自己认为不错的java的基础书籍,一是<<Thinking in java>>,另外两本是第二版的<<Data Structures & Algorithms in Java>>和一本国人写的<<Java面向对象程序设计教程>>.
没有什么事做的时候,自己总是会拿起这几本翻一翻,免得有一些基础的东西忘记了。
下边的例子就是<<Data Structures & Algorithms in Java>>书的一个例子,并非我所写的,这一本书我觉得是最好
的一本java数据结构的入门书籍.现在把这一个例子记录在blog上,当作温习一下啦。
进入正题,深度优等搜索有三个规则:
1、如果可能,访问一个邻接的未访问的顶点,标记它,并把放入栈中。
2、当不能执行规则1时,如果栈不空,就从栈中弹出一个顶点。
3、如果不能执行规则1和规则2,就完成了整个搜索的过程。
class StackX
{
private final int SIZE = 20;
private int[] st;
private int top;
public StackX() // constructor
{
st = new int[SIZE]; // make array
top = -1;
}
public void push(int j) // put item on stack
{ st[++top] = j; }
public int pop() // take item off stack
{ return st[top--]; }
public int peek() // peek at top of stack
{ return st[top]; }
public boolean isEmpty() // true if nothing on stack
{ return (top == -1); }
} // end class StackX
class Vertex
{
public char label; // label (e.g. 'A')
public boolean wasVisited;
public Vertex(char lab) // constructor
{
label = lab;
wasVisited = false;
}
} // end class Vertex
class Graph
{
private final int MAX_VERTS = 20;
private Vertex vertexList[]; // list of vertices
private int adjMat[][]; // adjacency matrix
private int nVerts; // current number of vertices
private StackX theStack;
public Graph() // constructor
{
vertexList = new Vertex[MAX_VERTS];
// adjacency matrix
adjMat = new int[MAX_VERTS][MAX_VERTS];
nVerts = 0;
for(int y=0; y<MAX_VERTS; y++) // set adjacency
for(int x=0; x<MAX_VERTS; x++) // matrix to 0
adjMat[x][y] = 0;
theStack = new StackX();
} // end constructor
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 void dfs() // depth-first search
{ // begin at vertex 0
vertexList[0].wasVisited = true; // mark it
displayVertex(0); // display it
theStack.push(0); // push it
while( !theStack.isEmpty() ) // until stack empty,
{
// get an unvisited vertex adjacent to stack top
int v = getAdjUnvisitedVertex( theStack.peek() );
if(v == -1) // if no such vertex,
theStack.pop();
else // if it exists,
{
vertexList[v].wasVisited = true; // mark it
displayVertex(v); // display it
theStack.push(v); // push it
}
} // end while
// stack is empty, so we're done
for(int j=0; j<nVerts; j++) // reset flags
vertexList[j].wasVisited = false;
} // end dfs
// returns an unvisited vertex adj to v
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;
} // end getAdjUnvisitedVertex()
} // end class Graph
class DFSApp
{
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(); // depth-first search
System.out.println();
} // end main()
} // end class DFSApp
输入结果:
Visits:ABCDE
分享到:
相关推荐
通过本文的介绍,读者应该能够理解无向图的深度优先遍历算法,并能根据所提供的示例代码实现自己的无向图深度优先遍历程序。这种遍历方式对于解决图理论中的许多问题非常有用,例如最短路径问题、拓扑排序等。
对于无向图,矩阵是对称的,因为边i到j和j到i是等价的。对于有向图,矩阵可能不对称。 在Java中,我们可以创建一个二维整数数组来表示邻接矩阵。例如,对于一个包含n个节点的图,我们可以定义一个n×n的数组。下面...
深度优先搜索(DFS,Depth-First Search)是一种用于遍历或搜索树或图的算法,其基本思想是从起点开始,尽可能深地探索图的分支,直到达到目标节点或遍历完所有可达节点。在环路检测的问题中,DFS能够有效地找到图中...
对于无向图,邻接矩阵是对称的;而对于有向图,可能不对称。 2. **邻接表**:邻接表是一种更节省空间的表示方法,尤其在处理稀疏图时。它为每个节点维护一个列表,列表中的元素是与其相连的所有节点。邻接表不存储...
例如,对于一个无向图,我们可以通过以下方式定义一个节点类Node,然后用邻接表来表示图: ```python class Node: def __init__(self, value): self.value = value self.neighbors = [] def dfs(node, visited=...
DFS在有向图和无向图中都能使用,但不保证找到最短路径。在某些问题,如判断图是否连通、查找有向图中的环等,DFS是非常有效的。 在提供的文件列表中,我们可以看到`Graph.cpp`, `Node.cpp`, `Path.cpp`, 和 `Main....
- **有向图与无向图**:如果图中的每条边都具有明确的方向,则该图称为有向图;反之,若图中边无方向,则称为无向图。 - **简单图与多重图**:简单图要求任意两条边的起点和终点不能完全相同,并且每条边必须连接...
给定的代码实现了一个简单的无向图,并使用递归的方式实现了深度优先遍历算法。下面对代码的主要部分进行解析: 1. **定义基本数据类型**: - `VertexType` 代表顶点的类型,在这里被定义为 `char`。 - `EdgeType...
邻接矩阵适用于表示有向或无向图,其中每个节点都有一个与之关联的数组,数组中的元素指示是否存在边,如果是有向图,则还记录边的方向。邻接表则更适合稀疏图,它以链表或集合的形式存储每个节点的邻居。 DFS的...
无向图的课设,有程序和报告,内容有邻接矩阵建立无向图、邻接矩阵遍历、广度优先搜索遍历、深度优先搜索遍历、(最小生成树普里姆(Prim)算法)、单源最短路径(地杰斯特拉(Dijkstra)算法),程序打开即可运行。
**深度优先搜索**(Depth First Search, DFS)是一种用于遍历或搜索树或图的算法。此算法按照尽可能深的路径探索尽可能远的节点,直到遇到目标或无法再深入为止。在本课程中,我们将深入了解深度优先搜索的基本原理...
- 图可以分为有向图(Directed Graph)和无向图(Undirected Graph)。有向图的边具有方向,而无向图的边没有方向。 2. **深度优先搜索(DFS, Depth-First Search)** - 深度优先搜索是一种用于遍历或搜索树或图的...
深度优先搜索通常用于无环图或确保不会形成环的有向图中,以避免无限循环。在寻找最短路径时,DFS可以结合回溯策略,即当发现当前路径不可能是最短路径时,回溯到前一个节点并尝试其他分支。这种方法适用于某些特定...
3. **拓扑排序**:在无环有向图(DAG)中,DFS可以进行拓扑排序,将所有节点按照无后继关系排列。 4. **强连通分量**:判断图中是否存在强连通分量,即每个节点都能到达其他所有节点。 5. **环检测**:DFS配合标志位...
对于无向图,这种关系是对称的。 在给定的代码中,`GRAPH`结构体定义了一个图,包括顶点数组`vex`,邻接矩阵`edge`,以及当前顶点数`n`和边数`e`。`Create`函数用于创建图,通过用户输入的顶点数和边数,然后逐个...
一个整型变量`kind`用于表示图的类型(如无向图、有向图等);以及一个`symbol[maxnum]`数组,用于标记节点是否已被访问过。 4. **Graph类的方法**: - `Graph()`构造函数:初始化图的成员变量。 - `Create()`...
常见的算法包括深度优先搜索(DFS)和Kahn的算法。 5. **广度优先搜索(Breadth-First Search, BFS)**:BFS是一种从起点开始遍历图的算法,按照层次顺序访问节点。在DAG中,它可以用于找到从起点到所有其他节点的...
**标题解析:** “TSP.zip_TSP 回路_TSP回溯_tsp问题无向图_tsp...通过上述分析,我们可以推断,提供的资源很可能是关于如何使用回溯法在无向图中解决旅行商问题的实例或教程,可能包括了算法实现、示例和解释等内容。
在给定的代码示例中,`Graph` 类定义了一个简单的无向图,包含了添加节点、边的方法,以及获取节点列表的函数。`visited` 字典用于跟踪已访问的节点,`node_neighbors` 字典存储每个节点的邻接节点列表。 `depth_...