`
狂盗一枝梅
  • 浏览: 17733 次
  • 性别: Icon_minigender_1
  • 来自: 青岛
社区版块
存档分类
最新评论

【数据结构】【图论】DFS

阅读更多

      DFS(Depth-First-Search),中文名称为“深度优先搜索”,是纵向遍历图的一种递归算法。

      需求:输入edgeCount、startNode,然后输入edgeCount组数据,每组数据有两个数node1与node2,表示一条无向边,最后使用DFS算法输出遍历图的结果,数和数之间使用空格隔开。

一、Java代码

import java.util.Scanner;
class Node{
	int nodeValue;
	Node next=null;
}
public class DFS{
	private static boolean[] visited=new boolean[1024];
	private static Node[] nodes=new Node[1024];
	public static void main(String args[]){
		init();
		Scanner scanner=new Scanner(System.in);		
		int edgeCount=scanner.nextInt();
		int startNode=scanner.nextInt();
		for(int i=0;i<edgeCount;i++){
			int nodeValue1=scanner.nextInt();
			int nodeValue2=scanner.nextInt();
			
			Node node1=new Node();
			node1.nodeValue=nodeValue2;
			node1.next=nodes[nodeValue1].next;
			nodes[nodeValue1].next=node1;	

			Node node2=new Node();
			node2.nodeValue=nodeValue1;
			node2.next=nodes[nodeValue2].next;
			nodes[nodeValue2].next=node2;
		}	
		dfs(nodes,visited,startNode);
		System.out.println();
	}
	public static void dfs(Node[] nodes,boolean[] visited,int startNode){
		Node node=nodes[startNode].next;
		visited[startNode]=true;
		System.out.print(startNode+" ");
		sort(node);
		while(node!=null){
			if(visited[node.nodeValue]==false){
				dfs(nodes,visited,node.nodeValue);
			}
			node=node.next;
		}		
	}
	public static void sort(Node node){
		boolean flag=false;
		while(flag=!flag){
			Node p=node;
			Node q=p.next;
			while(q!=null){
				if(p.nodeValue>q.nodeValue){
					int temp=p.nodeValue;
					p.nodeValue=q.nodeValue;
					q.nodeValue=temp;
					flag=false;
				}else{
					p=p.next;
					q=p.next;
				}
			}				
		}
		
	}
	public static void init(){
		for(int i=0;i<visited.length;i++){
			visited[i]=false;
		}
		for(int i=0;i<nodes.length;i++){
			nodes[i]=new Node();
		}
	}
}

    上述代码中对邻接表进行了排序,所以边的输入顺序不会影响到最终的结果。

二、测试数据

输入
7 0 0 3 0 4 1 4 1 5 2 3 2 4 3 5
输出
0 3 2 4 1 5

 三、ACM

    题目链接:图的深度遍历

    AC代码(Java版):

import java.util.Scanner;
class Node{
	int nodeValue;
	Node next=null;
}
public class Main{
	private static boolean[] visited=new boolean[1024];
	private static Node[] nodes=new Node[1024];
	private static boolean isFirst=false;
	public static void main(String args[]){
		Scanner scanner=new Scanner(System.in);		
		int count=scanner.nextInt();
		while((count--)!=0){
			init();
			int nodeCount=scanner.nextInt();
			int edgeCount=scanner.nextInt();
			int startNode=0;
			for(int i=0;i<edgeCount;i++){
				int nodeValue1=scanner.nextInt();
				int nodeValue2=scanner.nextInt();
			
				Node node1=new Node();
				node1.nodeValue=nodeValue2;
				node1.next=nodes[nodeValue1].next;
				nodes[nodeValue1].next=node1;	

				Node node2=new Node();
				node2.nodeValue=nodeValue1;
				node2.next=nodes[nodeValue2].next;
				nodes[nodeValue2].next=node2;
			}	
			dfs(nodes,visited,startNode);
			System.out.println();
		}
	}
	public static void dfs(Node[] nodes,boolean[] visited,int startNode){
		Node node=nodes[startNode].next;
		visited[startNode]=true;
		if(!isFirst){
			System.out.print(startNode);
			isFirst=true;
		}else{
			System.out.print(" "+startNode);
		}
		sort(node);
		while(node!=null){
			if(visited[node.nodeValue]==false){
				dfs(nodes,visited,node.nodeValue);
			}
			node=node.next;
		}		
	}
	public static void sort(Node node){
		boolean flag=false;
		while(flag=!flag){
			Node p=node;
			Node q=p.next;
			while(q!=null){
				if(p.nodeValue>q.nodeValue){
					int temp=p.nodeValue;
					p.nodeValue=q.nodeValue;
					q.nodeValue=temp;
					flag=false;
				}else{
					p=p.next;
					q=p.next;
				}
			}				
		}
		
	}
	public static void init(){
		isFirst=false;
		for(int i=0;i<visited.length;i++){
			visited[i]=false;
		}
		for(int i=0;i<nodes.length;i++){
			nodes[i]=new Node();
		}
	}
}

    需要注意的是这里默认使用0作为遍历的起点,而且需要输入顶点的个数(虽然没用)。

 

分享到:
评论

相关推荐

    数据结构 图论 最经典的结合

    数据结构中的图论和树是两个非常重要的概念,它们在计算机科学中有着广泛的应用,尤其是在算法设计和数据存储方面。图论关注的是节点之间通过边连接的网络结构,而树是一种特殊的图,它具有单一的根节点和分层的结构...

    图论与数据结构 课后习题答案

    《图论与数据结构》是计算机科学中一门重要的理论课程,涵盖了离散数学中的核心概念,如图的基本概念、图的遍历算法、树与树形结构、图的搜索算法、最短路径问题以及数据结构如栈、队列、链表、数组、哈希表等。...

    数据结构 图论 拓扑排序

    数据结构是计算机科学中至关重要的基础,而图论作为数据结构的一个分支,研究的是网络状数据的组织方式。拓扑排序则是图论中一个实用且基础的概念,它主要用于有向无环图(DAG,Directed Acyclic Graph)的排序问题...

    图论算法 DFS深度优先遍历

    在这个过程中,DFS会用到栈这种数据结构来辅助实现。 在**VS2010**环境下编写DFS算法,开发者可以利用C++或C#等语言,利用标准模板库(STL)中的`stack`容器来实现栈操作,或者自定义栈结构来实现回溯功能。VS2010...

    图论DFS,BFS,shortestPath,topoSort,keyPath

    BFS 使用队列数据结构来存储待访问的节点。这种算法在寻找最短路径、计算图的直径或找到最近的顶点时特别有效。 3. 最短路径算法: 最短路径问题是图论中的经典问题,目标是找到两个节点之间路径的最小代价。...

    数据结构-图论-PPT

    数据结构图论是计算机科学中研究图的数据结构和算法的领域。图是由顶点和边组成的数学结构,广泛应用于计算机科学、信息科学、物理科学等领域。 图的定义:图G由两个集合V(Vertex)和E(Edge)组成,记为G=(V,E),其中...

    严蔚敏数据结构算法实现

    《严蔚敏数据结构算法实现》是一份针对计算机科学领域中的核心课程——数据结构的算法实践资料,由清华大学教授严蔚敏的经典教材《数据结构》为基础编写的。这份资源包含了严蔚敏教授在教材中提到的各种数据结构及其...

    数据结构大全,从最基础的线性数据结构到树形数据结构,再到图论,排序算法,都有完整的实现。

    这份“数据结构大全”涵盖了从基本的线性数据结构到复杂的数据结构,再到图论和排序算法,是大学生深入学习数据结构的理想资源。 1. **线性数据结构**:线性数据结构包括数组、链表、栈和队列等。数组是最基础的...

    数据结构 考试 试卷 数据结构期末复习

    数据结构是计算机科学中的核心课程,它探讨了如何在计算机中高效地组织和管理数据,以便于进行快速的检索、存储和操作。本资料主要针对数据结构期末考试进行复习,涵盖了数据结构的基本概念、主要类型以及相关的算法...

    数据结构邻接矩阵DFS非递归算法以及PRIM算法最小生成树

    在图论领域,邻接矩阵是一种常用的数据结构,用于表示图中节点之间的连接关系。本篇文章将深入探讨如何利用邻接矩阵实现深度优先遍历(DFS)的非递归算法,并介绍PRIM算法构建最小生成树。 邻接矩阵是一个二维数组...

    数据结构大全,从最基础的线性数据结构到树形数据结构,再到图论,排序算法,都有完整的实现!

    本资源包"ljg_resource1"提供了全面的数据结构知识,从基础的线性数据结构到复杂的树形结构,再到图论以及排序算法的实现。 1. **线性数据结构**:线性结构是最基本的数据结构,包括数组、链表、栈和队列。数组是一...

    数据结构课后答案.pdf

    6. **图(Graph)**:图是由顶点(节点)和连接这些顶点的边组成的复杂数据结构,用于模拟网络、图论中的关系等。图可以是有向的或无向的,并且可以包含权重。图的遍历算法有深度优先遍历(DFS)和广度优先遍历(BFS...

    数据结构与算法 数据结构与算法课后习题答案

    算法部分,主要包括排序算法(如冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等)、搜索算法(如深度优先搜索DFS、广度优先搜索BFS、A*搜索等)、图论算法(如最短路径算法Dijkstra、Floyd-Warshall、...

    数据结构 朱战力 习题解答 数据结构 朱战力 习题解答

    数据结构是计算机科学中的核心课程之一,主要研究如何在计算机中高效地组织和管理数据,以便进行快速查找、插入和删除等操作。朱战力教授的《数据结构》习题解答是一个宝贵的资源,帮助学生深入理解和掌握这门学科的...

    数据结构教程-第5版-李春葆-配套课件PPT

    图论在数据结构中扮演着重要角色,如深度优先搜索(DFS)和广度优先搜索(BFS)用于遍历图,迪杰斯特拉算法和弗洛伊德算法用于求解单源最短路径,普里姆和克鲁斯卡尔算法用于构建最小生成树。 十、堆与优先队列 堆...

    清华大学教程 --数据结构

    数据结构是计算机科学中的核心课程,它探讨了如何在计算机中有效地存储和组织数据,以便进行高效的检索、插入和删除操作。《清华大学教程 -- 数据结构》是一部权威且深入的教材,特别适合初学者和进阶者学习。这篇...

    2015-2017年青岛大学910数据结构考研真题

    数据结构是计算机科学与技术专业的一门核心课程,它研究如何在计算机中组织和存储数据,以便高效地访问和处理。对于准备参加青岛大学910数据结构考研的学生来说,了解并掌握这部分知识至关重要。本资源包含2015年至...

    2017-2021年重庆邮电大学802数据结构考研真题

    此外,图论问题和动态规划也是数据结构考试中的常见考点。图论涉及最小生成树(如Prim算法和Kruskal算法)、最短路径(Dijkstra算法、Floyd-Warshall算法)等;动态规划则是一类优化问题的解决方案,如背包问题、...

    DFS.rar_dfs_图 数据结构

    在图论和数据结构的学习中,理解并能熟练应用DFS是非常重要的,因为它在很多实际问题中都有应用,比如网络爬虫、迷宫求解、游戏状态搜索等。通过掌握DFS,你可以更好地理解和解决问题,进一步提升编程能力。

Global site tag (gtag.js) - Google Analytics