精华内容
下载资源
问答
  • 前序,中序遍历,在此就不大家下说明了,如不懂请先理解,再来看此篇文章。 当我们拿到前序和中序时,如何重新构建一颗新的数呢? 首先,大家都知道的,由中序遍历序列可知,第一个节点是根节点, 其次,由...

    前序,中序遍历,在此就不向大家向下说明了,如有不懂请先理解,再来看此篇文章。

    当我们拿到前序和中序时,如何重新构建一颗新的数呢?

    首先,大家都知道的,由中序遍历序列可知,第一个节点是根节点,
    其次,由前序遍历序列可知,第一个节点是根节点的左子树节点,而且前序遍历中,根节点左边是左子树,右边是右子树
    ,因此通过中序遍历的根节点可以确定的是:

    根节点在前序遍历中的位置(通过遍历前序遍历序列,比较每一个节点与中序遍历中的第一个节点即根节点可知); 左子树的节点数,因为一旦找到前序遍历中根节点的位置,就找到左右子树的分界点,也就是说,前序遍历中根节点左边的都是左子树节点,可以通过遍历知道左子树的节点数; 同样,右子树的节点数也可以确定。

    我们可以这样来重新构造它。

    假如,我们要构建的树是这样的


    现在,我们知道它的根节点,和左右节点的个数,正如下图


    然后现在,我们只能重建它的左树,然后重建它的右树。依次这样递归下去

    <span style="font-size:18px;">void Findpost(const vector<T> prev, const vector<T> in)
    	{
    		Del();
    		_root = Greattree(prev,in);
    	}
    
    	BinaryTreeNode<T>* Greattree(const vector<T> prev, const vector<T> in)
    	{
    		if(prev.size() == 0 || in.size() == 0)  //如果前序或中序的值为空的话,条件不满足
    			return NULL;
    
    		T gen = 0;
    		BinaryTreeNode<T>* root = new BinaryTreeNode<T>(prev[0]);  //首先建立根节点
    
    		vector<T> prev_p,prev_e;
    		vector<T> in_p,in_e;
    
    		for(int i = 0;i < in.size();i++)    //寻找根节点在中序中的位置
    		{
    			if(in[i] == prev[0])
    			{
    				gen = i;
    				break;
    			}
    		}
    
    		for(int i = 0;i < gen; i++)   //计算出左节点个数
    		{
    			in_p.push_back(in[i]);
    			prev_p.push_back(prev[i+1]);
    		}
    
    		for(int i = gen+1; i< in.size(); i++ )  //计算右系欸但个数
    		{
    			in_e.push_back(in[i]);
    			prev_e.push_back(prev[i]);
    		}
    
    		root->_left = Greattree(prev_p,in_p);  //依次递归下去
    		root->_right = Greattree(prev_e,in_e);
    		return  root;
    		
    	}
    </span>


    由于本人使用的是模板参数,如有需要,完整二叉树代码在点击打开链接这里,请读者自行需要便可观看。


    本博文对 前序遍历序列和中序遍历序列构造二叉树算法做了粗略的介绍,如有不足,欢迎指正。


    展开全文
  • 向图的广度遍历序列一般会多种广度遍历序列。 要求:1对于给定的无向图,输出所有的正确的广度遍历序列 2对任何给定的存储为邻接矩阵的图都能够处理 3 给定起点 提示:采用树来存储多个广度遍历序列 ...
  • 如果有一个有向图,他有始点无法到达的顶点,即始点不存在到达次顶点的路径,那么此时dfs和bfs应该怎么处理呢? 比如有一个有向图G,他有8个顶点(1-8),邻接矩阵如下。 0 0 1 0 0 0 0 1 0 0 1 0 0 1 1 0 ...
  • 我们知道,二叉树的遍历序列有三种:先序遍历(VLR)、中序遍历(LVR)、后序遍历(LRV)。(不谈别的遍历,如层次遍历。默认访问顺序是先左后右) 这三种遍历序列在严蔚敏编撰的《数据结构(C语言版)》 一书中是这样定义...

    遍历序列

    能看到这篇章,想必对二叉树有所了解,我就在这里不介绍二叉树的定义及性质啥的了。

    我们知道,二叉树的遍历序列有三种:先序遍历(VLR)中序遍历(LVR)后序遍历(LRV)。(不谈别的遍历,如层次遍历。默认访问顺序是先左后右)

    这三种遍历序列在严蔚敏编撰的《数据结构(C语言版)》 一书中是这样定义的:

    二叉树若为空,则返回空;

    先序遍历:
    (1)访问根节点
    (2)先序遍历左子树
    (3)先序遍历右子数
    中序遍历:
    (1)中序遍历左子树
    (2)访问根节点
    (3)中序遍历右子树
    后序遍历:
    (1)后序遍历左子树
    (2)后序遍历右子树
    (3)访问根节点

    我不知道你们觉得绕不绕,我根据二叉树写这三个序列时,反正是觉得有点绕,然后就这样记这三个遍历序列的规则的:

    第一次遇见根节点记为第一次
    第二次遇见根节点记为第二次
    第三次遇见根节点记为第三次

    先序遍历:
    该节点第一次遇见就访问
    中序遍历:
    该节点第二次遇见就访问
    后序遍历:
    该节点第三次遇见就访问

    有人就要问了,第一次我能理解,要是这个节点没有左/右孩子的第二/三次该如何理解?看下面
    访问次序
    A是一个叶子节点,它没有孩子,从父节点 ? 到达A,我称为第一次遇见A,访问A的左孩子发现没有,我掉头回来又遇上A,称为第二次遇见A,再访问A的右孩子,发现还是没有,继续掉头回来遇上A,称为第三次。就算你没有孩子,我还是会存在第二次和第三次遇见你。感兴趣的小伙伴要是还是想不通,用笔沿着树走,只能用一条线把所有遍历序列连出来,你就明白这个逻辑了。

    这个方法和代码的逻辑也是也是一样的:就算某节点没有孩子,代码里还是要往深度方向访问,看存不存在孩子。

    来看,下面有一个我自己随手构建的二叉树:
    二叉树
    根据规则可以很容易写出该树对应的三个序列,如下:

    先序序列:ABDEFCHGI
    中序序列:DBFEAHIGC
    后序序列:DFEBIGHCA

    用程序构建这棵树,再验证上面序列写的对不对:
    序列
    到这,我们应该就懂二叉树的遍历了。

    上面为我们讲的是根据二叉树写遍历序列,那要是现在反过来,要根据二叉树的遍历序列构建二叉树又该如何做呢?

    不能恢复二叉树的情况?

    首先我们要知道恢复二叉树必须需要这三个序列中的其中两个组成一组,这一组的两个序列不能同时为前序和后序,也就是说,只有两种恢复方法:前序和中序,中序和后序。把上面的树先拿下来再看看:
    树

    为什么不能用一个呢?
    既然是默认访问先后右,那么只拿一个序列,比如先序序列:ABDEFCHGI。我完全可以恢复成为下面这两棵树:
    lrleft树和right树的先序序列一样且和原本的数先序序列一样,这就离谱了,让你恢复树不是让你创造出新的树,创造的结果还不唯一。同理,其他两个序列用一个也不能恢复正确。因此,一种遍历序列不能恢复出正确的二叉树。

    再说先序和后序,就举一个简单的例子:
    先序:ABCD
    后序:DCBA
    可以恢复成下面两个树:
    在这里插入图片描述
    结果不唯一,自然就不是正确的树。所以先序和后序也恢复不出来正确的树。

    恢复正确的二叉树

    现在就剩下两种情况,可以正确恢复二叉树了:(先序序列,中序序列)、(中序序列,后序序列)

    先序和中序恢复

    定义两个指针:
    VLR:指向二叉树的先序序列
    LVR:指向二叉树的中序序列

    先序序列有一个现象:先出现的节点必然不可能是后出现的节点的孩子(要么兄弟,要么祖先),也就是说先出现的节点所处的层次不可能比后出现的节点所处的层次低。

    恢复二叉树没有父节点肯定不能恢复出孩子,那我们就从先序序列入手吗,看下图:
    11VLR指向先序序列的第0个元素A,我们用LVR在中序序列中也找到A,发现A的索引k=4,而且A将中序序列一分两半,左边有k个,右边有n-k-1个,将k=4拿过来,发现在先序序列中[1,k]的区间元素和中序序列中[0,k)元素一样,而且这个k的左右一分两半,两半元素一样,数目也一样,我们再看看原来的树,以k划分,两个序列左边都属于A的左子树,右边都属于A的右子树,左边都是k个元素,右边都是n-k-1个元素。
    在这里插入图片描述A的左右子树分出来了,创建A,
    A

    让左边元素去创建A的左子树,右边元素去创建A的右子树,如下图:我们先创左子树,还和上面的解释亦一样,以k划分,两个序列左边都属于B的左子树,右边都属于B的右子树,左边都是k个元素,右边都是n-k-1个元素。由此可见,问题是一样的entity,规模越来越小,这不就是递归嘛。

    BB的左右子树分出来了,创建B。
    b
    让左边元素去创建B的左子树,右边元素去创建B的右子树,我们先左子树,如下图:
    在这里插入图片描述此时LVR,VLR都指向D,索引都为0,此时也不存在C的左右子树了,创建D,下一步区去创建B的右子树
    D无需多言,虽然接下来是创建右子树,无非是继续重复一样的套路,当前序序列遍历完(递归出口),整个树就会创建成功。

    代码实现

    BinTree BinTreeCreat_VLR_LVR(const char* vlr,const char* lvr, int n)
    {
    	if (n == 0)//该子树没有数据,说明是叶节点的孩子(不存在),所以直接返回
    		return NULL;
    	int k = 0;
    	while (lvr[k] != vlr[0]) //在中序中寻找与前序一样的数据
    		k++;
    	BTNode* t = (BTNode*)malloc(sizeof(BTNode));//父节点创建
    	assert(t != NULL);
    	t->data = lvr[k];//父节点数据放入
    	t->left = BinTreeCreat_VLR_LVR(vlr + 1, lvr, k);//创建左子树
    	t->right = BinTreeCreat_VLR_LVR(vlr + k + 1, lvr + k + 1, n - k - 1);//创建右子树
    	return t;
    }
    

    中序和后序恢复

    基本思路没什么区别,只不过是把前序序列换为后序序列,让后序序列由后往前走即可
    h

    代码实现

    BinTree BinTreeCreat_LVR_LRV(const char* lvr,const char* lrv, int n)
    {
    	if (n == 0)
    		return NULL;
    	int k = 0;
    	while (lvr[k] != lrv[n-1])
    		k++;
    	BTNode* t = (BTNode*)malloc(sizeof(BTNode));
    	assert(t != NULL);
    	t->data = lvr[k];
    	t->right = BinTreeCreat_LVR_LRV(lvr + k + 1, lrv + k, n - k - 1);
    	t->left = BinTreeCreat_LVR_LRV(lvr, lrv, k);
    	return t;
    }
    

    二叉树的代码实现(基本操作)

    有几个函数涉及到队列和栈,因此包含有堆和栈的头文件

    #ifndef __BINTREE_H__
    #define __BINTREE_H__
    #include "Sysutil.h"
    #include "Queue.h"
    #include "LinkStack.h"
    
    typedef char DataType;
    
    typedef struct BTNode
    {
    	DataType data;
    	struct BTNode* left;
    	struct BTNode* right;
    }BTNode;
    typedef BTNode* BinTree;
    
    void BinTreeCreat(BinTree* bt);//创建方法1
    BinTree BinTreeCreat_1(const char* str, int* i);//创建方法2
    BinTree BinTreeCreat_2();//创建方法3
    void PreOrder(BinTree bt);//递归先序遍历
    void InOrder(BinTree bt);//递归中序遍历
    void PostOrder(BinTree bt);//递归后序遍历
    size_t Height(BinTree bt);//树深
    BTNode* Find(BinTree bt, DataType key);//查找
    BinTree Clone(BinTree bt);//树克隆
    BTNode* Parent(BinTree bt, BTNode* key);//父节点查找
    bool Euqal(BinTree bt1, BinTree bt2);//树同异比较
    void LevelOrder(BinTree bt);//层次遍历
    void PreOrderStack(BinTree bt);//非递归先序遍历
    void InOrderStack(BinTree bt);//非递归中序遍历
    void PostOrderStack(BinTree bt);//非递归后序遍历
    BinTree BinTreeCreat_VLR_LVR(const char* vlr, const char* lvr, int n);//前序和中序恢复树
    BinTree BinTreeCreat_LVR_LRV(const char* lvr, const char* lrv, int n);//中序和后序恢复树
    int BinTreeSize(BTNode* root);//树的节点数目
    int BinTreeLeafSize(BTNode* root);//树的叶子数目
    int BinTreeComplete(BTNode* root);//树是完全树码?
    int BinTreeLevelKSize(BTNode* root, int k);//树的第K层节点数目
    
    void BinTreeCreat(BinTree* bt)
    {
    	DataType item;
    	scanf("%c", &item);
    	if ('#' == item)
    		*bt = NULL;
    	else {
    		*bt = (BTNode*)malloc(sizeof(BTNode));
    		if (*bt) {
    			(*bt)->data = item;
    			BinTreeCreat(&((*bt)->left));
    			BinTreeCreat(&((*bt)->right));
    		}
    	}
    }
    BinTree BinTreeCreat_1( const char* str,int *i)
    {
    	if (str[*i] == '#' || str[*i] == '\0')
    		return NULL;
    	else {
    		BTNode* p = (BTNode*)malloc(sizeof(BTNode));
    		if (p) {
    			p->data = str[*i];
    			(*i)++;
    			p->left = BinTreeCreat_1(str, i);
    			(*i)++;
    			p->right = BinTreeCreat_1(str, i);
    			return p;
    		}
    	}
    }
    BinTree BinTreeCreat_2()
    {
    	DataType item;
    	scanf("%c", &item);
    	if ('#' == item)
    		return  NULL;
    	else {
    		BTNode *bt = (BTNode*)malloc(sizeof(BTNode));
    		if (bt) {
    			bt->data = item;
    			bt->left = BinTreeCreat_2();
    			bt->right = BinTreeCreat_2();
    			return bt;
    		}
    	}
    }
    void PreOrder(BinTree bt)
    {//先序输出
    	if (bt) {
    		printf("%c ",bt->data);
    		PreOrder(bt->left);
    		PreOrder(bt->right);
    	}
    }
    void InOrder(BinTree bt)
    {
    	if (bt) {
    		InOrder(bt->left);
    		printf("%c ",bt->data);
    		InOrder(bt->right);
    	}
    }
    void PostOrder(BinTree bt)
    {
    	if (bt) {
    		PostOrder(bt->left);
    		PostOrder(bt->right);
    		printf("%c ", bt->data);
    	}
    }
    size_t Height(BinTree bt)
    {
    	if (!bt)
    		return 0;
    	else {
    		int h_left = Height(bt->left) + 1;
    		int h_right = Height(bt->right) + 1;
    		return h_left > h_right ? h_left : h_right;//谁深返回谁
    	}
    }
    BTNode* Find(BinTree bt,DataType key)
    {
    	if (bt == NULL || bt->data == key)//找到
    		return bt;
    	BTNode* p = Find(bt->left, key);
    	if (p)//左树存在
    		return p;
    	return Find(bt->right,key);
    }
    BTNode* Parent(BinTree bt, BTNode* key)
    {
    	if (!bt||bt==key)//空树||根节点
    		return NULL;
    	if (bt->left == key || bt->right == key)//左||右孩子就是key
    		return bt;
    	BTNode* p = Parent(bt->left,key);//都不是,向深度前进
    	if (p)//在左树找到
    		return p;
    	return Parent(bt->right,key);//在右树找
    }
    BinTree Clone(BinTree bt)
    {
    	if (NULL == bt)//空树
    		return bt;
    	else{
    		BTNode* new_t = (BTNode*)malloc(sizeof(BTNode));
    		if (NULL != new_t) {
    			new_t->data = bt->data;//节点数据
    			new_t->left = Clone(bt->left);//左树复制
    			new_t->right = Clone(bt->right);//右树复制
    		}
    	}
    }
    bool Euqal(BinTree bt1, BinTree bt2)
    {
    	if (bt1 == bt2 && !bt1)//两个都是空树
    		return true;
    	if (!bt1 || !bt2)//一个NULL,另一个非NULL
    		return false;
    	return (bt1->data == bt2->data) && Euqal(bt1->left, bt2->left) && Euqal(bt1->right, bt2->right);//值相同&&左树相等&&右树相等
    }
    void LevelOrder(BinTree bt)
    {//层次遍历
    	if (NULL != bt) {
    		Queue Q;
    		QueueInit(&Q);
    		QueuePush(&Q, bt);//根节点入队
    		while (!QueueEmpty(&Q)) {//队列非空
    			BTNode* p = QueueFront(&Q);//获取队头元素
    			QueuePop(&Q);//出队
    			printf("%c ",p->data);
    			if (p->left)//左树遍历
    				QueuePush(&Q, p->left);
    			if (p->right)//右树遍历
    				QueuePush(&Q, p->right);
    		}
    	}
    }
    void PreOrderStack(BinTree bt)
    {	//先序遍历,非递归
    	if (NULL != bt) {
    		LinkStack stack;
    		LinkStackInit(&stack);
    		LinkStackPush(&stack,bt);
    		while (!LinkStackEmpty(&stack)) {
    			BTNode* p = LinkStackTop(&stack);
    			LinkStackPop(&stack);
    			printf("%c ",p->data);
    			if (p->right)
    				LinkStackPush(&stack, p->right);
    			if (p->left)
    				LinkStackPush(&stack, p->left);
    		}
    	}
    }
    void InOrderStack(BinTree bt)
    {	//中序遍历,非递归
    	if (NULL != bt) {
    		LinkStack stack;
    		LinkStackInit(&stack);
    		BTNode* p = bt;
    		while (!LinkStackEmpty(&stack) || p){//栈未空||树不空
    			while (p) {//p存在节点,压栈
    				LinkStackPush(&stack, p);
    				p = p->left;
    			}
    			p = LinkStackTop(&stack);
    			LinkStackPop(&stack); //出栈
    			printf("%c ", p->data);
    			p = p->right;//进入右树
    		}
    	}
    }
    void PostOrderStack(BinTree bt)
    {
    	//后序遍历,非递归
    	if (NULL != bt) {
    		LinkStack stack;
    		LinkStackInit(&stack);
    		BTNode* p, * pre = NULL;
    		while (!LinkStackEmpty(&stack) || bt) {//栈未空||树不空
    			while (bt) {//p存在节点,压栈
    				LinkStackPush(&stack, bt);
    				bt = bt->left;
    			}
    			p = LinkStackTop(&stack);
    			if (p->right == NULL || p->right == pre) {
    				printf("%c ", p->data);
    				LinkStackPop(&stack); //出栈
    				pre = p;//前驱更新
    			}
    			else
    				bt = p->right;//进入右树
    		}
    	}
    }
    BinTree BinTreeCreat_VLR_LVR(const char* vlr,const char* lvr, int n)
    {
    	if (n == 0)//该子树没有数据,说明是叶节点的孩子(不存在),所以直接返回
    		return NULL;
    	int k = 0;
    	while (lvr[k] != vlr[0]) //在中序中寻找与前序一样的数据
    		k++;
    	BTNode* t = (BTNode*)malloc(sizeof(BTNode));//父节点创建
    	assert(t != NULL);
    	t->data = lvr[k];//父节点数据放入
    	t->left = BinTreeCreat_VLR_LVR(vlr + 1, lvr, k);//创建左子树
    	t->right = BinTreeCreat_VLR_LVR(vlr + k + 1, lvr + k + 1, n - k - 1);//创建右子树
    	return t;
    }
    BinTree BinTreeCreat_LVR_LRV(const char* lvr,const char* lrv, int n)
    {
    	if (n == 0)
    		return NULL;
    	int k = 0;
    	while (lvr[k] != lrv[n-1])
    		k++;
    	BTNode* t = (BTNode*)malloc(sizeof(BTNode));
    	assert(t != NULL);
    	t->data = lvr[k];
    	t->right = BinTreeCreat_LVR_LRV(lvr + k + 1, lrv + k, n - k - 1);
    	t->left = BinTreeCreat_LVR_LRV(lvr, lrv, k);
    	return t;
    }
    void BinTreeDestory(BinTree* bt)
    {
    	if(*bt){
    		BinTreeDestory(&((*bt)->left));
    		BinTreeDestory(&((*bt)->right));
    		free(*bt);
    		*bt = NULL;
    	}
    }
    int BinTreeSize(BTNode* root)
    {
    	if (NULL == root)
    		return 0;
    	return BinTreeSize(root->left) + BinTreeSize(root->right) + 1;
    }
    int BinTreeLeafSize(BTNode* root)
    {
    	if (NULL == root)
    		return 0;
    	if (NULL == root->left && NULL == root->right)
    		return 1;
    	return BinTreeLeafSize(root->left) + BinTreeLeafSize(root->right);
    }
    int BinTreeComplete(BTNode* root)
    {	//0表示不是
    	if (NULL == root)
    		return 1;
    	if (root->right && NULL == root->left)
    		return 0;
    	return BinTreeComplete(root->left) && BinTreeComplete(root->right);
    }
    int BinTreeLevelKSize(BTNode* root, int k)
    {//根节点视为第一层
    	if (NULL == root || k <= 0)
    		return 0;
    	if (1 == k)
    		return 1;
    	return BinTreeLevelKSize(root->left, k - 1) + BinTreeLevelKSize(root->right, k - 1);
    }
    #endif 
    
    展开全文
  • 遍历序列得到二叉树

    千次阅读 2009-03-08 21:31:00
    由前序遍历序列和中序遍历序列或者中序遍历序列和后序遍历序列可以得到二叉树。由前序遍历序列和后序遍历序列不一定能得到确定的二叉树。例:前序遍历序列:AB后序遍历序列:BA就无法确定B是A的左孩子还是右孩子。经...

    由遍历序列得到二叉树

    ——这里讨论的只是在纸上逻辑图形的推导,不涉及

    计算机上的算法。适用于解决考卷上的问题。

    由两种遍历序列可得到二叉树,其实是不完全正确的。由前序遍历序列和中序遍历序列或者中序遍历序列和后序遍历序列可以得到二叉树。由前序遍历序列和后序遍历序列不一定能得到确定的二叉树。

    例:

    前序遍历序列:AB

    后序遍历序列:BA

    就无法确定BA的左孩子还是右孩子。

    经研究后发现,如果二叉树含有度(孩子数)为一的节点,那么由它的前序遍历序列和后序遍历序列就不能确定该二叉树。但如果知道所求的二叉树是完全二叉树(没有度为一的节点),则可以确定二叉树。

     

    由前序遍历序列和中序遍历序列得到二叉树:

    比如二叉树有七个节点(包括根)

    1建立7*8的表格,将中序遍历序列写在最上一行。

    2然后前序遍历序列的顺序将该节点写在2-8行(节点与中序序列在同一列)。

    3然后从上到下连接,将某节点与该节点以下最高的左节点和最高右节点连接。

    即得到二叉树。

    例:

    前序遍历序列:ABDECFG

    中序遍历序列:DBEAFCG

    D

    B

    E

    A

    F

    C

    G

     

     

     

    A

     

     

     

     

    B

     

     

     

     

     

    D

     

     

     

     

     

     

     

     

    E

     

     

     

     

     

     

     

     

     

    C

     

     

     

     

     

    F

     

     

     

     

     

     

     

     

    G

     

     

     

     

    A

     

     

     

     

    B

     

     

     

     

     

    D

     

     

     

     

     

     

     

     

    E

     

     

     

     

     

     

     

     

     

    C

     

     

     

     

     

    F

     

     

     

     

     

     

     

     

    G

     

    由后序遍历序列和中序遍历序列得到二叉树:

    1与(前序和中序1)相同。

    2将后序遍历序列,按从后向前的顺序填表。

    3同(前序和中序3)。

     

    二叉树是满二叉树,由前序遍历序列和后序遍历序列得到二叉树:

    比如二叉树有七个节点(包括根)

    1建立7*8的表格,将后序遍历序列(前序遍历序列)写在最上一行。

    2将前序遍历序列(后序遍历序列),按从前向后的顺序(从后向前的顺序)填表。注意:新加节点不能在任一已加节点的左下对角线(右下对角线)上,否则加一空列。

    3将表格逆时针(顺时针)旋转45°。

    4同(前序和中序3)。

    得到二叉树。

    例:

    前序遍历序列:ABDECFG

    后序遍历序列:DEBFGCA

    D

    E

    B

    F

    G

    C

    A

     

     

     

     

     

     

    A

     

     

    B

     

     

     

     

    D

     

     

     

     

     

     

     

    E

     

     

     

     

     

     

     

     

     

     

    C

     

     

     

     

    F

     

     

     

     

     

     

     

    G

     

     

     

     

    若有错误之处,欢迎大家指正。

    展开全文
  • 的深度优先遍历序列

    千次阅读 2013-12-16 23:08:51
    设V={0,1,2,……,n-1},图中的结点又称为顶点(vertex),有向图(directed graph)指图中代表边的偶对是有序的,用代表一条有向边(又称为弧),则u称为该边的始点(尾),v称为边的终点(头)。无向图(undirected g

    题目:

    描述

    图(graph)是数据结构 G=(V,E),其中V是G中结点的有限非空集合,结点的偶对称为边(edge);E是G中边的有限集合。设V={0,1,2,……,n-1},图中的结点又称为顶点(vertex),有向图(directed graph)指图中代表边的偶对是有序的,用<u,v>代表一条有向边(又称为弧),则u称为该边的始点(尾),v称为边的终点(头)。无向图(undirected graph)指图中代表边的偶对是无序的,在无向图中边(u,v )和(v,u)是同一条边。

    输入边构成无向图,求以顶点0为起点的深度优先遍历序列。

    输入

    第一行为两个整数ne,表示图顶点数和边数。以下e行每行两个整数,表示一条边的起点、终点,保证不重复、不失败。1n20,0e190

    输出

    前面n行输出无向图的邻接矩阵,最后一行输出以顶点0为起点的深度优先遍历序列,对于任一起点,首先遍历的是终点序号最小的、尚未被访问的一条边。每个序号后输出一个空格。

    样例输入

    4 5
    0 1
    0 3
    1 2
    1 3
    2 3

    样例输出

    0 1 0 1 
    1 0 1 1 
    0 1 0 1 
    1 1 1 0 
    0 1 2 3 



    代码:

    #include <iostream>
    #include <cstring>
    using namespace std;
    
    class Graph
    {
    private:
    	int **a, n, e;//n点,e边
    public:
    	Graph(int num, int edge);
    	~Graph();
    	void insert();//插入图的节点
    	bool exist(int u, int v);//是否存在(u,v)
    	void output();
    	void DFS();//深度优先
    	void DFS(int v, bool *used);
    };
    
    int main()
    {
    	int n, m;//n点,m边
    
    	cin >> n >> m;
    	Graph graph(n, m);
    	graph.insert();
    	graph.output();
    	graph.DFS();
    	return 0;
    }
    
    Graph::Graph(int num, int edge)
    {
    	n = num, e = edge;
    	a = new int*[n];
    	for(int i = 0; i < n; i++)
    	{
    		a[i] = new int[n];
    		memset(a[i], 0, n*sizeof(int));
    	}
    }
    
    Graph::~Graph()
    {
    	for(int i = 0; i < n; i++)
    	{
    		delete []a[i];
    	}
    	delete []a;
    }
    
    void Graph::insert()
    {
    	int na, nb;
    	for(int i = 0; i < e; i++)
    	{
    		cin >> na >> nb;
    		a[na][nb] = 1;
    		a[nb][na] = 1;
    	}
    }
    
    bool Graph::exist(int u, int v)
    {
    	if(a[u][v]) return true;
    	return false;
    }
    
    void Graph::DFS()
    {
    	bool *used = new bool[n];
    	int i;
    	for(i = 0; i < n; i++)
    	{
    		used[i] = false;
    	}
    	for(i = 0; i < n; i++)
    	{
    		if(!used[i]) DFS(i, used);
    	}
    	cout << endl;
    	delete []used;
    }
    
    void Graph::DFS(int v, bool *used)
    {
    	used[v] = true;
    	cout<< v << " " ;
    	for(int i = 0; i < n; i++)
    	{
    		if(!used[i] && a[v][i])
    		{
    			DFS(i, used);
    		}
    	}
    }
    
    void Graph::output()
    {
    	for(int i = 0; i < n; i++)
    	{
    		for(int j = 0; j < n; j++)
    		{
    			cout << a[i][j] << " ";
    		}
    		cout << endl;
    	}
    }


    展开全文
  • 的宽度优先遍历序列

    千次阅读 2013-12-16 23:11:12
    设V={0,1,2,……,n-1},图中的结点又称为顶点(vertex),有向图(directed graph)指图中代表边的偶对是有序的,用,v>代表一条有向边(又称为弧),则u称为该边的始点(尾),v称为边的终点(头)。无向图(undir
  • 的宽度优先遍历序列 Time Limit(Common/Java):1000MS/3000MS Memory Limit:65536KByte Total Submit:488 Accepted:216 Description (graph)是数据结构 G=(V,E),其中V是G中结点的有限非空集合,结点的偶...
  • 的深度优先遍历序列 Time Limit(Common/Java):1000MS/3000MS Memory Limit:65536KByte Total Submit:899 Accepted:275 Description (graph)是数据结构 G=(V,E),其中V是G中结点的有限非空集合,结点的偶...
  • 的深度优先遍历序列 时间限制(普通/Java) : 1000 MS/ 3000 MS 运行内存限制 : 65536 KByte 总提交 : 1186 测试通过 : 358  比赛描述 (graph)是数据结构 G=(V,E),其中V是G中结点的有限非空集合,...
  • 的宽度优先遍历序列 时间限制(普通/Java) : 1000 MS/ 3000 MS 运行内存限制 : 65536 KByte 总提交 : 633 测试通过 : 282  比赛描述 (graph)是数据结构 G=(V,E),其中V是G中结点的有限非空集合,...
  • 求连通的所有深度优先遍历序列

    千次阅读 2019-02-28 09:52:13
    如果 G 是有向图,那么连接vi和vj的路径中所有的边都必须同向。如果图中任意两点都是连通的,那么图被称作连通图。如果此图是有向图,则称为强连通图(注意:需要双向都有路径)。图的连通性是图的基本性质。 ...
  • leetcode 第105题(从前序与中序遍历序列构造二叉树) ,第106题(从中序与后序遍历序列构造二叉树)python解法(用时40ms) 先从105题开始: 第105题是利用前序和中序恢复二叉树,主要还是应用递归的思想。 首先看...
  • 设V={0,1,2,……,n-1},图中的结点又称为顶点(vertex),有向图(directed graph)指图中代表边的偶对是有序的,用<u,v>代表一条有向边(又称为弧),则u称为该边的始点(尾),v称为边的终点(头)。无向图...
  • 【0】README0.1) 本文总结于 数据结构与算法分析, 源代码均为原创, 旨在 理解 “DFS应用——遍历有向图+判断有向图是否有圈” 的idea 并用源代码加以实现 ; 0.2) 判断有向图是否有圈的rule—— 一个有向图是无...
  • 的深度优先遍历序列 时间限制(普通/Java) :1000 MS/ 3000 MS 运行内存限制 : 65536 KByte 总提交 : 1083 测试通过 : 327 题目描述 (graph)是数据结构 G=(V,E),其中V是G中结点的有限非空集合,结点的偶对...
  • 有向图的深度和广度遍历

    万次阅读 2018-05-04 09:33:26
    对于下图所示的有向图(访问顺序按序号从小到大),试写出: (1) 从顶点①出发进行深度优先搜索所得到的深度优先生成树;(2) 从顶点②出发进行广度优先搜索所得到的广度优先生成树。 package com.test.tree; ...
  • 有向图遍历(深度遍历和广度遍历)

    千次阅读 2019-01-23 16:05:15
    typedef struct _BinaryTreeNode { char data; //int ltag , rtag; struct _BinaryTreeNode *lchild; struct _BinaryTreeNode *rchild;.../创建邻接矩阵 假定这里是有向图 void createMGraph(AGraph *a) { //...
  • 利用前序遍历序列化二叉树时,遇到非空结点时,记录结点的值;如果是空节点,用#记录。 给定一个逗号分隔的字符串,判断它是否是二叉树的前序遍历序列化。不需重建二叉树 例子 Example 1: Input: "9,3,4,#,#,1,#,#...
  • // // main.cpp // Grpah_DFS_BFS // // Created by duanqibo on 2019/7/3. // Copyright © 2019年 duanqibo....// 无向图和有向图的深度遍历和广度遍历 #include <iostream> #include &l...
  • 请定一个无向图,顶点编号从0到n-1,用深度优先搜索(DFS),遍历并输出。遍历时,先遍历节点编号小的。 输入 输入第一行为整数n(0 < n < 100),表示数据的组数。 对于每组数据,第一行是两个整数k,m(0 ,0...
  • ①无向图的非递归深度优先搜索需借用一个堆栈保存被访问过的顶点,以便回溯查找已被访问结点的被访问过的邻接点。 ②访问起始顶点v0,visited[v0]标记1,v0入栈,指针p指向v0对应的边表首结点; ③从左到右扫描p所指的...
  • 1. 输入一个有向图的顶点数 n 和边数 e,设图中顶点编号为 1 到 n, 1)依次输入每个边的起点和终点,创建该图的邻接表; 2)边链表中边结点编号按照从小到大的顺序存储。 2. 实现图的深度优先遍历和广度优先遍历...
  • 从键盘接收有向图的顶点集,弧集,创建有向图,并完成下列任务: (1)计算结点的出度、入度以及度; (2) 从第一个顶点出发,求一个深度优先遍历序列; (3) 从第一个顶点顶点出发,求一个广度优先遍历序列。 注意:以...
  • 在前面的文章中,我已经讨论了无向图的遍历,现在发现在有向图中,可能会发生无法遍历到所有节点的情况。因此在经历一次深度优先搜索遍历后,如果还存在未被搜索到的节点,则需要再从新的节点开始进行深度优先搜索...
  • 剑指offer-23:二叉搜索树的后序遍历序列 目录 剑指offer-23二叉搜索树的后序遍历序列 目录 1问题描述 2二叉树遍历 3问题解析 4问题答案 1问题描述 输入一个整数数组,判断该数组是不是某二叉搜索树...
  • /*(1)输入一组顶点,建立...(2)根据建立的有向图,判断该图是否是有向无环图,若是,则输出其一种拓扑有序序列。*/ #include #include #define max 20 #define SIZE 20 #define MORE 10 typedef struct ArcNode{

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 86,355
精华内容 34,542
关键字:

有向图的遍历序列