범위 우선

트 리 와 유사 한 계층 을 우선 검색 합 니 다.그림 의 특정한 정점 에서 출발 하여 모든 정점 을 옮 겨 다 닐 때 모든 인접 점 을 차례대로 옮 겨 다 닌 다음 에 이 인접 점 에서 출발 하여 똑 같이 그들의 인접 점 을 순서대로 방문 합 니 다.이 과정 에 따라 그림 에 있 는 모든 방문 한 정점 의 인접 점 이 접근 할 때 까지 합 니 다.
마지막 으로 해 야 할 작업 은 그림 에 접근 되 지 않 은 정점 이 있 는 지 확인 하 는 것 입 니 다. 있 으 면 이 정점 을 시작 으로 위 와 같은 과정 을 반복 하 는 것 입 니 다.
범위 우선 검색 의 실현 은 대기 열 이라는 특수 한 데이터 구 조 를 통 해 코드 를 실현 해 야 합 니 다.

#include 
#include 
#include 

#define MAX_VERTEX_NUM 20//     
#define VRType int//         
#define InfoType char//            
#define VertexType int//      
bool visited[MAX_VERTEX_NUM];//    ，        
typedef struct Queue
{
    VertexType data;
    struct Queue *next;
}Queue;
typedef struct 
{
    VRType adj;
    InfoType info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct 
{
    VertexType vexs[MAX_VERTEX_NUM];
    AdjMatrix arcs;
    int vexnum,arcnum;
}MGgraph;

int LocateVex(MGgraph *G,VertexType v)
{
    int i=0;
    for(;ivexnum;i++)
    {
        if(G->vexs[i]==v)
        {
            break;
        }
    }
    if(i>=G->vexnum)
    {
        printf("       
");
        return -1;
    }
    return i;
}

void CreateUDG(MGgraph *G)
{
    scanf("%d%d",&(G->vexnum),&(G->arcnum));
    for(int i=0;ivexnum;i++)
    {
        scanf("%d",&(G->vexs[i]));
    }
    for(int i=0;ivexnum;i++)
    {
        for(int j=0;jvexnum;j++)
        {
            G->arcs[i][j].adj=0;
            G->arcs[i][j].info=NULL;
        }
    }
    for(int k=0;karcnum;k++)
    {
        int v1,v2;
        int i=LocateVex(G,v1);
        int j=LocateVex(G,v2);
        if(i==-1||j==-1)
        {
            printf("       
");
            return;
        }
        G->arcs[i][j].adj=1;
        G->arcs[j][i].adj=1;
    }
}

int FirstAdjVex(MGgraph G,int v)
{
    for(int i=0;inext=NULL;
}
//    v   
void EnQueue(Queue **Q,VertexType v)
{
    Queue *element=(Queue*)malloc(sizeof(Queue));
    element->data=v;
    element->next=NULL;
    Queue *temp=(*Q);
    while(temp->next!=NULL)
    {
        temp=temp->next;
    }
    temp->next=element;
}
//       
void DeQueue(Queue **Q,int *u)
{
    *u=(*Q)->next->data;
    (*Q)->next=(*Q)->next->next;
}
//        
bool QueueEmpty(Queue *Q)
{
    if(Q->next==NULL)
    {
        return true;
    }
    return false;
}

//BFS
void BFSTraverse(MGgraph G)
{
    int v;
    for(v=0;v=0;w=NextAdjVex(G,u))
                {
                    if(!visited[w])
                    {
                        visited[w]=true;
                        visitVex(G,w);
                        EnQueue(&Q,G.vexs[w]);
                    }
                }
            }
        }
    }
}

int main()
{
    MGgraph G;
    CreateUDG(&G);
    BFSTraverse(G);
    return 0;
}