图->连通性->无向图的连通分量和生成树

时间:2022-05-26 11:38:16

文字描述

  对无向图进行遍历时,对于连通图,仅需从图中任一顶点出发,进行深度优先搜索或广度优先搜索,便可访问到图中所有顶点。但对非连通图,则需从多个顶点出发搜索,每一次从一个新的起始点出发进行搜索过程得到的顶点访问序列恰为其各个连通分量中的顶点集。

  对于非连通图,每个连通分量中的顶点集,和遍历时走过的边一起构成若干棵生成树,这些连通分量的生成树组成非连通图的生成森林.

示意图

图->连通性->无向图的连通分量和生成树

图->连通性->无向图的连通分量和生成树

 

算法分析

求无向图的连通分量的生成森林的算法时间复杂度和遍历相同.

代码实现

图->连通性->无向图的连通分量和生成树图->连通性->无向图的连通分量和生成树
  1 //1.建立无向图
  2 //2.建立无向图的深度优先生成森林, 森林转换成二叉树结构,并采用孩子兄弟链表存储
  3 //https://www.cnblogs.com/tgycoder/p/5048898.html
  4 //https://blog.csdn.net/qq_16234613/article/details/77431043
  5 
  6 #include <stdio.h>
  7 #include <stdlib.h>
  8 #include <string.h>
  9 
 10 ///for debug start///
 11 #include <stdarg.h>
 12 #define DEBUG(args...) debug_(__FILE__, __FUNCTION__, __LINE__, ##args)
 13 void debug_(const char* file, const char* function, const int line, const char *format, ...)
 14 {
 15     char buf[1024] = {0};
 16     sprintf(buf, "[%s,%s,%d]", file, function, line);
 17 
 18     va_list list;
 19     va_start(list, format);
 20     vsprintf(buf+strlen(buf), format, list);
 21     va_end(list);
 22 
 23     printf("%s\n", buf);
 24 
 25 }
 26 ///for debug end///
 27 
 28 #define INFINITY        100000
 29 #define MAX_VERTEX_NUM    20
 30 #define None -1
 31 typedef enum {DG, DN, UDG, UDN} GraphKind;
 32 typedef char VertexType;
 33 typedef struct{char note[10];}InfoType;
 34 //弧结点
 35 typedef struct ArcNode{
 36     int adjvex;//该弧所指向的顶点的位置
 37     struct ArcNode *nextarc;//指向下一条弧的结点
 38     InfoType *info;//与该弧相关的其他信息
 39 }ArcNode;
 40 typedef struct VNode{
 41     VertexType data;//顶点信息
 42     ArcNode *firstarc;//指向第一条依附该顶点的弧的指针
 43 }VNode, AdjList[MAX_VERTEX_NUM];
 44 
 45 typedef struct{
 46     AdjList vertices;//存放图的头结点的链表
 47     int vexnum;//图的顶点数
 48     int arcnum;//图的弧数
 49     int kind;//图类型
 50 }ALGraph;
 51 
 52 //返回图G中顶点信息委v的顶点位置
 53 int LocateVex(ALGraph G, VertexType v)
 54 {
 55     int i = 0;
 56     for(i=0; i<G.vexnum; i++){
 57         if(G.vertices[i].data == v){
 58             return i;
 59         }
 60     }
 61     return -1;
 62 }
 63 
 64 //返回图G的顶点位置为loc的顶点信息
 65 VertexType GetVex(ALGraph G, int loc)
 66 {
 67     return G.vertices[loc].data;
 68 }
 69 
 70 //在链表L的头部插入顶点v
 71 int InsFirst(ArcNode *L, int v)
 72 {
 73     ArcNode *n = (ArcNode *)malloc(sizeof(struct ArcNode));
 74     n->adjvex = v;
 75     n->nextarc = L->nextarc;
 76     L->nextarc = n;
 77     return 0;
 78 }
 79 
 80 //返回图G中与顶点v相连的第一个顶点在图中的位置
 81 int FirstAdjVex(ALGraph G, int v)
 82 {
 83     return G.vertices[v].firstarc->nextarc->adjvex;
 84 }
 85 
 86 //返回图G中与顶点v相邻的w的下一个相邻的定点在图中的位置
 87 int NextAdjVex(ALGraph G, int v, int w)
 88 {
 89     ArcNode *arc = G.vertices[v].firstarc;
 90     while(arc && arc->adjvex != w){
 91         arc = arc->nextarc;
 92     }
 93     if(arc && arc->nextarc){
 94         return arc->nextarc->adjvex;
 95     }
 96     return None;
 97 }
 98 
 99 //创建一个无向图
100 int CreateUDG(ALGraph *G){
101     printf("!以邻接表作为图的存储结构创建无向图!\n");
102     G->kind = UDG;
103     int i = 0, j = 0, k = 0, IncInfo = 0;
104     int v1 = 0, v2 = 0;
105     char tmp[10] = {0};
106     printf("输入顶点数,弧数:");
107     scanf("%d,%d", &G->vexnum, &G->arcnum);
108     for(i=0; i<G->vexnum; i++){
109         printf("输入第%d个顶点: ", i+1);
110         memset(tmp, 0, sizeof(tmp));
111         scanf("%s", tmp);
112         G->vertices[i].data = tmp[0];
113         G->vertices[i].firstarc = malloc(sizeof(struct ArcNode));
114         G->vertices[i].firstarc->adjvex = None;
115         G->vertices[i].firstarc->nextarc = NULL;
116     }
117     for(k=0; k<G->arcnum; k++){
118         printf("输入第%d条弧(顶点1, 顶点2): ", k+1);
119         memset(tmp, 0, sizeof(tmp));
120         scanf("%s", tmp);
121         sscanf(tmp, "%c,%c", (char *)&v1, (char *)&v2);
122         i = LocateVex(*G, v1);
123         j = LocateVex(*G, v2);
124         InsFirst(G->vertices[i].firstarc, j);
125         InsFirst(G->vertices[j].firstarc, i);
126         if(IncInfo){}
127     }
128     return 0;
129 }
130 
131 //打印无向图G的邻接表信息
132 void printALG(ALGraph G)
133 {
134     int i = 0;
135     ArcNode *p = NULL;
136     for(i=0; i<G.vexnum; i++){
137         printf("%c\t", G.vertices[i].data);
138         p = G.vertices[i].firstarc;
139         while(p){
140             if(p->adjvex != None){
141                 printf("%d\t", p->adjvex);
142             }
143             p = p->nextarc;
144         }
145         printf("\n");
146     }
147     return;
148 }
149 
150 typedef VertexType TElemType;
151 //采用孩子兄弟链表存储结构
152 typedef struct{
153     TElemType data;
154     struct CSNode *firstchild;
155     struct CSNode *nextsibling;
156 }CSNode, *CSTree;
157 
158 //先根遍历树T
159 void PreOrderTraverse(CSTree T){
160     if(T){
161         printf("%c\t", T->data);
162         PreOrderTraverse((CSTree)T->firstchild);
163         PreOrderTraverse((CSTree)T->nextsibling);
164         return ;
165     }else{
166         return ;
167     }
168 }
169 
170 //中根遍历树T
171 void InOrderTraverse(CSTree T){
172     if(T){
173         InOrderTraverse((CSTree)T->firstchild);
174         printf("%c\t", T->data);
175         InOrderTraverse((CSTree)T->nextsibling);
176         return ;
177     }else{
178         return ;
179     }
180 }
181 
182 int visited[MAX_VERTEX_NUM];
183 CSTree DFSTree_q = NULL;
184 int ISFirst = 1;
185 //从第v个顶点出发深度优先遍历图G,建立以T为根的生成树
186 void DFSTree(ALGraph G, int V, CSTree *T)
187 {
188     int w = 0;
189     CSTree p = NULL;
190     visited[V] = 1;
191     for(w=FirstAdjVex(G, V); w>=0; w=NextAdjVex(G, V, w)){
192         if(!visited[w]){
193             //分配孩子结点
194             p = (CSTree)malloc(sizeof(CSNode));
195             p->data = GetVex(G, w);
196             p->firstchild = NULL;
197             p->nextsibling = NULL;
198             if(ISFirst){
199                 //w是v的第一个未被访问的邻接顶点
200                 ISFirst = 0;
201                 (*T)->firstchild = (struct CSNode *)p;
202             }else{
203                 //w是v的其它未被访问的邻接顶点
204                 //是上一个邻接顶点的右兄弟结点 
205                 DFSTree_q->nextsibling = (struct CSNode *)p;
206             }
207             DFSTree_q = p;
208             //从第w个顶点出发深度优先遍历图G,建立子生成树DFSTree_q
209             DFSTree(G, w, &DFSTree_q);
210         }
211     }
212 }
213 
214 //建立无向图G的深度优先生成森林的孩子兄弟链表T
215 void DFSForest(ALGraph G, CSTree *T)
216 {
217     CSTree p = NULL;
218     CSTree q = NULL;
219     *T = NULL;
220     int v = 0;
221     for(v=0; v<G.vexnum; v++){
222         visited[v] = 0;
223     }
224     for(v=0; v<G.vexnum; v++){
225         if(!visited[v]){
226             //第v个顶点为新的生成树的根结点
227             p = (CSTree)malloc(sizeof(CSNode));
228             p->data = GetVex(G, v);
229             p->firstchild = NULL;
230             p->nextsibling = NULL;
231             if(!(*T)){
232                 //是第一颗生成树的根
233                 *T = p;
234             }else{
235                 //是其他生成树的根(前一颗的根的“兄弟”)
236                 q->nextsibling = (struct CSNode *)p;
237             }
238             //q指示当前生成树的根
239             q = p;
240             //建立以p为根的生成树
241             ISFirst = 1;
242             DFSTree(G, v, &p);
243         }
244     }
245 }
246 
247 int main(int argc, char *argv[])
248 {
249     ALGraph G;
250     //创建一个无向图
251     CreateUDG(&G);
252     //打印无向图中的信息
253     printALG(G);
254     
255     CSTree T;
256     //依照无向图G,建立一颗生成森林,并将其转换成成二叉树存储,二叉树以孩子兄弟链表存储结构存储
257     DFSForest(G, &T);
258     //先根遍历该生成树
259     PreOrderTraverse(T);printf("\n");
260     //中根遍历该生成树
261     InOrderTraverse(T);printf("\n");
262     return 0;
263 }
无向图的深度优先生成森林算法

代码运行

图->连通性->无向图的连通分量和生成树