그림 의 깊이 우선 옮 겨 다 니 기

그림 을 옮 겨 다 니 는 방법 은 주로 두 가지 가 있 습 니 다. 깊이 우선 옮 겨 다 니 기 (Depth First Search) 깊이 우선 옮 겨 다 니 기 와 넓이 우선 옮 겨 다 니 기 (Breadth First Search) 입 니 다.그림 의 깊이 는 나무의 순서 와 유사 하 게 옮 겨 다 니 며 그림 의 넓이 는 나무의 차원 과 유사 하 게 옮 겨 다 닌 다.
그림 의 깊이 를 우선 적 으로 옮 겨 다 니 며 그림 의 옮 겨 다 니 기 (무 방향 그림 기반 인접 표 저장 구조)

#pragma once
#include
#include
#include

#define Max_size 10
#define T char

typedef struct Edges
{
    int dex;//     
    struct Edges *link;//         
}Edges;

typedef struct Vertex
{
    T data;//    
    Edges *adj;//        
}Vertex;

typedef struct Graph_table
{
    int MaxVertices;//    
    int NmuVertices; //   
    int NumEdges;    //  
    Vertex *NnodeTable;//       ，
}Graph_table;

void InitGraph(Graph_table *gt)
{
    gt->MaxVertices = Max_size;
    gt->NmuVertices = gt->NumEdges = 0;
    gt->NnodeTable = (Vertex*)malloc(sizeof(Vertex)*(gt->MaxVertices));
    assert(NULL != gt->NnodeTable);
    for(int i= 0;i<gt->MaxVertices;++i)
    {
        gt->NnodeTable[i].adj = NULL;
    }
}

void InsertVertex(Graph_table *gt,T x)//

{

    if(gt->NmuVertices >= gt->MaxVertices)
        return;
    gt->NnodeTable[gt->NmuVertices++].data = x;
}

void Show(Graph_table *gt)
{
    Edges *p;
    for(int i=0;i<gt->NmuVertices;++i)
    {
        printf("%d , %c : ",i,gt->NnodeTable[i].data);
        p = gt->NnodeTable[i].adj;
        while(NULL != p)
        {
            printf("%d --> ",p->dex);
            p = p->link;
        }
        printf("NULL.
");
    }
    printf("
");
}

int Getpos(Graph_table *gt,T x)    //       
{
    for(int i= 0;i<gt->NmuVertices;++i)
    {
        if(gt->NnodeTable[i].data == x)
            return i;
    }
    return -1;  //        
}

void InsertEdge(Graph_table *gt,T x,T y)  //   
{
    int p1 = Getpos(gt,x);
    int p2 = Getpos(gt,y);
    if(p1==-1 || p2==-1)
        return;
    Edges *s;
    s = (Edges *)malloc(sizeof(Edges));//     
    assert(s != NULL);
    s->dex = p2;      //x-->y  x y  
    s->link = gt->NnodeTable[p1].adj;
    gt->NnodeTable[p1].adj = s;

    s = (Edges *)malloc(sizeof(Edges));//     
    assert(s != NULL);
    s->dex = p1;      //y-->x y  x  
    s->link = gt->NnodeTable[p2].adj;
    gt->NnodeTable[p2].adj = s;

    gt->NumEdges++;
}

typedef int Boolean;
Boolean visited[Max_size];
void DFS(Graph_table *gt,int i)  //            
{
    Edges *p;
    visited[i] = true;
    printf("%c ",gt->NnodeTable[i].data);
    p = gt->NnodeTable[i].adj;
    while(p)
    {
        if(!visited[p->dex])
            DFS(gt,p->dex);
        p = p->link;
    }
}

void DFSvisit(Graph_table *gt)  //        
{
    int i;
    for(i=0;i<gt->NmuVertices;++i)
    {
        visited[i] = false;
    }
    for(i=0;i<gt->NmuVertices;++i)
    {
        if(!visited[i])
            DFS(gt,i);
    }
}


    
#include"Graph_DFS.h"

void main()
{
    Graph_table gt;   //      
    InitGraph(&gt);    //       
    InsertVertex(&gt,'A');//       
    InsertVertex(&gt,'B');
    InsertVertex(&gt,'C');
    InsertVertex(&gt,'D');
    InsertVertex(&gt,'E');
    Show(&gt);

    InsertEdge(&gt,'A','B');//      
    InsertEdge(&gt,'A','D');
    InsertEdge(&gt,'B','C');
    InsertEdge(&gt,'B','E');
    InsertEdge(&gt,'C','D');
    InsertEdge(&gt,'C','E');
    Show(&gt);

    DFSvisit(&gt);//        
}