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
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会用到栈这种数据结构来辅助实现。 在**VS2010**环境下编写DFS算法,开发者可以利用C++或C#等语言,利用标准模板库(STL)中的`stack`容器来实现栈操作,或者自定义栈结构来实现回溯功能。VS2010...
BFS 使用队列数据结构来存储待访问的节点。这种算法在寻找最短路径、计算图的直径或找到最近的顶点时特别有效。 3. 最短路径算法: 最短路径问题是图论中的经典问题,目标是找到两个节点之间路径的最小代价。...
数据结构图论是计算机科学中研究图的数据结构和算法的领域。图是由顶点和边组成的数学结构,广泛应用于计算机科学、信息科学、物理科学等领域。 图的定义:图G由两个集合V(Vertex)和E(Edge)组成,记为G=(V,E),其中...
《严蔚敏数据结构算法实现》是一份针对计算机科学领域中的核心课程——数据结构的算法实践资料,由清华大学教授严蔚敏的经典教材《数据结构》为基础编写的。这份资源包含了严蔚敏教授在教材中提到的各种数据结构及其...
这份“数据结构大全”涵盖了从基本的线性数据结构到复杂的数据结构,再到图论和排序算法,是大学生深入学习数据结构的理想资源。 1. **线性数据结构**:线性数据结构包括数组、链表、栈和队列等。数组是最基础的...
数据结构是计算机科学中的核心课程,它探讨了如何在计算机中高效地组织和管理数据,以便于进行快速的检索、存储和操作。本资料主要针对数据结构期末考试进行复习,涵盖了数据结构的基本概念、主要类型以及相关的算法...
在图论领域,邻接矩阵是一种常用的数据结构,用于表示图中节点之间的连接关系。本篇文章将深入探讨如何利用邻接矩阵实现深度优先遍历(DFS)的非递归算法,并介绍PRIM算法构建最小生成树。 邻接矩阵是一个二维数组...
本资源包"ljg_resource1"提供了全面的数据结构知识,从基础的线性数据结构到复杂的树形结构,再到图论以及排序算法的实现。 1. **线性数据结构**:线性结构是最基本的数据结构,包括数组、链表、栈和队列。数组是一...
6. **图(Graph)**:图是由顶点(节点)和连接这些顶点的边组成的复杂数据结构,用于模拟网络、图论中的关系等。图可以是有向的或无向的,并且可以包含权重。图的遍历算法有深度优先遍历(DFS)和广度优先遍历(BFS...
算法部分,主要包括排序算法(如冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等)、搜索算法(如深度优先搜索DFS、广度优先搜索BFS、A*搜索等)、图论算法(如最短路径算法Dijkstra、Floyd-Warshall、...
数据结构是计算机科学中的核心课程之一,主要研究如何在计算机中高效地组织和管理数据,以便进行快速查找、插入和删除等操作。朱战力教授的《数据结构》习题解答是一个宝贵的资源,帮助学生深入理解和掌握这门学科的...
图论在数据结构中扮演着重要角色,如深度优先搜索(DFS)和广度优先搜索(BFS)用于遍历图,迪杰斯特拉算法和弗洛伊德算法用于求解单源最短路径,普里姆和克鲁斯卡尔算法用于构建最小生成树。 十、堆与优先队列 堆...
数据结构是计算机科学中的核心课程,它探讨了如何在计算机中有效地存储和组织数据,以便进行高效的检索、插入和删除操作。《清华大学教程 -- 数据结构》是一部权威且深入的教材,特别适合初学者和进阶者学习。这篇...
数据结构是计算机科学与技术专业的一门核心课程,它研究如何在计算机中组织和存储数据,以便高效地访问和处理。对于准备参加青岛大学910数据结构考研的学生来说,了解并掌握这部分知识至关重要。本资源包含2015年至...
此外,图论问题和动态规划也是数据结构考试中的常见考点。图论涉及最小生成树(如Prim算法和Kruskal算法)、最短路径(Dijkstra算法、Floyd-Warshall算法)等;动态规划则是一类优化问题的解决方案,如背包问题、...
在图论和数据结构的学习中,理解并能熟练应用DFS是非常重要的,因为它在很多实际问题中都有应用,比如网络爬虫、迷宫求解、游戏状态搜索等。通过掌握DFS,你可以更好地理解和解决问题,进一步提升编程能力。