数据结构学习—图的遍历

#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;
typedef int Boolean;

typedef char VertexType;
typedef int EdgeType;

#define MAXSIZE 9
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITY 65535

typedef struct //图的结构定义 
{
    VertexType vexs[MAXVEX]; //顶点表
    EdgeType arc[MAXVEX][MAXVEX]; //邻接矩阵，边表
    int numVertexes, numEdges; //图中节点数、边数
}MGraph; 


typedef struct //循环队列结构
{
    int data[MAXSIZE];
    int front;
    int rear;
}Queue;  


Status InitQueue(Queue *Q)  //队列初始化
{
    Q->front=0;
    Q->rear=0;
    return  OK;
}


Status QueueEmpty(Queue Q)  //队列置空
{
    if(Q.front==Q.rear)
        return TRUE;
    else
        return FALSE;
}


Status EnQueue(Queue *Q,int e)  //队列插入元素
{
    if ((Q->rear+1)%MAXSIZE == Q->front)
        return ERROR;
    Q->data[Q->rear]=e;
    Q->rear=(Q->rear+1)%MAXSIZE;
    return  OK;
}


Status DeQueue(Queue *Q,int *e) //出队
{
    if (Q->front == Q->rear)
        return ERROR;
    *e=Q->data[Q->front];
    Q->front=(Q->front+1)%MAXSIZE;
    return  OK;
}



void CreateMGraph(MGraph *G)  //建表
{
    int i, j;

    G->numEdges=15;  //图的顶点数、边数
    G->numVertexes=9;


    G->vexs[0]='A'; //定义图的顶点
    G->vexs[1]='B';
    G->vexs[2]='C';
    G->vexs[3]='D';
    G->vexs[4]='E';
    G->vexs[5]='F';
    G->vexs[6]='G';
    G->vexs[7]='H';
    G->vexs[8]='I';


    for (i = 0; i < G->numVertexes; i++)  //初始化图
    {
        for ( j = 0; j < G->numVertexes; j++)
        {
            G->arc[i][j]=0;
        }
    }

    G->arc[0][1]=1; //设置边
    G->arc[0][5]=1;

    G->arc[1][2]=1;
    G->arc[1][8]=1;
    G->arc[1][6]=1;

    G->arc[2][3]=1;
    G->arc[2][8]=1;

    G->arc[3][4]=1;
    G->arc[3][7]=1;
    G->arc[3][6]=1;
    G->arc[3][8]=1;

    G->arc[4][5]=1;
    G->arc[4][7]=1;

    G->arc[5][6]=1;

    G->arc[6][7]=1;


    for(i = 0; i < G->numVertexes; i++)  //邻接矩阵是对称矩阵
    {
        for(j = i; j < G->numVertexes; j++)
        {
            G->arc[j][i] =G->arc[i][j];
        }
    }

}

Boolean visited[MAXVEX]; //是否被访问过的标志


void DFS(MGraph G, int i) //深度优先搜索
{
    int j;
    visited[i] = TRUE;
    printf("%c ", G.vexs[i]);
    for(j = 0; j < G.numVertexes; j++)
        if(G.arc[i][j] == 1 && !visited[j])
            DFS(G, j);
}


void DFSTraverse(MGraph G)  
{
    int i;
    for(i = 0; i < G.numVertexes; i++)
        visited[i] = FALSE;
    for(i = 0; i < G.numVertexes; i++)
        if(!visited[i])
            DFS(G, i);
}


void BFSTraverse(MGraph G)
{
    int i, j;
    Queue Q;
    for(i = 0; i < G.numVertexes; i++)
        visited[i] = FALSE;
    InitQueue(&Q);
    for(i = 0; i < G.numVertexes; i++)
    {
        if (!visited[i])
        {
            visited[i]=TRUE;
            printf("%c ", G.vexs[i]);
            EnQueue(&Q,i);
            while(!QueueEmpty(Q))
            {
                DeQueue(&Q,&i);
                for(j=0;j<G.numVertexes;j++)
                {

                    if(G.arc[i][j] == 1 && !visited[j])
                    {
                        visited[j]=TRUE;
                        printf("%c ", G.vexs[j]);
                        EnQueue(&Q,j);				
                    }
                }
            }
        }
    }
}


int main(void)
{
    MGraph G;
    CreateMGraph(&G);
    printf("\n深度遍历：");
    DFSTraverse(G);
    printf("\n广度遍历：");
    BFSTraverse(G);
    return 0;
}