数据结构-无向图的连通分量和生成树 （C语言代码）

解题思路:

    尝试写了出来。

参考代码:

#include<stdio.h>
#include<malloc.h>

#define MAX_VEX_NUM 50
#define True 1
#define False 0

typedef struct AdjCell{
    int adj;
    //int *info;
} AdjCell, AdjMatrix[MAX_VEX_NUM][MAX_VEX_NUM];

typedef struct MGraph{
    int vexs[MAX_VEX_NUM];
    AdjMatrix arcs;
    int vexnum;
    //int arcnum;
} MGraph;

typedef struct CSNode{
    int data;
    struct CSNode *firstchild;
    struct CSNode *nextsibling;
} *CSTree, CSNode;

void CreateMGraph(MGraph *G);

void DFSForest(MGraph *G, CSTree *T);

void DFSTree(MGraph *G, CSTree *T, int i, int *visited);

void PreOrderTraverse(CSTree T);

int main()
{
    MGraph G;
    CSTree T = NULL;
    CreateMGraph(&G);
    DFSForest(&G, &T);
    return 0;
}

void CreateMGraph(MGraph *G){
    
    int i, j;
    
    scanf("%d", &G->vexnum);
    
    for(i = 0; i < G->vexnum; i++){
        
        G->vexs[i] = i;
    }
    
    for(i = 0; i < G->vexnum; i++){
        
        for(j = 0; j < G->vexnum; j++){
            
            scanf("%d", &G->arcs[i][j].adj);
        }
    }
}

void DFSForest(MGraph *G, CSTree *T){
    
    int visited[MAX_VEX_NUM] = { False };
    int i;
    CSNode *p = NULL, *q = NULL;
    
    for(i = 0; i < G->vexnum; i++){
        
        if(visited[i] == False){
            
            p = (CSNode *)malloc(sizeof(CSNode));
            p->data = G->vexs[i];
            p->firstchild = NULL;
            p->nextsibling = NULL;
            
            if(!(*T)){
                
                (*T) = p;
            }
            else{
                
                q->nextsibling = p;
            }
            
            q = p;
            DFSTree(G, &p, i, visited);
            PreOrderTraverse(p);
        }
    }
}

void DFSTree(MGraph *G, CSTree *T, int i, int *visited){
    
    visited[i] = True;
    int j, first = True;
    CSNode *p = NULL, *q = NULL;
    
    for(j = 0; j < G->vexnum; j++){
        
        if(G->arcs[i][j].adj == 1 && visited[j] == False){
            
            p = (CSNode *)malloc(sizeof(CSNode));
            p->data = j;
            p->firstchild = NULL;
            p->nextsibling = NULL;
            
            if(first == True){
                
                (*T)->firstchild = p;
                first = False;
            }
            else{
                
                q->nextsibling = p;
            }
            
            q = p;
            DFSTree(G, &p, j, visited);
        }
    }
}

void PreOrderTraverse(CSTree T){
    
    CSNode *stack[MAX_VEX_NUM];
    int top = -1;
    CSNode *p = T;
    
    while(p || top > -1){
        
        if(p){
            
            printf("%d ", p->data);
            stack[++top] = p;
            p = p->firstchild;
        }
        else{
            
            p = stack[top--];
            p = p->nextsibling;
        }
    }
    printf("\n");
}