图的遍历生成树(深度遍历和广度遍历)

article/2025/10/3 11:23:28

基本思想

  1. 深度优先遍历生成森林
    1）遍历无向图的各顶点，将其作为一个初始点，建立深度优先生成树
    2）在建树函数DFSTree()中，设置标识，将第一个结点设置为根节点的左孩子，其余结点作为左孩子的兄弟，具体见DFSTree()函数
    3）在生成森林函数DFSForest()中，如果仍然存在未访问节点，则说明是非连通图将该结点接入到根节点的兄弟结点上，继续深度优先建立生成树，具体见DFSForest()函数
    4）前序遍历生成树，用来检验结果
  2. 广度优先遍历生成森林
    1）利用队列来存储树的结点
    2）循环遍历图的每个顶点，以该顶点作为根节点进行广度优先遍历，若还有未访问的结点，则继续
    运行，将该结点作为树的根节点的兄弟结点，转移指针，然后该结点继续广度优先遍历，具体见BFSTree()
    3）在生成森林函数BFSForest()函数中，建立队列并初始化，将生成树的根节点入队。从队列中取出一个结点，循环遍历该节点的邻接结点，如果存在未访问的邻接结点，入队，标记为已访问，同时建立生成树，将fisrt == True的结点作为左孩子，其余为兄弟结点

数据表示

数据

13,13
1
2
3
4
5
6
7
8
9
10
11
12
13
1,2
1,3
1,6
1,12
2,13
4,5
7,8
7,10
7,9
8,10
11,12
11,13
12,13

深度优先遍历生成树

在这里插入图片描述

实现代码

/*深度优先遍历生成森林基本思想：1.遍历无向图的各顶点，将其作为一个初始点，建立深度优先生成树2. 在建树函数DFSTree()中，设置标识，将第一个结点设置为根节点的左孩子，其余结点作为左孩子的兄弟，具体见DFSTree()函数3. 在生成森林函数DFSForest()中，如果仍然存在未访问节点，则说明是非连通图将该结点接入到根节点的兄弟结点上，继续深度优先建立生成树，具体见DFSForest()函数4. 前序遍历生成树，用来检验结果
*/
#include <stdio.h>
#include <stdlib.h>#define MAX_VERtEX_NUM 20                   //顶点的最大个数
#define VRType int                          //表示顶点之间的关系的变量类型
#define VertexType int                     //图中顶点的数据类型
typedef enum{False,True}Bool;               //定义bool型常量
bool visited[MAX_VERtEX_NUM];               //设置全局数组，记录标记顶点是否被访问过typedef struct {VRType adj;                             //对于无权图，用 1 或 0 表示是否相邻；对于带权图，直接为权值。
}ArcCell,AdjMatrix[MAX_VERtEX_NUM][MAX_VERtEX_NUM];typedef struct {VertexType vexs[MAX_VERtEX_NUM];        //存储图中顶点数据AdjMatrix arcs;                         //二维数组，记录顶点之间的关系int vexnum,arcnum;                      //记录图的顶点数和弧（边）数
}MGraph;
//孩子兄弟表示法的链表结点结构
typedef struct CSNode{VertexType data;struct CSNode * lchild;//孩子结点struct CSNode * nextsibling;//兄弟结点
}*CSTree,CSNode;//根据顶点本身数据，判断出顶点在二维数组中的位置
int LocateVex(MGraph G,VertexType v){int i=0;//遍历一维数组，找到变量vfor (; i < G.vexnum; i++) {if (G.vexs[i] == v) {break;}}//如果找不到，输出提示语句，返回-1if (i > G.vexnum) {printf("no such vertex.\n");return -1;}return i;
}//构造无向图
void CreateDN(MGraph *G){FILE *fp;fp = fopen("data.txt", "r");fscanf(fp, "%d,%d", &(G->vexnum), &(G->arcnum));//各个点的序号for (int i=0; i < G->vexnum; i++) {fscanf(fp, "%d",&(G->vexs[i]));}//邻接矩阵进行初始化for (int i=0; i < G->vexnum; i++) {for (int j=0; j < G->vexnum; j++) {G->arcs[i][j].adj=0;}}//连接各点，为邻接矩阵赋初值for (int i=0; i < G->arcnum; i++) {int v1,v2;fscanf(fp, "%d,%d", &v1, &v2);int n=LocateVex(*G, v1);int m=LocateVex(*G, v2);if (m==-1 ||n==-1) {printf("no this vertex\n");return;}G->arcs[n][m].adj=1;G->arcs[m][n].adj=1;//无向图的二阶矩阵沿主对角线对称}fclose(fp);
}//找到第一个邻接点
int FirstAdjVex(MGraph G,int v)
{//查找与数组下标为v的顶点之间有边的顶点，返回它在数组中的下标for(int i = 0; i < G.vexnum; i++){if( G.arcs[v][i].adj ){return i;}}return -1;
}//找到下一个邻接点
int NextAdjVex(MGraph G,int v,int w)
{//从前一个访问位置w的下一个位置开始，查找之间有边的顶点for(int i = w + 1; i < G.vexnum; i++){if(G.arcs[v][i].adj){return i;}}return -1;
}void DFSTree(MGraph G,int v,CSTree *T){//将正在访问的该顶点的标志位设为Truevisited[v] = True;bool first = True;CSTree q = NULL;//依次遍历该顶点的所有邻接点for (int w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w)) {//如果该临界点标志位为False，说明还未访问if (!visited[w]) {//为该邻接点初始化为结点CSTree p = (CSTree)malloc(sizeof(CSNode));p->data = G.vexs[w];p->lchild=NULL;p->nextsibling=NULL;//该结点的第一个邻接点作为孩子结点，其它邻接点作为孩子结点的兄弟结点if (first) {(*T)->lchild = p;first = False;}//否则，为兄弟结点else{q->nextsibling = p;}q = p;//以当前访问的顶点为树根，继续访问其邻接点DFSTree(G, w, &q);}//if (!visited[w])}//for
}//深度优先搜索生成森林并转化为二叉树
void DFSForest(MGraph G, CSTree *T){(*T)=NULL;//每个顶点的标记为初始化为Falsefor (int v = 0; v < G.vexnum; v++) {visited[v] = False;}CSTree q = NULL;//遍历每个顶点作为初始点，建立深度优先生成树for (int v = 0; v < G.vexnum; v++) {//如果该顶点的标记位为False，证明未访问过if (!(visited[v])) {//新建一个结点，表示该顶点CSTree p = (CSTree)malloc(sizeof(CSNode));p->data = G.vexs[v];p->lchild = NULL;p->nextsibling=NULL;//如果当前树为空，则该顶点作为树的树根if (!(*T)) {(*T) = p;}//该顶点作为树根的兄弟结点else{q->nextsibling=p;}//每次都要把q指针指向新的结点，为下次添加结点做铺垫q = p;//以该结点为起始点，构建深度优先生成树DFSTree(G, v, &p);}//if (!(visited[v]))}
}//前序遍历二叉树
void PreOrderTraverse(CSTree T){if (T) {printf("%d ",T->data);PreOrderTraverse(T->lchild);PreOrderTraverse(T->nextsibling);}return;
}int main() {MGraph G;//建立一个图的变量CreateDN(&G);//初始化图CSTree T;						//建立一棵树DFSForest(G, &T);PreOrderTraverse(T);			//前序遍历生成树	用来检验getchar();return 0;
}

广度优先遍历生成树

在这里插入图片描述

实现代码

/*广度遍历生成森林基本思想：1.利用队列来存储树的结点2. 循环遍历图的每个顶点，以该顶点作为根节点进行广度优先遍历，若还有未访问的结点，则继续运行，将该结点作为树的根节点的兄弟结点，转移指针，然后该结点继续广度优先遍历，具体见BFSTree()3. 在生成森林函数BFSForest()函数中，建立队列并初始化，将生成树的根节点入队。从队列中取出一个结点，循环遍历该节点的邻接结点，如果存在未访问的邻接结点，入队，标记为已访问，同时建立生成树，将fisrt == True的结点作为左孩子，其余为兄弟结点
*/#include<stdio.h>
#include<stdlib.h>#define MAX_VERtEX_NUM 20                   //顶点的最大个数
#define VRType int                          //表示顶点之间的关系的变量类型
#define VertexType int                     //图中顶点的数据类型
typedef enum{False,True}Bool;               //定义bool型常量
bool visited[MAX_VERtEX_NUM];               //设置全局数组，记录标记顶点是否被访问过typedef struct {VRType adj;                             //对于无权图，用 1 或 0 表示是否相邻；对于带权图，直接为权值。
}ArcCell,AdjMatrix[MAX_VERtEX_NUM][MAX_VERtEX_NUM];typedef struct {VertexType vexs[MAX_VERtEX_NUM];        //存储图中顶点数据AdjMatrix arcs;                         //二维数组，记录顶点之间的关系int vexnum,arcnum;                      //记录图的顶点数和弧（边）数
}MGraph;
//孩子兄弟表示法的链表结点结构
typedef struct CSNode{VertexType data;struct CSNode * lchild;//孩子结点struct CSNode * nextsibling;//兄弟结点
}*CSTree,CSNode;typedef struct Que{CSTree data;		//队列中存放的是树结点struct Que *next;
}Que;//根据顶点本身数据，判断出顶点在二维数组中的位置
int LocateVex(MGraph G,VertexType v){int i=0;//遍历一维数组，找到变量vfor (; i < G.vexnum; i++) {if (G.vexs[i] == v) {break;}}//如果找不到，输出提示语句，返回-1if (i > G.vexnum) {printf("no such vertex.\n");return -1;}return i;
}//找到第一个邻接点
int FirstAdjVex(MGraph G,int v)
{//查找与数组下标为v的顶点之间有边的顶点，返回它在数组中的下标for(int i = 0; i < G.vexnum; i++){if( G.arcs[v][i].adj ){return i;}}return -1;
}//找到下一个邻接点
int NextAdjVex(MGraph G,int v,int w)
{//从前一个访问位置w的下一个位置开始，查找之间有边的顶点for(int i = w + 1; i < G.vexnum; i++){if(G.arcs[v][i].adj){return i;}}return -1;
}//建立无向图
void CreateDN(MGraph *G)
{FILE *fp;fp = fopen("data.txt", "r");fscanf(fp, "%d,%d", &(G->vexnum), &(G->arcnum));//各个点的序号for (int i=0; i < G->vexnum; i++) {fscanf(fp, "%d",&(G->vexs[i]));}//邻接矩阵进行初始化for (int i=0; i < G->vexnum; i++) {for (int j=0; j < G->vexnum; j++) {G->arcs[i][j].adj=0;}}//连接各点，为邻接矩阵赋初值for (int i=0; i < G->arcnum; i++) {int v1,v2;fscanf(fp, "%d,%d", &v1, &v2);int n=LocateVex(*G, v1);int m=LocateVex(*G, v2);if (m==-1 ||n==-1) {printf("no this vertex\n");return;}G->arcs[n][m].adj=1;G->arcs[m][n].adj=1;//无向图的二阶矩阵沿主对角线对称}fclose(fp);
}//初始化队列
void InitQueue(Que **Q)
{(*Q) = (Que *)malloc(sizeof(Que));(*Q)->next = NULL;
}//结点v进队列
void EnQueue(Que **Q,CSTree T){Que * element=(Que*)malloc(sizeof(Que));element->data=T;element->next=NULL;Que * temp=(*Q);while (temp->next!=NULL) {temp = temp->next;}temp->next = element;
}
//队头元素出队列
void DeQueue(Que **Q,CSTree *U){(*U)=(*Q)->next->data;(*Q)->next = (*Q)->next->next;
}
//判断队列是否为空
bool QueueEmpty(Que *Q){if (Q->next==NULL) {return true;}return false;
}void BFSTree(MGraph G, int v, CSTree *T)
{CSTree q = NULL;Que *Q;InitQueue(&Q);EnQueue(&Q, (*T));//当队列为空时，证明遍历完成while (!QueueEmpty(Q)) {bool first = true;//队列首个结点出队DeQueue(&Q,&q);//判断结点中的数据在数组中的具体位置int v=LocateVex(G,q->data);//已经访问过的更改其标志位visited[v]=true;//遍历以出队结点为起始点的所有邻接点for (int w = FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v, w)) {//标志位为false，证明未遍历过if (!visited[w]) {//新建一个结点 p，存放当前遍历的顶点CSTree p=(CSTree)malloc(sizeof(CSNode));p->data=G.vexs[w];p->lchild=NULL;p->nextsibling=NULL;//当前结点入队EnQueue(&Q, p);//更改标志位visited[w]=true;//如果是出队顶点的第一个邻接点，设置p结点为其左孩子if (first) {q->lchild = p;first = false;}//否则设置其为兄弟结点else{q->nextsibling=p;}q=p;}}}
}void BFSForest(MGraph G, CSTree *T)
{(*T) = NULL;//每个顶点的标记初始化为falsefor(int v = 0;v < G.vexnum;v++)visited[v] = false;CSTree q = NULL;//遍历图中的所有的顶点for(int v = 0;v < G.vexnum;v++){//如果未被访问if(!visited[v]){	//新建一个结点CSTree p = (CSNode *)malloc(sizeof(CSNode));p->data = G.vexs[v];p->lchild = NULL;p->nextsibling = NULL;//如果树为空，则作为根节点if(!(*T))(*T) = p;elseq->nextsibling = p;q = p;BFSTree(G, v, &p);}}
}//前序遍历二叉树
void PreOrderTraverse(CSTree T){if (T) {printf("%d ",T->data);PreOrderTraverse(T->lchild);PreOrderTraverse(T->nextsibling);}return;
}int main()
{MGraph G;				//建立一个图的变量CreateDN(&G);			//初始化图CSTree T;				//建立一棵树BFSForest(G, &T);PreOrderTraverse(T);			//前序遍历生成树	用来检验getchar();return 0;
}

http://chatgpt.dhexx.cn/article/QI3NdGr6.shtml

相关文章

关于树的深度和高度的计算

关于树的深度和高度的计算

关于树的深度和高度的计算&#xff0c;我看到两个不同的说法&#xff0c;它们的区别就在于到底是从0开始计算还是从1开始计算。&#xff08;网上的和算法题偏向说法二&#xff0c;如果有能找到更加权威的解答望不吝赐教&#xff09; 说法一&#xff1a; 《数据结构与算法分析&…
阅读更多...
树的高度与深度--真情版

树的高度与深度--真情版

文章目录 一. 前言二. 大话高度与深度三. OJ题中使用的版本四. 考研中使用的版本五. 总结 一. 前言 数据结构-----树的学习过程中&#xff0c;我们会遇见一些摸棱两可的概念&#xff0c;比如树的度&#xff0c;子树的高度&#xff0c;子树的的深度等。我们时不时的会产生这样的…
阅读更多...
树的高度、深度、层的区别

树的高度、深度、层的区别

“高度”这个概念&#xff0c;其实就是从下往上度量&#xff0c;比如我们要度量第10层楼的高度、第13层楼的高度&#xff0c;起点都是地面。所以&#xff0c;树这种数据结构的高度也是一样&#xff0c;从最底层开始计数&#xff0c;并且计数的起点是0。 “深度”这个概念在生活…
阅读更多...
【数据结构】树的高度和深度

【数据结构】树的高度和深度

1.高度 结点的高度&#xff1a;从该节点向下分支的叶节点开始自底向上逐层累加。 对于高度的理解&#xff0c;就拿楼房来说&#xff0c;我们会从底层开始往上数&#xff0c;假如楼有6层&#xff0c;则我们会说&#xff0c;这个楼有6层楼那么高。所以高度就是以从下往上对比&…
阅读更多...
树的高度和深度以及结点的高度和深度

树的高度和深度以及结点的高度和深度

–> 参考链接 <– 树的高度和深度 深度定义是从上往下的&#xff0c;高度定义是从下往上的。&#xff08;其实不用在意这个&#xff0c;反正树的深度高度怎么数都一样的&#xff09;。 有两种说法&#xff1a; 高度就是深度看层数&#xff1a; 如果根结点第0&#xff…
阅读更多...
树的深度与广度优先遍历

树的深度与广度优先遍历

树是前端工程师最经常打交道的一个数据结构&#xff0c;比如说html标签组成的dom树、树形控件等。 在js中没有树这个数据结构&#xff0c;但是可以用Object和Array来构建树&#xff1a; //val是当前的节点值&#xff0c;children是子节点 const tree {val: A,children: [{va…
阅读更多...
树的高度和深度的区别

树的高度和深度的区别

树的高度和深度的区别 标签&#xff1a; 数据结构二叉树 2014-04-16 10:47 3362人阅读 评论(0) 收藏 举报 分类&#xff1a; 数据结构 版权声明&#xff1a;本文为博主原创文章&#xff0c;未经博主允许不得转载。 目录(?)[] 对于树的基本概念上理解&#xff0c;对于才接触…
阅读更多...
树的深度和高度解释

树的深度和高度解释

有个缺点&#xff0c;看到什么东西不管是不是重点只要说不通总是爱钻牛角尖。 对于 树的高度和深度&#xff08;以及结点的高度和深度&#xff09; 看了几本不同的书&#xff0c;都有各自的说法&#xff0c;多方查证吧&#xff0c;花了很多时间&#xff0c;最后归纳一个能说服我…
阅读更多...
大白话概念---树的高度和深度

大白话概念---树的高度和深度

树的高度和深度 &#xff08;本博客中使用图片为转载&#xff0c;侵删&#xff09; 1.深度 概念&#xff1a; 树的深度&#xff1a;距离根结点最远的结点所处的层数即为树的深度。 结点的深度我的课本上称为“层数”&#xff1a;即从根到该结点所经路径上的分支条数 空树深…
阅读更多...
树的最大深度和最小深度（java）

树的最大深度和最小深度（java）

目录 树的深度和高度二叉树的最大高度思路分析递归迭代 N叉树的最大深度LeetCode.559.N叉树的最大深度思路分析递归迭代 LeetCode.二叉树的最小深度思路分析递归迭代 树的深度和高度 什么是树的深度&#xff1f;什么是树的高度&#xff0c;一张图让你弄明白&#xff01;我们暂…
阅读更多...
【数据结构】树

【数据结构】树

树 前言树的定义和基本术语二叉树二叉树的性质二叉树的存储遍历二叉树线索二叉树 树和森林树的存储结构 赫夫曼树及其应用总结 前言 最害怕的数据结构之一——树&#xff0c;另一个是图。主要是当时递归和链表没学好&#xff0c;遍历或插入的时候总是思路不清&#xff0c;一堆的…
阅读更多...
树的高度和深度

树的高度和深度

1、树的深度 树的深度可以这样理解&#xff0c;计算一个节点的深度&#xff0c;从根节点算起&#xff08;记住从1开始计数&#xff0c;而不是0&#xff0c;程序员的通病在这不好使&#xff09;&#xff0c;到该节点所经过的节点数&#xff08;包括此节点&#xff09;为树的深度…
阅读更多...
无线协议

无线协议

一个AP的网络覆盖半径只有15米&#xff0c;需要布置多个AP&#xff0c;并且保证处在同一个网络中&#xff0c;受同一台或几台AC同一管理WDS&#xff0c;无线分布系统&#xff0c;俗称“无线桥接”指多个无线网络相互联结的方式构成一个整体的无线网络AP和AP之间通过无线信号互联…
阅读更多...
Wi-Fi 安全协议 - RSN

Wi-Fi 安全协议 - RSN

RSN&#xff08;Robust Security Network&#xff0c;强健安全网络&#xff09; TKIP 和 CCMP只能解决数据完整和机密性问题&#xff1b;为解决认证问题&#xff0c;IEEE 802.11借鉴了802.1X&#xff0c;引入RSNA&#xff08;Robust Secure Network Association&#xff09;&a…
阅读更多...
Wi-Fi 安全协议 - WPA

Wi-Fi 安全协议 - WPA

WPA (Wi-Fi Protected Access) 网络安全存取技术 WPA具有两种标准&#xff1a;WPA和WPA2&#xff0c;WPA2是WPA的增强型版本&#xff0c;增加了支持AES的加密方式。 WPA&#xff1a;由于WEP存在安全缺陷&#xff0c;在IEEE 802.11i提出前&#xff0c;Wi-Fi联盟&#xff08;WFA…
阅读更多...
wifi协议-802

wifi协议-802

WIFI协议 http://standards.ieee.org/about/get/802/802.11.html https://en.wikipedia.org/wiki/IEEE_802 Name Description NoteIEEE 802.1Higher Layer LAN ProtocolsactiveIEEE 802.2LLCdisbandedIEEE 802.3EthernetactiveIEEE 802.4Token busdisbandedIEEE 802.5Defines t…
阅读更多...
WIFI无线协议802.11a/b/g/n/ac的演变以及区别

WIFI无线协议802.11a/b/g/n/ac的演变以及区别

毫无疑问&#xff0c;WiFi的出现普及带给我们巨大的上网便利&#xff0c;所以了解一下WiFi对应的802.11协议的演变和现在不同版本之前的区别也是非常有必要的。 1&#xff0c;常识普及 Wi-Fi是一种允许电子设备连接到一个无线局域网&#xff08;WLAN&#xff09;的技术&#…
阅读更多...
WiFi各协议理论速度

WiFi各协议理论速度

一、总览 二、11b到11g提升点 802.11g工作在2.4G频段下&#xff0c;能够支持OFDM和CCK两种调制方式&#xff0c;提供16-QAM、64-QAM、BPSK和QPSK四种编码方式&#xff0c;我们通常说的54Mbps速率就是在2.4G频段下&#xff0c;通过OFDM调制&#xff0c;采用64-QAM编码的情况下实…
阅读更多...
Wi-Fi 安全协议

Wi-Fi 安全协议

无线网络的安全要求 机密性&#xff1a;确保数据不会泄露&#xff0c;防止数据被未经授权的第三者拦截。 帧主体加密机制&#xff08;frame body encryption&#xff09;&#xff1a;主要用来提供机密性。完整性&#xff1a;确保数据在传输过程中不被修改了。 完整性检验机制&…
阅读更多...
图解 802.11wifi协议

图解 802.11wifi协议

微信公号&#xff1a;卢同学 关注可了解更多。若有问题或建议&#xff0c;请与本人联系; 目录 凡事若能综观形势&#xff0c;通常有助于细节的进一步探究 从OSI七层模型来看&#xff0c;802规范的重心放在OSI模型最下面的两层&#xff0c;即数据链路层和物理层。 数据链路层又…
阅读更多...
推荐文章

Copyright @ 2022~2023