`

java 图论一 深度遍历和广度遍历

阅读更多

图对建模很有帮助。

 

图的基本知识:

 

Java实现图的两种方法

邻接矩阵

邻接矩阵是用二维数据,使用1代表节点间有边,如下表格:

 

A

B

C

D

A

0

1

1

1

B

1

0

0

1

C

1

0

0

0

D

1

1

0

0

 

邻接表

临界表是使用类似链表,连接节点,表示有边

定点

包含邻接顶点的链表

A

B->C->D

B

A->D

C

A

D

A->B

 

深度遍历思路:

 

使用栈,查找栈顶顶点连通到的,没有访问的顶点,使其入栈,并访问。当找不到,则当前栈顶元素出栈。否则继续查找。

 

 

广度遍历思路:

 

使用队列,查找队列头连通的,没有访问的顶点,使其入队列,并访问。当找不到,则当前顶点出队列。否则继续遍历当前队列顶点

 

他们的不同之处就在,栈访问的顶点变化,会越来越深;队列访问的顶点不变化,只有出队列后才换节点访问。

 

 

 

图在java中的邻接矩阵实现:

 

package com.Construction;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class GraphSimpleExample {
	private final int MAX_VERTS = 20;
	private GraphNodeBean nodeList[];
	private int adjMat[][];
	private int nVerts;
	
	public GraphSimpleExample(){
		nodeList = new GraphNodeBean[MAX_VERTS];
		adjMat = new int[MAX_VERTS][MAX_VERTS];
		nVerts = 0;
		for (int i = 0; i < MAX_VERTS; i++) {
			for (int j = 0; j < MAX_VERTS; j++) {
				adjMat[i][j] = 0;
			}
		}
	}
	
	public void addNode(char label){
		nodeList[nVerts++] = new GraphNodeBean(label);
	}
	
	public void addEdge(int start,int end){
		adjMat[start][end] = 1;
		adjMat[end][start] = 1;
	}

	public void displayGraphNode(int v){
		System.out.println(nodeList[v].label);
	}
	
	/**
	 * 获得未访问节点
	 * @param v
	 * @return
	 */
	public int getAdjUnvisitedVertex(int v){
		for (int i = 0; i < nVerts; i++) {
			if(adjMat[v][i]==1 && nodeList[i].isVisited == false)
				return i;
		}
		return -1;
	}
	
	/**
	 * deft first 
	 */
	public void dfs(){
		@SuppressWarnings("rawtypes")
		Stack<Integer> theStack = new Stack<Integer>();
		nodeList[0].isVisited = true;
		displayGraphNode(0);
		theStack.push(0);
		
		while(!theStack.isEmpty()){
			int v = getAdjUnvisitedVertex(theStack.peek());
			if(v == -1)
				theStack.pop();
			else{
				nodeList[v].isVisited = true;
				displayGraphNode(v);
				theStack.push(v);
			}
		}
//		for (int i = 0; i < nVerts; i++) {
//			nodeList[i].isVisited = false;
//		}
	}
	
	public void bds(){
		Queue<Integer> theQueue = new LinkedList<Integer>();
		
		nodeList[0].isVisited = true;
		displayGraphNode(0);
		theQueue.offer(0);
		int v2;
		
		while(!theQueue.isEmpty()){
			int v1 = theQueue.poll();
			while((v2 = getAdjUnvisitedVertex(v1)) != -1){
				nodeList[v2].isVisited = true;
				displayGraphNode(v2);
				theQueue.add(v2);
			}
		}
//		for (int i = 0; i < nVerts; i++) {
//		nodeList[i].isVisited = false;
//	}
		
	}
	
}

 其中dfs是深度优先算法

bfs是广度优先算法

分享到:
评论
1 楼 chenbaohua518 2013-10-08  
你的头像照片是你的女神?

相关推荐

    图的遍历(有向图和无向图)

    图的遍历是图论中的一个基础概念,用于探索图中的所有节点以及它们之间的连接关系。在计算机科学中,这通常用于数据结构的处理、网络路由、搜索算法等。本主题将详细介绍有向图和无向图的深度优先遍历(DFS)与宽度...

    图的遍历(java)

    首先,我们来看看“图的深度广度遍历”。深度优先搜索(DFS, Depth First Search)和广度优先搜索(BFS, Breadth First Search)是图遍历的两种基本策略。 1. **深度优先搜索**:DFS是一种递归策略,它从图的一个...

    图遍历的演示报告及源代码

    本文主要探讨了在连通无向图上的两种遍历方法——深度优先搜索(DFS)和广度优先搜索(BFS),并结合C++编程语言进行了实践。 深度优先搜索通常使用栈来实现。在给定的概要设计中,ADT Stack被定义为具有初始化、...

    邻接矩阵和邻接表存储的图的遍历

    本主题将深入探讨两种常见的图存储方式——邻接矩阵和邻接表,以及如何在这两种存储方式下实现深度优先遍历(DFS)和广度优先遍历(BFS)。 首先,邻接矩阵是一种直观的图表示方法,它使用二维数组来存储图中每个...

    城市遍历求解问题

    城市遍历求解问题在计算机科学中是一个经典的图论问题,通常被用来模拟旅行者试图以最有效的方式访问一系列城市。在这个Java课程设计项目中,我们可能会遇到如何使用编程技术来解决这一问题的挑战。这个问题可以被视...

    图的遍历和生成树求解实现 数据结构课程设计

    本次课程设计的主题是“图的遍历和生成树求解实现”,这涵盖了两个核心概念:图的遍历算法(深度优先搜索DFS和广度优先搜索BFS)以及最小生成树(如Prim's算法或Kruskal's算法)。我们将深入探讨这两个知识点,并...

    分层遍历二叉树

    - **易于理解和实现**:相较于深度优先搜索,分层遍历更容易理解和编码。 - **良好的空间效率**:只需要额外的空间来存储当前层的节点,因此对于高度相对较小的树来说,空间复杂度较低。 - **方便获取各层节点数量**...

    数据结构 图的遍历(实现代码).zip

    本资料包含关于图的深度优先遍历(DFS)和广度优先遍历(BFS)的实现代码,包括递归和非递归方式。下面将详细讲解这两种遍历方法。 1. 深度优先遍历(DFS) 深度优先遍历是从起点开始,尽可能深地探索图的分支。当...

    基础07图的遍历和最小生成树.flv.zip

    在IT领域,图的遍历和最小生成树是图论中的两个重要概念,它们在算法设计和网络优化问题中有着广泛的应用。让我们深入探讨这两个概念。 首先,我们来看图的遍历。图是由顶点(节点)和边(连接顶点的线)构成的数据...

    实现深度优先广度优先算法

    深度优先搜索(DFS, Depth-First Search)和广度优先搜索(BFS, Breadth-First Search)是图论中的两种基本搜索策略,用于遍历或搜索树或图。这两种算法在解决各种问题中有着广泛的应用,如路径查找、判断连通性、...

    图的几种常用算法(广度/深度优先搜索,最小生成树,弗洛伊德,拓扑排序....)java实现,简单易懂。

    在计算机科学中,图是一种非常重要的数据结构,用于表示对象之间的关系。本资源包含了一些图算法的Java实现,包括但不限于广度...理解这些算法的原理和Java实现,对于提升编程能力,特别是解决图论问题的能力大有裨益。

    Java语言程序设计(一)实践操作04748

    图的遍历算法主要有深度优先搜索(Depth First Search, DFS)和广度优先搜索(Breadth First Search, BFS)两种。 ### 总结 本次实践操作涵盖了图论中的两个经典问题——最小生成树的求解和堆数据结构的应用。通过...

    图论算法软件.rar

    在编程中,有许多开源库支持图论算法,如C++的`Boost.Graph`库,Python的`NetworkX`,Java的`JUNG`等,这些库提供了丰富的接口和实现,简化了开发者在实际项目中应用图论算法的难度。 综上所述,“图论算法软件....

    图论算法-求(有向)图中任意两点间所有路径

    图论是计算机科学中的一个重要分支,它研究网络结构和关系,包括节点、边以及它们之间的连接。在有向图中,边是有方向的,从一个节点指向另一个节点,表示一种特定的流向。本主题主要关注如何在有向图中找到任意两点...

    图论及安全威胁建模

    1. 深度优先搜索(DFS)和广度优先搜索(BFS):用于遍历和查找图中的特定路径或节点,帮助识别潜在的威胁路径。 2. 最小生成树算法(如Prim's和Kruskal's):用于构建网络的安全通信路径,减少攻击面。 3. 矩阵运算...

    daohang.rar_完全遍历

    常见的图遍历方法有深度优先搜索(DFS,Depth-First Search)和广度优先搜索(BFS,Breadth-First Search)。 1. **深度优先搜索**:DFS是一种递归策略,从起始节点开始,尽可能深地探索图的分支,直到达到叶子节点...

    Java骑士游历(课程设计)

    3. **算法设计**:骑士游历的算法设计是关键,可以使用深度优先搜索(DFS)或广度优先搜索(BFS)来遍历所有可能的路径。DFS通常用于寻找是否存在解,而BFS可以找到最短路径。骑士游历问题也可以转换成图论中的遍历...

    suanfa.zip_图论_图论算法

    在IT领域,图论是一种非常重要的理论基础,它在计算机科学和算法设计中扮演着核心角色。图论算法是解决复杂问题的有效工具,尤其在处理网络、数据结构和优化问题时。"suanfa.zip_图论_图论算法"这个压缩包文件很可能...

    图论算法及其matlab程序代码.pdf

    3. **遍历算法**:包括深度优先搜索(DFS)和广度优先搜索(BFS)。DFS适用于寻找路径或检测环,BFS常用于找到最短路径。 4. **最短路径算法**:Dijkstra算法用于找到单源最短路径,Floyd-Warshall算法用于求解所有...

Global site tag (gtag.js) - Google Analytics