非连通图生成森林

非连通图生成森林

   数据结构 16 分钟读完 (大约2464个字) 0次访问

一、深度优先生成森林

本节实现对非连通图由深度优先搜索生成森林；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//----------------建立无向图的深度优先生成森林------------------//
// 以孩子兄弟链表作生成森林的存储结构
typedef struct CSNode {
       TElemType data;
       struct CSNode  *firstchild,  *nextsibling;  
}CSNode, *CSTree;
Status DFSForest(ALGraph G,  CSTree &T)
{   
    // 建立无向图G的深度优先生成森林
    CSTree  p,  q;   
    T = NULL; 
    int v = 0;   
    inp(v,0,G.vexnum-1)  visite[v] = unvisited;   // 节点初始化
    inp(v,0,G.vexnum-1)
        if(!visite[v]){
            p = (CSTree) malloc(sizeof(CSNode));
            *p = {G.Vextices[v].data, NULL, NULL};
            if(!T) T = p;
            else q->nextsibling = p;     // 是其他生成树的根
            q = p;                 // q指示当前生成树的根
            DFSTree(G, v, q);        // 建立以p为根的生成树
        }
    return true;
}
Status DFSTree(ALGraph G,  int v,  CSTree &T)
{   
    // 从第v个顶点出发深度优先遍历图G，建立以T为根的生成树
    CSTree p, q;  
    visite[v] = visited;    // 子树根节点已访问过
    bool first = true;
    for(ArcNode *a=G.Vextices[v].firstarc; a; a=a->nextarc){
        int w = a->adjvex;
        if(!visite[w]){    // 排除根节点的父代节点
            p = (CSTree)malloc(sizeof(CSNode));    // 为当前遍历的节点申请空间
            *p = {G.Vextices[w].data, NULL, NULL}; 
            if(first) {
                T->firstchild = p;     // 找到根节点的第一个孩子 
                first = false; 
            }
            else q->nextsibling = p;    // 其他孩子节点作为上一节点的右兄弟节点
            q = p;                      // 更新上一节点
            DFSTree(G, w, q);           // 递归生成以q为根节点的子树
        }
    }
    return ;
}

注解：DFSForest()函数：

  • 通过对所有节点遍历，如果节点未被访问过，申请节点空间，进行赋值存储；
  • T指向整个森林的根节点，DFSTree()函数为连通子图生成一棵树，从一个连通子图中的一个节点进行深度优先搜索一定会遍历该连通子图中所有的节点；
  • 因此对其他未被访问过的节点即是另一个连通子图上的节点，再次循环，将其连接在 q(指向上一棵树的根节点)的兄弟节点；
  • 总体而言，DFSForest()函数是将各个连通子图转换成一棵树，再串联成森林；DFSTree()函数：
  • 通过邻接点遍历，设置第一次访问(除了父代节点)为孩子节点，其余邻接点均通过 q记录上一个兄弟置于右兄弟位置上；
  • 深度优先的体现：对当前节点的每一个邻接点，再次进行递归生成树，优先保证加深度而非加宽度(即优先遍历孩子节点而非优先遍历兄弟节点)；

二、广度优先生成森林

本节实现对非连通图由广度优先搜索生成森林；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//----------------建立无向图的广度优先生成森林------------------//
typedef struct QElem {        // 用于广度优先生成树中元素结构
       CSTree  node;
       int v;  
}QElem;
Status BFSForest(ALGraph G,  CSTree &T)
{   
    // 建立无向图G的广度优先生成森林
    CSTree  p,  q;   
    T = NULL; 
    int v = 0;   
    inp(v,0,G.vexnum-1)  visite[v] = unvisited;   // 节点初始化
    inp(v,0,G.vexnum-1)
        if(!visite[v]){
            p = (CSTree) malloc(sizeof(CSNode));
            *p = {G.Vextices[v].data, NULL, NULL};
            if(!T) T = p;
            else q->nextsibling = p;     // 是其他生成树的根
            q = p;                 // q指示当前生成树的根
            BFSTree(G, v, q);        // 建立以p为根的生成树
        }
    return true;
}
Status BFSTree(ALGraph G,  int v,  CSTree &T)
{
    bool first = true;
    // 处理根节点
    queue<QElem> Q; Q.push({T, v}); visite[v]=visited; 
    while (!Q.empty()) {
        QElem e = Q.front(); Q.pop();
        CSTree q = e.node;
        first = true;    // 标记q节点的第一个孩子
        // 在邻接表中搜寻当前节点未访问过的节点
        for(ArcNode *a=G.Vextices[e.v].firstarc;  a;  a=a->nextarc){
            int w = a->adjvex;
            if(!visite[w]){
                CSTree p = (CSTree)malloc(sizeof(CSNode));
                *p = {G.Vextices[w].data, NULL, NULL};
                Q.push({p, w});visite[w] = visited;

                if(first){
                    q->firstchild = p;  
                    first = false; 
                }
                else q->nextsibling = p;
                q = p;   // 更新上一节点==>指向上一兄弟
            }//if
        }//for
    }//while
    return true;
}

注解：

  • DFSForest()函数同理，而 BFSTree()函数通过队列对根节点未被访问过的邻接点不断扩展；
  • 广度优先的体现：对每一个从队列取出的当前节点扩展所有邻接点，即遍历构建除根节点外的其他所有孩子节点；
  • 因此生成的森林中按照层序遍历，每一层都是尽量多节点的；
    综合后的代码：(其中 ADL.h是图的存储结构表示中给出的邻接表与逆邻接表表示方式)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
#include<iostream>
#include<queue>
#include"ADL.h"
using namespace std;
//-------------建立无向图的生成森林------------------//
// 以孩子兄弟链表作生成森林的存储结构
#define TElemType string
#define inp(i,x,y) for(i=x;i<=y;i++)
#define Max_Vertex_Num 20
typedef enum{unvisited, visited}VisitIf;

typedef struct CSNode {
       TElemType data;
       struct CSNode  *firstchild,  *nextsibling;  
}CSNode, *CSTree;
typedef struct QElem {        // 用于广度优先生成树中元素结构
       CSTree  node;
       int v;  
}QElem;

VisitIf visite[Max_Vertex_Num];

//-------------------------生成森林函数---------------------------//
Status CreateForest(ALGraph G,  CSTree &T, Status(*CreateTree)(ALGraph G,  int v,  CSTree &T));
Status DFSTree(ALGraph G,  int v,  CSTree &T);   // 深度优先
Status BFSTree(ALGraph G,  int v,  CSTree &T);   // 广度优先
//--------------------生成森林的遍历-------------------------//
Status CSFPreRootOrder(CSTree T, Status(*Visit)(TElemType e));     // 先根遍历
Status CSFPostRootOrder(CSTree T, Status(*Visit)(TElemType e));		// 后根遍历
Status LevelOrderTraverse(CSTree T, Status(*Visit)(TElemType e));     // 层序遍历
Status TreeTransOperator(TElemType e);    // 二叉树遍历算子
Status ForestPrint(CSTree T);       // 森林输出函数
int main()
{
    ALGraph G, GR;
    CreateGraph(G, GR);
    CSTree DFST, BFST;
    CreateForest(G, DFST, DFSTree);
    CreateForest(G, BFST, BFSTree);
    GraphPrint(G, GR);
    cout << "------------------------CS_Forest DFS Traverse-------------------------\n";
    ForestPrint(DFST);
    cout << endl << "------------------------CS_Forest BFS Traverse-------------------------\n";
    ForestPrint(BFST);
    return 0;
}

Status CreateForest(ALGraph G,  CSTree &T, Status(*CreateTree)(ALGraph G,  int v,  CSTree &T))
{   
    // 建立无向图G的生成森林
    CSTree  p,  q;   
    T = NULL; 
    int v = 0;   
    inp(v,0,G.vexnum-1)  visite[v] = unvisited;   // 节点初始化
    inp(v,0,G.vexnum-1)
        if(!visite[v]){
            p = (CSTree) malloc(sizeof(CSNode));
            *p = {G.Vextices[v].data, NULL, NULL};
            if(!T) T = p;
            else q->nextsibling = p;     // 是其他生成树的根
            q = p;                 // q指示当前生成树的根
            CreateTree(G, v, q);        // 建立以p为根的生成树
        }
    return true;
}
//-----------深度优先生成森林------------//
Status DFSTree(ALGraph G,  int v,  CSTree &T)
{   
    // 从第v个顶点出发深度优先遍历图G，建立以T为根的生成树
    CSTree p, q;  
    visite[v] = visited;    // 子树根节点已访问过
    bool first = true;
    for(ArcNode *a=G.Vextices[v].firstarc; a; a=a->nextarc){
        int w = a->adjvex;
        if(!visite[w]){    // 排除根节点的父代节点
            p = (CSTree)malloc(sizeof(CSNode));    // 为当前遍历的节点申请空间
            *p = {G.Vextices[w].data, NULL, NULL}; 
            if(first) {
                T->firstchild = p;     // 找到根节点的第一个孩子 
                first = false; 
            }
            else q->nextsibling = p;    // 其他孩子节点作为上一节点的右兄弟节点
            q = p;                      // 更新上一节点
            DFSTree(G, w, q);           // 递归生成以q为根节点的子树
        }
    }
    return true;
}

//-----------广度优先生成森林------------//
Status BFSTree(ALGraph G,  int v,  CSTree &T)
{
    bool first = true;
    // 处理根节点
    queue<QElem> Q; Q.push({T, v}); visite[v]=visited; 
    while (!Q.empty()) {
        QElem e = Q.front(); Q.pop();
        CSTree q = e.node;
        first = true;    // 标记q节点的第一个孩子
        // 在邻接表中搜寻当前节点未访问过的节点
        for(ArcNode *a=G.Vextices[e.v].firstarc;  a;  a=a->nextarc){
            int w = a->adjvex;
            if(!visite[w]){
                CSTree p = (CSTree)malloc(sizeof(CSNode));
                *p = {G.Vextices[w].data, NULL, NULL};
                Q.push({p, w});visite[w] = visited;

                if(first){
                    q->firstchild = p;  
                    first = false; 
                }
                else q->nextsibling = p;
                q = p;   // 更新上一节点==>指向上一兄弟
            }//if
        }//for
    }//while
    return true;
}

Status TreeTransOperator(TElemType e)    // 二叉树遍历算子
{
    // 对数据元素操作的应用函数
    cout << e << " ";
    return true;
}
Status CSFPreRootOrder(CSTree T, Status(*Visit)(TElemType e))    // 前根遍历
{
	if(T == NULL){
        return true;
    }
	Visit(T->data);
	CSFPreRootOrder(T->firstchild, Visit);
	CSFPreRootOrder(T->nextsibling, Visit);
    return true;
}
Status CSFPostRootOrder(CSTree T, Status(*Visit)(TElemType e))		// 后根遍历
{
	if(T == NULL){
        return true;
    }
	CSFPostRootOrder(T->firstchild, Visit);
	Visit(T->data);
	CSFPostRootOrder(T->nextsibling, Visit);
    return true;
}
Status LevelOrderTraverse(CSTree T, Status(*Visit)(TElemType e))
{
	if(T == NULL){
        cout << "This is an empty tree.\n";
        return true;
    }
	queue<CSNode*> q;
    q.push(T);
    int i = 0, width = 1;
    while(!q.empty())
    {
        CSTree P;
        inp(i,0,width-1){
            if(!q.empty()){
                P = q.front();q.pop();
                q.push(P);
            }
            while(P->nextsibling){
                q.push(P->nextsibling);
                P = P->nextsibling;
            }
        }

        width = q.size();
        cout << "Nodes number of the current layer: " << width << " ";
        inp(i,0,width-1){
            if(!q.empty()){
                P = q.front();q.pop();
            }
            Visit(P->data);
            if(P->firstchild) q.push(P->firstchild);
        }
        cout << endl;
    }
    return true;
}
Status ForestPrint(CSTree T)
{
    int i = 1;
    CSTree P = T;
    while(T){
        cout << "--------------------Subtree " << i++ <<"------------------\n";
        cout << "CS_Forest First root Traverse:\n";
        TreeTransOperator(T->data);
        CSFPreRootOrder(T->firstchild, TreeTransOperator);     // 等于二叉树中先序
    
        cout << endl << "CS_Forest Post root Traverse:\n";
        CSFPostRootOrder(T->firstchild, TreeTransOperator);    // 等于二叉树中中序
        TreeTransOperator(T->data);
        cout << endl;
        T = T->nextsibling;
    }
    cout << "CS_Forest Level Traverse:\n";
    LevelOrderTraverse(P, TreeTransOperator);
    return true;
}

给出一个算例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
/*
Input the type of graph(0:DG,1:DN,2:UDG,3:UDN):
2
Input Vextices number, Arcs number and Incinformation(1:Yes,0:NO):
13 13 0
Input Graph Node Sign:
A B C D E F G H I J K L M
Input two vertices of the edges:
A B 
A C
A F
A L
L J
L M
J M
B M
D E
G H
G K
G I
H K
----------------Output Graph Information-----------------
Graph Kind: undirected graph
Vextices number: 13   Arcs number: 13

----------------Vextices Vector Information----------------
The Nodes Path:
Out path: A-<-[1]->-B  A-<-[1]->-C  A-<-[1]->-F  A-<-[1]->-L
A  Vextice Degree: 4

Out path: B-<-[1]->-A  B-<-[1]->-M
B  Vextice Degree: 2

Out path: C-<-[1]->-A
C  Vextice Degree: 1

Out path: D-<-[1]->-E
D  Vextice Degree: 1

Out path: E-<-[1]->-D
E  Vextice Degree: 1

Out path: F-<-[1]->-A
F  Vextice Degree: 1

Out path: G-<-[1]->-H  G-<-[1]->-K  G-<-[1]->-I
G  Vextice Degree: 3

Out path: H-<-[1]->-G  H-<-[1]->-K
H  Vextice Degree: 2

Out path: I-<-[1]->-G
I  Vextice Degree: 1

Out path: J-<-[1]->-L  J-<-[1]->-M  
J  Vextice Degree: 2

Out path: K-<-[1]->-G  K-<-[1]->-H
K  Vextice Degree: 2

Out path: L-<-[1]->-A  L-<-[1]->-J  L-<-[1]->-M
L  Vextice Degree: 3

Out path: M-<-[1]->-L  M-<-[1]->-J  M-<-[1]->-B
M  Vextice Degree: 3

------------------------CS_Forest DFS Traverse-------------------------
--------------------Subtree 1------------------
CS_Forest First root Traverse:
A B M L J C F 
CS_Forest Post root Traverse:
J L M B C F A
--------------------Subtree 2------------------
CS_Forest First root Traverse:
D E
CS_Forest Post root Traverse:
E D
--------------------Subtree 3------------------
CS_Forest First root Traverse:
G H K I
CS_Forest Post root Traverse:
K H I G
CS_Forest Level Traverse:
Nodes number of the current layer: 3 A D G
Nodes number of the current layer: 6 B C F E H I
Nodes number of the current layer: 2 M K
Nodes number of the current layer: 1 L
Nodes number of the current layer: 1 J

------------------------CS_Forest BFS Traverse-------------------------
--------------------Subtree 1------------------
CS_Forest First root Traverse:
A B M C F L J
CS_Forest Post root Traverse:
M B C F J L A
--------------------Subtree 2------------------
CS_Forest First root Traverse:
D E
CS_Forest Post root Traverse:
E D
--------------------Subtree 3------------------
CS_Forest First root Traverse:
G H K I
CS_Forest Post root Traverse:
H K I G
CS_Forest Level Traverse:
Nodes number of the current layer: 3 A D G
Nodes number of the current layer: 8 B C F L E H K I
Nodes number of the current layer: 2 M J
*/

非连通图生成森林

https://markstiff.github.io/数据结构/生成森林/

作者

Mark Stiff

发布于

2022-10-30

更新于

2024-01-21

许可协议

 

喜欢这篇文章？打赏一下作者吧

评论

  关注我

目录

分类

标签

Generative Model1
Latex3
Markdown1
二叉树1
人工智能1
体系结构1
图论2
字符串1
嵌入式2
嵌入式系统1
排序4
数字信号处理1
数学6
数据库系统1
数据结构16
数据结构与算法 - LeetCode1
概率论与数理统计 - 数学1
稀疏矩阵3
算法3
算法竞赛3
计算机原理4
软件工程1
×