数据结构 图G的广度、深度优先生成树分别怎么画呀？，广度优先生成树怎么画

123

数据结构 图G的广度、深度优先生成树分别怎么画呀？


1、首先第一步若节点右左子树，则左链域lchild指示其左孩子（ltag=0）,否则，令左链域指示其前驱（ltag=1）。若结点有右子树，则右链域rchild指示其右孩子（rtag=0）,否则，令右链域指示其后继（rtag=1）。

2、然后击亅实现这一过程，设指针p指向当前结点，pre始终指向刚刚访问过的结点，即p的前驱，以便于修改pre的后继线索和p的前驱线索。在线索化算法中访问当前结点p来进行处理。

3、最后几是结点p的左指针域为空，则将其标志位置为1，并使p->lchild指向中序前驱结点pre（即左线索化）；结点pre的右指针域为空，则将其标志位置为1，并使pre->rchild指向中序后继结点p（即右线索化）；将pre指向刚刚访问过的结点p（即pre=p），线索化p的右子树。

扩展资料：
设G=(V,E)是一个图，其中V={v1,v2,…,vn}。G的邻接矩阵是一个具有下列性质的n阶方阵：
对无向图而言，邻接矩阵一定是对称的，而且主对角线一定为零（在此仅讨论无向简单图），副对角线不一定为0，有向图则不一定如此。
在无向图中，任一顶点i的度为第i列（或第i行）所有非零元素的个数，在有向图中顶点i的出度为第i行所有非零元素的个数，而入度为第i列所有非零元素的个数。






请大神详细讲解一下广度优先生成树的构造过程。所构造的生成树唯一吗？
请大神详细讲解一下广度优先生成树的构造过程。所构造的生成树唯一吗？以2为根构造广度优先生成树



广度优先就是从起点出发，每一轮遍历距离起点位置等距离的节点，以这题为例，从2出发，6和1距离2的距离都是1，所以他们是2的子树，同理，接下来第二轮的起点就是6和1,3和7距离6的距离都是1所以是6的子树，以此类推，直到所有的节点都遍历到。
生成树协议工作原理：任意一交换机中如果到达根网桥有两条或者两条以上的链路。生成树协议都根据算法把其中一条切断，仅保留一条。从而保证任意两个交换机之间只有一条单一的活动链路，因为这种生成的这种拓扑结构，很像是以根交换机为树干的树形结构，故为生成树协议。


扩展资料：
生成树协议的主要功能有两个：一是在利用生成树算法、在以太网络中，创建一个以某台交换机的某个端口为根的生成树，避免环路。二是在以太网络拓扑发生变化时，通过生成树协议达到收敛保护的目的。
生成树协议提供一种控制环路的方法。采用这种方法，在连接发生问题的时候，你控制的以太网能够绕过出现故障的连接。生成树中的根桥是一个逻辑的中心，并且监视整个网络的通信。最好不要依靠设备的自动选择去挑选哪一个网桥会成为根桥。
生成树协议重新计算是繁冗的。恰当地设置主机连接端口(这样就不会引起重新计算)，推荐使用快速生成树协议。

设G=(V,E)以邻接表储存,如图所示,试画出从顶点1出发所得到的深度优先生成树


深度优先生成树
1-2-3-4-5
广度优先生成树
      1
      /|\
    /  |  \
  2  3   4
  |
5