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作为遍历的起点,而且需要输入顶点的个数(虽然没用)。
相关推荐
其涵盖了数据结构中图章节的大部分算法 #include #include #include #include #include #ifndef ONCE_GRAPH #define ONCE_GRAPH const int MAX_NUM=32767; const int QUEUESIZE=100; struct ArcNode {int adjvex; ...
数据结构图论中,实现邻接矩阵的深度遍历和邻接矩阵广度遍历.
数据结构 —— 代码模板链接 常用代码模板2——数据结构 链表与邻接表:树与图的存储 栈与队列:单调队列、单调栈 kmp Trie 并查集 堆 Hash表 搜索与图论 —— 代码模板链接 常用代码模板3——搜索与图论 DFS与BFS...
提供了邻接矩阵,邻接表,哈希图的图数据结构以及顶点、边访问接口 提供邻接顶点访问迭代器,便于邻接顶点的单独访问,以及非递归式的dfs访问。 提供基于虚图类的图算法框架,目前已实现最短路径、最大团、最大匹配...
数据结构 —— 代码模板链接 常用代码模板2——数据结构 链表与邻接表:树与图的存储 栈与队列:单调队列、单调栈 kmp Trie 并查集 堆 Hash表 搜索与图论 —— 代码模板链接 常用代码模板3——搜索与图论 DFS与BFS...
数据结构基础总结;树型数据结构知识总结(包括二叉搜索树,AVL树,红黑树等);图论知识总结(包括DFS,BFS等),基础算法总结(包括8种排序算法总结,常用算法思想等。)
3、 结构 58 3.1 并查集 58 3.2 堆 59 3.3 线段树 60 3.4 子段和 65 3.5 子阵和 65 4、 数论 66 4.1 阶乘最后非0位 66 4.2 模线性方程组 67 4.3 素数 68 4.4 欧拉函数 69 5、 数值计算 70 5.1 定积分计算(Romberg) ...
002.玩转数据结构 概述 数据结构 数据结构研究的是数据如何在计算机中进行组织和存储,使得我们可以高效的获取数据或者修改数据 数据结构分类 线性结构 数组 栈 队列 链表 哈希表 树结构 二叉树 二分搜索树 AVL 红黑...
目录 一.数论 4 1.阶乘最后非零位 4 2. 模线性方程(组) 4 3. 素数表 6 4. 素数随机判定(miller_rabin) 6 5. 质因数分解 7 6. 最大公约数欧拉函数 8 ...数据结构: 1.顺序队列 2.顺序栈 3.链表 4.链栈 5.二叉树
便于学习图论基础和数据结构初学者理解树和图的结构与遍历
数据结构与算法 从四月份开始正式的断断续续刷题,有过迷茫,有过崩溃,有过看不清脚下的路,有过陷在众多知识点里的迷惑。 也想过自己是不是真的就刷不好题了,这么多知识点我是不是真的就无法弄懂了,为什么一个...
常用代码模板2——数据结构 链表与邻接表:树与图的存储 栈与队列:单调队列、单调栈 kmp Trie 并查集 堆 Hash表 C++ STL使用技巧 搜索与图论 —— 代码模板链接 常用代码模板3——搜索与图论 DFS与BFS 树与图的遍历...
数据结构和算法,LC = LeetCode,CLRS = Cormen、Leiserson、Rivest 和 Stein,BFS/DFS = 广度/深度优先搜索,DP = 动态编程。 时间复杂度 视频编号1-16 评论:看完这 16 个视频后,我可以保证您肯定会掌握时间...
天梯赛 1.排序算法:常见的排序算法包括冒泡排序、...8.数据结构:包括树、 堆、图等数据结构,需要熟练掌握其基本原理、 结构特点、操作等方面的内容。 9.其他算法: 例如双指针算法、 滑动窗口算法、 分治算法、 背
数据结构(栈、队列、树、哈希表) 动态规划 贪心算法 分治算法 数学类 数论(素数判定、约数、同余) 组合数学(排列、组合、容斥原理) 线性代数(矩阵运算、行列式) 概率论(事件概率、条件概率) 其他类型 ...
2.数据结构链表与合并表:树与图的存储栈与实例:单调、、单调栈kmp Trie并查集堆Hash表C ++ STL使用技巧 3.搜索与图论 DFS与BFS树与图的遍历:拓扑排序最短最小最小生成树 4.数学知识 质数约数欧拉函数快速幂扩展...
数据结构 并查集 树状数组 线段树 字典树 Splay ST表&划分树 树链剖分&Link;-Cut Tree 图论 强连通分量 1 双联通分量 割点和桥 拓扑排序 最短路 Dijkstra 最短路 SPFA 最短路 Floyed 次短路与第K短路 最近公共祖先...
本资料为西安电子科技大学 ACM/ICPC程序设计 选修课的教学PPT,包括基本数据结构,STL、BFS、DFS、动态规划、图论、计算几何、组合数学、网络流等专题讲解。
对ACM竞赛的算法大概分了一下类,分成了数学、数据结构和算法三大块。 一 数学(Mathematics) 1 离散数学(Discrete Mathematics) 1.1 图论(Graph Theory) 图的遍历(Graph Traversal): DFS, BFS 最小生成树...