文字描述
对无向图进行遍历时，对于连通图，仅需从图中任一顶点出发，进行深度优先搜索或广度优先搜索，便可访问到图中所有顶点。但对非连通图，则需从多个顶点出发搜索，每一次从一个新的起始点出发进行搜索过程得到的顶点访问序列恰为其各个连通分量中的顶点集。
对于非连通图,每个连通分量中的顶点集,和遍历时走过的边一起构成若干棵生成树,这些连通分量的生成树组成非连通图的生成森林.
示意图
算法分析
求无向图的连通分量的生成森林的算法时间复杂度和遍历相同.
代码实现
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 }
代码运行
