06 - 그림 1 연통 집 (25 점) [일 일 1 문제]

N 개의 정점 과 E 개의 변 이 있 는 무 방향 그림 을 지정 합 니 다. DFS 와 BFS 로 각각 모든 연결 집합 을 보 여 주 십시오.정점 을 0 에서 N - 1 번 으로 가정 하 다.검색 을 할 때, 우리 가 항상 번호 가 가장 작은 정점 에서 출발 하여 번호 가 증가 하 는 순서에 따라 인접 지점 에 접근한다 고 가정 합 니 다.
입력 형식:
첫 번 째 줄 을 입력 하여 정수 N 2 개 주기 (0)
출력 형식:
"{v 1 v 2... v k}" 형식 으로 줄 마다 연결 집합 을 출력 합 니 다. DFS 결 과 를 먼저 출력 하고 BFS 결 과 를 출력 합 니 다.
입력 예시:

8 6
0 7
0 1
2 0
4 1
2 4
3 5

출력 예시:

{ 0 1 4 2 7 }
{ 3 5 }
{ 6 }
{ 0 1 2 7 4 }
{ 3 5 }
{ 6 }

Code

#include 
#include 
#define MaxVertexNum 10

int Visited[MaxVertexNum];
int N;
typedef int Vertex; /*          ,    */
/*    */
typedef struct ENode *Edge;
struct ENode{
    Vertex V1,V2;
};

/*      */
typedef struct AdjNode *PtrToAdjNode;
struct AdjNode{
    Vertex AdjV;
    PtrToAdjNode Next;
};

/*        */
typedef struct VNode{
    PtrToAdjNode FirstEdge;
}AdjList[MaxVertexNum];

/*      */
typedef struct GNode *LGraph;
struct GNode{
    int Nv,Ne;
    AdjList G;
};

typedef struct QueueNode *Queue;
struct QueueNode{
    int Front,Rear;
    Vertex *Elements;
};

LGraph CreatGraph(int VexterNum);
void InsertEdge(LGraph Graph,Edge E);
LGraph BuildGraph();
void DFS(LGraph Graph,Vertex V,void (*Visit)(Vertex));
void BFS(LGraph Graph,Vertex S,void (*Visit)(Vertex));
Queue CreatQuene(int MaxSize);
void AddQ(Queue Q,Vertex V);
Vertex DeleteQ(Queue Q);
int IsEmpty(Queue Q);
void Visit(Vertex V);

int main()
{
    Vertex V;
    LGraph Graph = BuildGraph();
    for(V=0;V<MaxVertexNum;V++) Visited[V] = 0;
    for(V=0;V<N;V++)
    {
        if(!Visited[V])
        {
            printf("{ ");
            DFS(Graph,V,Visit);
            printf("}
");
        }
    }

    for(V=0;V<MaxVertexNum;V++) Visited[V] = 0;
    for(V=0;V<N;V++)
    {
        if(!Visited[V])
        {
            printf("{ ");
            BFS(Graph,V,Visit);
            printf("}
");
        }
    }
    return 0;
}

LGraph CreatGraph(int VexterNum)
{/*       VertexNum          */
    LGraph Graph;
    Graph = (LGraph)malloc(sizeof(struct GNode));
    Graph->Ne = 0;
    Graph->Nv = VexterNum;
    for(int V=0;V<Graph->Nv;V++)
    {
        Graph->G[V].FirstEdge = NULL;
    }
    return Graph;
}

void InsertEdge(LGraph Graph,Edge E)
{
    PtrToAdjNode NewNode,W;
    /*      , V1       ，    V2,  v1->v2*/
    NewNode = (PtrToAdjNode)malloc(sizeof(struct AdjNode));
    NewNode->AdjV = E->V2;
    /*remark:                     ，
                              ；
                     */
    if(!Graph->G[E->V1].FirstEdge)
    {

        NewNode->Next = Graph->G[E->V1].FirstEdge;
        Graph->G[E->V1].FirstEdge = NewNode;
    }
    else if(Graph->G[E->V1].FirstEdge&&!Graph->G[E->V1].FirstEdge->Next)
    {
        if(NewNode->AdjV < Graph->G[E->V1].FirstEdge->AdjV)
        {
            NewNode->Next = Graph->G[E->V1].FirstEdge;
            Graph->G[E->V1].FirstEdge = NewNode;
        }else{
            NewNode->Next = Graph->G[E->V1].FirstEdge->Next;
            Graph->G[E->V1].FirstEdge->Next = NewNode;
        }
    }
    else{
        for(W = Graph->G[E->V1].FirstEdge;W;W=W->Next)
        {
            if(!W->Next||(W->Next->AdjV > NewNode->AdjV))
            {
                NewNode->Next = W->Next;
                W->Next = NewNode;
                break;
            }
        }
    }
}

LGraph BuildGraph()
{
    Edge E1,E2;
    scanf("%d",&N);
    LGraph Graph = CreatGraph(N);
    scanf("%d",&Graph->Ne);
    E1 = (Edge)malloc(sizeof(struct ENode));
    E2 = (Edge)malloc(sizeof(struct ENode));
    for(int i=0;i<Graph->Ne;i++)
    {
        scanf("%d %d",&E1->V1,&E1->V2);
        InsertEdge(Graph,E1);
        E2->V1 = E1->V2;
        E2->V2 = E1->V1;
        InsertEdge(Graph,E2);
    }
    return Graph;
}
void Visit(Vertex V)
{
    printf("%d ",V);
}
void DFS(LGraph Graph,Vertex V,void (*Visit)(Vertex))
{
    PtrToAdjNode W;
    Visit(V);
    Visited[V] = 1;
    for(W = Graph->G[V].FirstEdge;W;W = W->Next)
    {
        if(!Visited[W->AdjV])
            DFS(Graph,W->AdjV,Visit);
    }
}

void BFS(LGraph Graph,Vertex S,void (*Visit)(Vertex))
{
    Vertex V;
    PtrToAdjNode W;
    Queue Q = CreatQuene(MaxVertexNum);

    Visit(S);
    Visited[S] = 1;
    AddQ(Q,S);

    while(!IsEmpty(Q))
    {
        V = DeleteQ(Q);
        for(W = Graph->G[V].FirstEdge;W;W = W->Next)
        {
            if(!Visited[W->AdjV])
            {
                Visit(W->AdjV);
                Visited[W->AdjV] = 1;
                AddQ(Q,W->AdjV);
            }
        }
    }
}

Queue CreatQuene(int MaxSize)
{
    Queue Q = (Queue)malloc(sizeof(struct QueueNode));
    Q->Elements = (int *)malloc(sizeof(int)*MaxSize);
    Q->Front = Q->Rear = 0;
    return Q;
}

void AddQ(Queue Q,Vertex V)
{
    Q->Elements[Q->Rear++] = V;
}

Vertex DeleteQ(Queue Q)
{
    return Q->Elements[Q->Front++];
}

int IsEmpty(Queue Q)
{
    return Q->Front==Q->Rear;
}