精华内容
下载资源
问答
  • 请定一个无向图,顶点编号从0到n-1,用深度优先搜索(DFS),遍历输出遍历时,先遍历节点编号小。 输入 输入第一行为整数n(0 < n < 100),表示数据组数。 对于每组数据,第一行是两个整数k,m(0 ,0...

    图的深度遍历

    Time Limit: 1000MS Memory limit: 65536K

    题目描述

    请定一个无向图,顶点编号从0到n-1,用深度优先搜索(DFS),遍历并输出。遍历时,先遍历节点编号小的。

    输入

    输入第一行为整数n(0 < n < 100),表示数据的组数。 对于每组数据,第一行是两个整数k,m(0 < k < 100,0 < m < k*k),表示有m条边,k个顶点。 下面的m行,每行是空格隔开的两个整数u,v,表示一条连接u,v顶点的无向边。

    输出

    输出有n行,对应n组输出,每行为用空格隔开的k个整数,对应一组数据,表示DFS的遍历结果。

    示例输入

    1
    4 4
    0 1
    0 2
    0 3
    2 3

    示例输出

    0 1 2 3


    #include <math.h>
    #include <string.h>
    #include <stdio.h>
    #include <iostream>
    #include <string>
    #include <algorithm>
    #include <queue>
    
    using namespace std;
    
    int map[102][102];
    int vis[102];
    int n;
    queue<int>q;
    
    void dfs(int dd)
    {
        int j;
        for(j=0; j<n; j++)
        {
            if(!vis[j] && map[dd][j]==1 )
            {
                q.push(j);
                vis[j]=1;
                dfs(j);
            }
        }
    }
    
    int main()
    {
        int t;
        cin>>t;
        int i, j;
        int m; //n个顶点,从0开始,m条边
        int u, v;
    
        while(t--)
        {
            cin>>n>>m;
            memset(map, 0, sizeof(map));
    
            memset(vis, 0, sizeof(vis));
    
            for(i=0; i<m; i++)
            {
                cin>>u>>v;
                map[u][v]=1;
                map[v][u]=1;
            }
            for(i=0; i<n; i++)
            {
                if(!vis[i])
                {
                    q.push(i);
                    vis[i]=1;
                    dfs(i);
                }
            }
    
            int ff=1;
    
            while(!q.empty())
            {
                int dd=q.front();
                if(ff==1)
                {
                    cout<<dd;
                    ff=0;
                }
                else
                  cout<<" "<<dd;
                q.pop();
            }
            cout<<endl;
        }
        return 0;
    }
    

     

    转载于:https://www.cnblogs.com/yspworld/p/4103952.html

    展开全文
  • 二叉树dfs遍历

    千次阅读 2018-08-26 16:23:10
    给一棵点带权(权值各不相同,都是小于10000正整数)二叉树中序序列和后序遍历,找一个叶子使得它到根路径上权和最小。如果有多解,该叶子本身权值应尽量小。 输入 每两行表示一棵树,其中第一行为中序...

    给一棵点带权(权值各不相同,都是小于10000的正整数)的二叉树的中序序列和后序遍历,找一个叶子使得它到根的路径上的权和最小。如果有多解,该叶子本身的权值应尽量小。

    输入

    每两行表示一棵树,其中第一行为中序遍历,第二行为后序遍历。

    输出

    输出叶子的权值

    样例输入

    3 2 1 4 5 7 6
    3 1 2 5 6 7 4
    7 8 11 3 5 16 12 18
    8 3 11 7 16 18 12 5
    255
    255

    样例输出

    1
    3
    255

    解题思路

    这个题明显就是考查二叉树的递归遍历,只要掌握了dfs的主要技巧,本题其实不难。主要需要解决的是利用题目给的中序后序序列构造成一棵二叉树,然后利用递归遍历求出权值进行保存以及判断。

    因输入没有个数 所以利用字符进行处理,代码内有单独函数

    以下是代码,以c为例:

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    int s1[100], s2[100];
    typedef struct Node TreeNode;
    struct Node {
    	TreeNode *Left;
    	TreeNode *Right;
    	int data;
    };
    
    TreeNode* build_Tree(int L1, int R1, int L2, int R2) //构建二叉树
     {
    	if (L1 > R1 || L2 > R2)
    		return NULL;
    	int i;
    	TreeNode *p = NULL;
    	p = malloc(sizeof(struct Node));//建立节点
    	p->data = s2[R2];//后序的最后一个节点就是根节点
    	for (i = L1; i < R1; i++) {  //找到中序中的根节点所在位置
    		if (s1[i] == p->data)
    			break;
    	}
    	// 利用中序序列的相对位置确定后续序列的位置
    	p->Left = build_Tree(L1, i - 1, L2, (L2 + ((i - 1) - L1)));
    	p->Right = build_Tree(i + 1, R1, (R2 - (R1 - (i + 1))) - 1, (R2 - 1));
    
    	return p;
    }
    
    int best=100001, best_sum=10000000; //叶节点数据不超过10000
    void dfs(TreeNode *p, int sum)
    {
    	if (p == NULL)
    		return;
    	sum += p->data;
    	if (p->Left == NULL && p->Right == NULL) //如果是叶节点
    	{
    		if (sum < best_sum) //如果是符合条件的节点,则进行替换
    		{
    			best_sum = sum;
    			best = p->data;
    		}
    		else if (sum == best_sum) { //如果和权值相同 则判断叶节点
    			if (p->data < sum)
    				p->data = sum;
    		}
    	}
    
    	//递归调用左右节点
    	dfs(p->Left, sum);
    	dfs(p->Right, sum);
    
    }
    
    int check(int *data, char *s)//处理输入数据使用
    {
    	int j = 0;
    	for (int i = 0; s[i] != '\0'; i++)
    	{
    		j++;
    		while (s[i] != ' ' && s[i] != '\0') {
    			data[j] = data[j] * 10 + s[i] - '0';//把节点数据变为整数
    			i++;
    		}
    	}
    	return j;
    }
    
    //主函数
    int main()
    {
    	int j = 0, n1, n2;
    	char s[100];
    	gets(s);//读入字符串
    	n1 = check(s1, s);
    	gets(s);
    	n2 = check(s2, s);
    	TreeNode *head = build_Tree(1, n1 - 1, 1, n2 - 1);
    	dfs(head, 0);
    	printf("%d", best);
    	return 0;
    }

     

    展开全文
  • 给定一个可包含重复数字的序列,返回所有不重复全排列。 示例: 输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ] 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/permutations-ii 著作权...

    47. 全排列 II

    给定一个可包含重复数字的序列,返回所有不重复的全排列。

    示例:

    输入: [1,1,2]
    输出:
    [
      [1,1,2],
      [1,2,1],
      [2,1,1]
    ]
    

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/permutations-ii
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    解题
    难点:数组中有相同元素,但输出的全排列数组不能有相同的排列;

    需要对每次的dfs算法进行剪枝!

    去重剪枝需要先排序,然后遍历时跳过相同元素,进行剪枝!

    解法

    class Solution {
    public:
        vector<vector<int>> permuteUnique(vector<int>& nums) {
            sort(nums.begin(),nums.end());              //先排序+跳过除重
            visited.resize(nums.size(),false);
            dfs(nums.size(),nums);
            return result;
        }
    
    private:
        vector<vector<int>> result;
        vector<int> path;
        vector<bool>visited;
        void dfs(int n,vector<int> &nums)
        {
            if(path.size()==n)
            {
                result.push_back(path);
                return;
            }
    
            for(int i=0;i<n;i++)
            {
                if(visited[i]) continue;
                if(i>0&&nums[i]==nums[i-1]&&!visited[i-1]) continue;
                visited[i]=1;
                path.push_back(nums[i]);
                dfs(n,nums);
                visited[i]=0;
                path.pop_back();
            }
        }
    };
    

    注意点
    去重行如下,在for循环中多加了一行;

      if(i>0&&nums[i]==nums[i-1]&&!visited[i-1]) continue;
    

    当执行该行时,说明当前遍历的i与i-1的值相等,而且i-1已经完成遍历,故此次path要添加数字的位置已经添加过该值,无需重复添加,跳过即可;
    (相同元素相邻放置是这个去重的关键,所以需要先对nums排序);

    稍微改变

    	  if(i>0&&nums[i]==nums[i-1]&&visited[i-1]) continue;
    

    去掉visited[i-1]前面的感叹号,程序也能得到正确答案;
    当有3个以上相等元素时,取前两个元素,都取不到后一个元素,故dfs会完全执行后失败返回,浪费很多时间,直到最先取相同元素的最后一个时,且逐个往前取相同元素时,会成功返回一个解,故此写法复杂度远远大于上面的写法;

    总结
    重复答案的 去重+剪枝 考虑先排序,后在遍历的合适时间跳过相同元素,完成剪枝去重;

    展开全文
  • 给定一个 没有重复 数字的序列,返回其所有可能全排列。 示例: 输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 来源:力扣(LeetCode) 链接:...

    46. 全排列

    给定一个 没有重复 数字的序列,返回其所有可能的全排列。

    示例:

    输入: [1,2,3]
    输出:
    [
      [1,2,3],
      [1,3,2],
      [2,1,3],
      [2,3,1],
      [3,1,2],
      [3,2,1]
    ]
    

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/permutations
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    解题
    将遍历操作转化成树的叶子节点遍历,每一层的结点增加一个未遍历的数;

    class Solution {
    public:
        vector<vector<int>> permute(vector<int>& nums) {
            int n=nums.size();
            vector<bool> visited(n,false);
            dfs(nums,path,visited,n,0);
            
            return result;
        }
    
    private:
        vector<vector<int>> result;
        vector<int> path;
        void dfs(vector<int> & nums,vector<int> &path,vector<bool> &visited,int n,int cur)
        {
            if(cur==n) 
            {
                result.push_back(path);
                return;
            }
    
            for(int i=0;i<nums.size();i++)
            {
                if(!visited[i]){          //表示下标为i的数字已遍历
                    path.push_back(nums[i]);
                    visited[i]=true;
                    dfs(nums,path,visited,n,cur+1);
                    visited[i]=false;
                    path.pop_back();
                }
            }
        }
    };
    

    注意点
    visited数组标记下标为i的数已遍历,并非值为i的数已遍历(因为存在负数,下标无法为负数);

    回溯算法:找到路径后需要撤销原先的操作(标记已遍历和加入path数组这两个操作);

    解题2:next_permutation函数
    用法:next_permutation(数组头地址,数组尾地址),将传入数组直接改写

    class Solution {
    public:
        vector<vector<int>> permute(vector<int>& nums) {
            vector<vector<int>> result;
            sort(nums.begin(),nums.end());
            result.push_back(nums);
            while(next_permutation(nums.begin(),nums.end()))
            {
                result.push_back(nums);
            }
            return result;
        }
    };
    
    展开全文
  • 给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。 解题报告: dfs求出这棵树来,然后bfs求层序遍历就行了。 AC代码: #include&lt;cstdio&gt; #...
  • 的DFS、BFS遍历补充

    2010-07-05 11:15:18
    实现无向图建立,深度优先和广度优先遍历输出遍历序列
  • 无向图的DFS、BFS遍历

    2010-07-05 11:10:39
    实现无向图的建立,深度优先、广度优先遍历遍历序列的输出
  • 因为在访问每一个顶点时顺便把其编号输出,所有最后得到的就是这整个图的DFS遍历序列。 int Visist[MAX]={0};//定义全局变量观察每一个被访问过的结点 static int _count=0;//记录DFS的输出次数 void DFS(G
  • 首先要明确:把中序遍历的结果push_back到数组v1里面,直接输出就是中序,排序输出就是层序(排序方式,层数小的排前面,相同层数时,index大的排前面 用到同种方法的题目:1127 ZigZagging on a Tree (30分)、1099 ...
  • 的遍历(BFS与DFS)

    2016-11-19 16:14:30
    输入:建立图的存储结构:顶点和边(弧),例:无向图G的顶点V={A,B,C,D,E,F,G,H}...输出:深度优先遍历的顶点序列(按照存储结构):A,B,D,H,E,C,F,G(或者其它的不同顺序的序列) import java.util.LinkedL
  • 给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。 输入格式: 输入第一行给出一个正整数N(≤30),是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给...
  • 给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。 输入格式: 输入第一行给出一个正整数N(≤30),是二叉树中结点的个数。第二行给出其后序遍历序列。第三行...
  • 图深度优先遍历 编写程序对给定 有向图(不一定连通) 进行深度优先遍历,图中包含n个顶点,编号为0至n-1。本题限定在深度优先遍历过程中,...输出为一行整数,每个整数后一个空格,即该有向图深度优先遍历结点序列
  • 写出深度优先遍历的递归和非递归算法。 (2)根据建立的有向图,判断该图是否是有向无环图,若是,则输出其一种拓扑有序序列。*/ #include #include #define max 20 #define SIZE 20 #define MORE 10 typedef struct...
  • 根据输入构造二叉树,输出该二叉树先序序列。二叉树共有N个节点,节点编号是1到N。约定1号节点是根节点。 输入格式: 第一行输入整数N。 接下来有N行,依次给出1到N节点左孩子和右孩子。对于这N行中每一行,有...
  • 深度遍历(dfs)

    2017-02-21 17:11:01
    Problem Description 有一个地下迷宫,它通道都是直,而通道所有交叉点(包括通道端点)上都有一盏灯和一个开关;...若可以点亮所有结点灯,则输出从S开始并以S结束的序列序列中相邻顶点
  • 输入一个非空整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 题意:该题描述的不够清楚,构建二叉树的依据是:左子树<当前根&...
  • L2-006. 树的遍历 时间限制 400 ms 内存限制 65536 kB ...给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。 输入格式: 输入第
  • 4、遍历序列从输入第一个结点开始。 【输入形式】 对于如上所示有向图,设置输入形式如下: 5 //结点个数 A B C D E//输入多个结点值,每个值之间用一个空格隔开 6 //有向弧个数 A B //第1条边弧尾...
  • 问题及代码: /* ...* All rights reserved. * 文件名称:ccc.cpp * 作 者:陈梦雪 ...* 问题描述: 实现图遍历算法,分别输出如下图结构深度优先(DFS)遍历序列和广度优先遍历(BFS)序列。 * 输入描述:
  • 创建和遍历

    2021-05-29 15:43:45
    创建无向图存储结构(图信息由用户输入) 输出无向图信息 (选做)深度优先遍历DFS)无向图,并输出遍历序列 (选做)广度优先遍历(BFS)无向图,并输出遍历序列
  • 的遍历

    2018-01-22 12:50:07
    课程名称:数据结构 实验项目名称:图结构基本操作实现 实验目的: 1.掌握图基本操作—遍历。 实验要求: ...1、 分别用DFS和BFS方法实现一个...3、 分别输出DFS和BFS两种遍历序列; 实验报告中给出DFS和BF
  • 2. Breadth First Search:广度优先搜索,利用队列,使用类似于二叉树层次遍历的方法,将顶点V出队后将V的邻接点入队,重复上述过程,直至访问完所有的节点(队列为空)。3.Depth First Search: 深度优先搜索,从...
  • 实现图的遍历算法

    千次阅读 2019-05-28 19:32:18
    (1)输出有向图G从顶点0开始深度优先遍历序列(递归算法)。 (2)输出有向图G从顶点0开始深度优先遍历序列(非递归算法)。 (3)输出有向图G从顶点0开始广度优先遍历序列。 设备: 计算机,VC6.0 注意点: ...
  • (3)指定任意顶点x为初始顶点,对图G作DFS遍历,输出DFS顶点序列(提示:使用一个栈实现DFS); (4)指定任意顶点x为初始顶点,对图G作BFS遍历,输出BFS顶点序列(提示:使用一个队列实现BFS); (5)输入顶点x,查找图G:...
  • 7-9 玩转二叉链表 (25分) 设计程序,按先序创建二叉树二叉链表;然后先序、中序、后序遍历二叉树。 输入格式: 按先序输入一棵二叉树。二叉树中每个结点键值用字符表示,...题目给出是一个dfs先序遍历, 对于
  • 基于邻接矩阵深度优先搜索遍历

    千次阅读 2017-11-30 20:58:59
    给定一个无向连通图,顶点编号从0到n-1,用深度优先搜索(DFS)遍历输出从某个顶点出发的遍历序列。(同一个结点同层邻接点,节点编号小优先遍历) Input 输入第一行为整数n(0 对于每组数据,第一行是
  • /* ... All rights reserved. 文件名称:第十二周项目3 - 图遍历算法实现.cpp ...问题描述: 实现图遍历算法,分别输出如下图结构深度优先(DFS)遍历序列和广度优先遍历(BFS)序列。 输入描述: 若干测试数据。
  • 解题思路: 参考了『手画图解』剖析DFS、BFS解法 | 二叉树的序列化与反序列化。 该题实际上并没有严格要求将二叉树序列化为[1,2,3,null,null,4,5]形式,只要...使用DFS遍历每个节点。 如果遇到节点为空,则返回X
  • 相当于给出二叉树先序遍历序列和中序遍历序列,重新构造这颗二叉树,并且输出这颗二叉树后续遍历序列。压栈顺序相当于先序遍历序列,出栈顺序相当于中序遍历序列。 提交结果如下: 提交代码如下: #...

空空如也

空空如也

1 2 3 4 5 ... 16
收藏数 304
精华内容 121
关键字:

dfs遍历的输出序列