無向圖的生成樹和生成森林---孩子兄弟連結清單表示法

//對于非連通圖，每個連通分量中的頂點集，和周遊時走過的邊一起構成若幹棵生成樹，
//這些連通分量的生成樹組成非連通圖的生成森林。
//以孩子兄弟連結清單作為生成森林的存儲結構，以下算法生成非連通圖的深度優先生成森林。
//算法的時間複雜度為周遊算法相同.
#include <stdio.h>
#include <stdlib.h>
#define MAX 20
typedef char ElemType;
typedef enum {FALSE,TRUE} Boolean;
typedef int Status;
Boolean visited[MAX];
//鄰接表結構表示的圖
#include <limits.h>
#define MAX_VERTEX_NUM 20
#define OK 1
#define ERROR 0
typedef int InfoType;  //定義弧相關資訊為整形
typedef char VertexType;    //定義頂點類型為字元型

typedef struct ArcNode
{
    int adjvex;               //該弧所指向的頂點在順序結構中的位置
    struct ArcNode *nextarc;  //與該弧鄰接(同一尾結點)的下一條弧的指針
    InfoType *info;           //該弧相關資訊的指針
}ArcNode;                     //弧結構

typedef struct VNode
{
    VertexType data;            //頂點
    ArcNode *firstarc;          //指向第一條依附該頂點的弧的指針
}VNode,AdjList[MAX_VERTEX_NUM]; //頂點結構

typedef struct
{
    AdjList vertices;     //頂點數組
    int vexnum,arcnum;    //頂點數和弧數
}ALGraph;                 //鄰接表表示的圖結構
//樹結構：孩子兄弟鍊
typedef struct CSNode
{
    ElemType data;
    struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;

Status CreateUDG(ALGraph *G);
void DFSForest(ALGraph G,CSTree *T);
void DFSTree(ALGraph G,int v,CSTree *t);
int LocateVex(ALGraph G,VertexType v);
void CSTreeTraverse(CSTree T);

int FirstAdjVex(ALGraph G,int v);
int NextAdjVex(ALGraph G,int v,int w);

int main()
{
    ALGraph *G;
    G=(ALGraph *)malloc(sizeof(ALGraph));
    CSTree T;
    T=(CSTree)malloc(sizeof(CSNode));

    CreateUDG(G);
    int i;
    printf("圖結構：\n");
    for(i=0;i<G->vexnum;i++)
    {
        ArcNode *p;

        p=(ArcNode *)malloc(sizeof(ArcNode));
        p=G->vertices[i].firstarc;
        printf("%c ",G->vertices[i].data);
        while(p)
        {
            VertexType t;
            int k;
            k=p->adjvex;
            t=G->vertices[k].data;
            printf("%c ",t);

            p=p->nextarc;
        }
        printf("\n");
    }
    printf("廣度優先搜尋：\n");
    DFSForest(*G,&T);
    CSTreeTraverse(T);
    return 0;
}
int LocateVex(ALGraph G,VertexType v)
{
    int i;
    for(i=0;i<G.vexnum;i++)
        if(G.vertices[i].data==v)
            return i;
    return -1;
}
//建立無向圖
Status CreateUDG(ALGraph *G)
{
   int i,IncInfo;
    printf("輸入頂點數量：");
    scanf("%d",&G->vexnum);
    printf("輸入弧數量：");
    scanf("%d",&G->arcnum);
    printf("弧是否含有其他資訊（否---0,是---1）：");
    scanf("%d",&IncInfo);
    //頭結點處理
    for(i=0;i<G->vexnum;i++)
    {
        fflush(stdin);
        printf("輸入第%d個頂點：",i+1);
        scanf("%c",&G->vertices[i].data);    //輸入頭結點的頂點資訊
        G->vertices[i].firstarc=NULL;        //初始化頭結點的弧指針
    }
    //弧結點處理
    for(i=0;i<G->arcnum;i++)
    {
        char v1,v2;
        int node1,node2;
        fflush(stdin);
        printf("輸入第%d條弧的依附的第一個結點：",i+1);
        scanf("%c",&v1);
        fflush(stdin);
        printf("輸入第%d條弧的依附的第二個結點：",i+1);
        scanf("%c",&v2);

        node1=LocateVex(*G,v1);
        node2=LocateVex(*G,v2);

        ArcNode *p1,*p2;
        //兩個指針變量雖然是同一類型，但不能用一條配置設定記憶體語句同時配置設定，否則為同一指針變量，即指向同一位址
        p1=(ArcNode *)malloc(sizeof(ArcNode));
        p2=(ArcNode *)malloc(sizeof(ArcNode));

        p1->adjvex=node1;
        p2->adjvex=node2;
        p1->nextarc=G->vertices[node2].firstarc;
        G->vertices[node2].firstarc=p1;
        p2->nextarc=G->vertices[node1].firstarc;
        G->vertices[node1].firstarc=p2;
        if(IncInfo)
        {
            int info;
            printf("輸入弧的其他資訊：");
            scanf("%d",&info);
            p1->info=p2->info=&info;
        }
        else
            p1->info=p2->info=NULL;
    }
    return OK;
}
//求位置v結點的第一個鄰接點
int FirstAdjVex(ALGraph G,int v)
{
    if(G.vertices[v].firstarc)
        return G.vertices[v].firstarc->adjvex;
    else
        return -1;
}
//求位置v結點就w外的其他鄰接點
int NextAdjVex(ALGraph G,int v,int w)
{
    ArcNode *p;
    p=(ArcNode *)malloc(sizeof(ArcNode));

    p=G.vertices[v].firstarc;
    while(p)
    {
        if(p->adjvex==w || visited[p->adjvex])
            p=p->nextarc;
        else
            return p->adjvex;
    }
    return -1;
}

void DFSForest(ALGraph G,CSTree *T)
{
    *T=NULL;
    int v;
    for(v=0;v<G.vexnum;v++)
        visited[v]=FALSE;
    CSTree q;
    q=(CSTree)malloc(sizeof(CSNode));
    for(v=0;v<G.vexnum;v++)
    {
        if(!visited[v])
        {
            CSTree p;
            p=(CSTree)malloc(sizeof(CSNode));

            p->data=G.vertices[v].data;
            p->firstchild=NULL;
            p->nextsibling=NULL;

            if(!(*T))
                *T=p;
            else
                q->nextsibling=p;
            q=p;
            DFSTree(G,v,&p);
        }
    }
}
void DFSTree(ALGraph G,int v,CSTree *t)
{
    int w;
    Boolean first;

    first=TRUE;
    visited[v]=TRUE;

    CSTree n;
    n=(CSTree)malloc(sizeof(CSNode));
    for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
    {
        if(!visited[w])
        {
            CSTree m;

            m=(CSTree)malloc(sizeof(CSNode));
            m->data=G.vertices[w].data;
            m->firstchild=NULL;
            m->nextsibling=NULL;

            if(first)
            {
                (*t)->firstchild=m;  //1.如果位置w結點m是位置v結點的第一個鄰接點，則将其作為孩子結點
                first=FALSE;
            }
            else
            {
                n->nextsibling=m;   //３.如果位置w結點m不是位置v結點的第一個鄰接點，則将其作為上一個結點的兄弟結點
            }
            n=m;                      //2.将指針指向目前生成的結點
            DFSTree(G,w,&m);          //4.再從目前結點m出發進行深度周遊
        }
    }
}
//孩子兄弟連結清單表示的樹的周遊
void CSTreeTraverse(CSTree T)
{
    if(T)
    {
        printf("%c ",T->data);
        printf("%c的兄弟：",T->data);
        CSTreeTraverse(T->nextsibling);
        printf("\n%c孩子：",T->data);
        CSTreeTraverse(T->firstchild);
    }
}