1. #include "stdio.h"    
    2. #include "stdlib.h"   
    3. #include "io.h"  
    4. #include "math.h"  
    5. #include "time.h"
    7. #define OK 1
    8. #define ERROR 0
    9. #define TRUE 1
    10. #define FALSE 0
    12. #define MAXSIZE 9 /* 存储空间初始分配量 */
    13. #define MAXEDGE 15
    14. #define MAXVEX 9
    15. #define INFINITY 65535
    17. typedef int Status;    /* Status是函数的类型,其值是函数结果状态代码,如OK等 */
    18. typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */
    20. typedef char VertexType; /* 顶点类型应由用户定义 */   
    21. typedef int EdgeType; /* 边上的权值类型应由用户定义 */
    23. /* 邻接矩阵结构 */
    24. typedef struct
    25. {
    26.     VertexType vexs[MAXVEX]; /* 顶点表 */
    27.     EdgeType arc[MAXVEX][MAXVEX];/* 邻接矩阵,可看作边表 */
    28.     int numVertexes, numEdges; /* 图中当前的顶点数和边数 */ 
    29. }MGraph;
    31. /* 邻接表结构****************** */
    32. typedef struct EdgeNode /* 边表结点 */ 
    33. {
    34.     int adjvex;    /* 邻接点域,存储该顶点对应的下标 */
    35.     int weight;        /* 用于存储权值,对于非网图可以不需要 */
    36.     struct EdgeNode *next; /* 链域,指向下一个邻接点 */ 
    37. }EdgeNode;
    39. typedef struct VertexNode /* 顶点表结点 */ 
    40. {
    41.     int in;    /* 顶点入度 */
    42.     char data; /* 顶点域,存储顶点信息 */
    43.     EdgeNode *firstedge;/* 边表头指针 */   
    44. }VertexNode, AdjList[MAXVEX];
    46. typedef struct
    47. {
    48.     AdjList adjList; 
    49.     int numVertexes,numEdges; /* 图中当前顶点数和边数 */
    50. }graphAdjList,*GraphAdjList;
    51. /* **************************** */
    53. /* 用到的队列结构与函数********************************** */
    54. /* 循环队列的顺序存储结构 */
    55. typedef struct
    56. {
    57.     int data[MAXSIZE];
    58.     int front;        /* 头指针 */
    59.     int rear;        /* 尾指针,若队列不空,指向队列尾元素的下一个位置 */
    60. }Queue;
    62. /* 初始化一个空队列Q */
    63. Status InitQueue(Queue *Q)
    64. {
    65.     Q->front=0;
    66.     Q->rear=0;
    67.     return  OK;
    68. }
    70. /* 若队列Q为空队列,则返回TRUE,否则返回FALSE */
    71. Status QueueEmpty(Queue Q)
    72. { 
    73.     if(Q.front==Q.rear) /* 队列空的标志 */
    74.         return TRUE;
    75.     else
    76.         return FALSE;
    77. }
    79. /* 若队列未满,则插入元素e为Q新的队尾元素 */
    80. Status EnQueue(Queue *Q,int e)
    81. {
    82.     if ((Q->rear+1)%MAXSIZE == Q->front)    /* 队列满的判断 */
    83.         return ERROR;
    84.     Q->data[Q->rear]=e;            /* 将元素e赋值给队尾 */
    85.     Q->rear=(Q->rear+1)%MAXSIZE;/* rear指针向后移一位置, */
    86.                                 /* 若到最后则转到数组头部 */
    87.     return  OK;
    88. }
    90. /* 若队列不空,则删除Q中队头元素,用e返回其值 */
    91. Status DeQueue(Queue *Q,int *e)
    92. {
    93.     if (Q->front == Q->rear)            /* 队列空的判断 */
    94.         return ERROR;
    95.     *e=Q->data[Q->front];                /* 将队头元素赋值给e */
    96.     Q->front=(Q->front+1)%MAXSIZE;    /* front指针向后移一位置, */
    97.                                     /* 若到最后则转到数组头部 */
    98.     return  OK;
    99. }
    100. /* ****************************************************** */
    104. void CreateMGraph(MGraph *G)
    105. {
    106.     int i, j;
    108.     G->numEdges=15;
    109.     G->numVertexes=9;
    111.     /* 读入顶点信息,建立顶点表 */ 
    112.     G->vexs[0]='A';
    113.     G->vexs[1]='B';
    114.     G->vexs[2]='C';
    115.     G->vexs[3]='D';
    116.     G->vexs[4]='E';
    117.     G->vexs[5]='F';
    118.     G->vexs[6]='G';
    119.     G->vexs[7]='H';
    120.     G->vexs[8]='I';
    123.     for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
    124.     {
    125.         for ( j = 0; j < G->numVertexes; j++)
    126.         {
    127.             G->arc[i][j]=0;
    128.         }
    129.     }
    131.     G->arc[0][1]=1;
    132.     G->arc[0][5]=1;
    134.     G->arc[1][2]=1; 
    135.     G->arc[1][8]=1; 
    136.     G->arc[1][6]=1; 
    138.     G->arc[2][3]=1; 
    139.     G->arc[2][8]=1; 
    141.     G->arc[3][4]=1;
    142.     G->arc[3][7]=1;
    143.     G->arc[3][6]=1;
    144.     G->arc[3][8]=1;
    146.     G->arc[4][5]=1;
    147.     G->arc[4][7]=1;
    149.     G->arc[5][6]=1; 
    151.     G->arc[6][7]=1; 
    154.     for(i = 0; i < G->numVertexes; i++)
    155.     {
    156.         for(j = i; j < G->numVertexes; j++)
    157.         {
    158.             G->arc[j][i] =G->arc[i][j];
    159.         }
    160.     }
    162. }
    164. /* 利用邻接矩阵构建邻接表 */
    165. void CreateALGraph(MGraph G,GraphAdjList *GL)
    166. {
    167.     int i,j;
    168.     EdgeNode *e;
    170.     *GL = (GraphAdjList)malloc(sizeof(graphAdjList));
    172.     (*GL)->numVertexes=G.numVertexes;
    173.     (*GL)->numEdges=G.numEdges;
    174.     for(i= 0;i <G.numVertexes;i++) /* 读入顶点信息,建立顶点表 */   
    175.     {
    176.         (*GL)->adjList[i].in=0;
    177.         (*GL)->adjList[i].data=G.vexs[i];
    178.         (*GL)->adjList[i].firstedge=NULL;     /* 将边表置为空表 */
    179.     }
    181.     for(i=0;i<G.numVertexes;i++) /* 建立边表 */
    182.     { 
    183.         for(j=0;j<G.numVertexes;j++)
    184.         {
    185.             if (G.arc[i][j]==1)
    186.             {
    187.                 e=(EdgeNode *)malloc(sizeof(EdgeNode));
    188.                 e->adjvex=j;                    /* 邻接序号为j */                         
    189.                 e->next=(*GL)->adjList[i].firstedge;    /* 将当前顶点上的指向的结点指针赋值给e */
    190.                 (*GL)->adjList[i].firstedge=e;        /* 将当前顶点的指针指向e */   
    191.                 (*GL)->adjList[j].in++;
    193.             }
    194.         }
    195.     }
    197. }
    199. Boolean visited[MAXSIZE]; /* 访问标志的数组 */
    201. /* 邻接表的深度优先递归算法 */
    202. void DFS(GraphAdjList GL, int i)
    203. {
    204.     EdgeNode *p;
    205.      visited[i] = TRUE;
    206.      printf("%c ",GL->adjList[i].data);/* 打印顶点,也可以其它操作 */
    207.     p = GL->adjList[i].firstedge;
    208.     while(p)
    209.     {
    210.          if(!visited[p->adjvex])
    211.              DFS(GL, p->adjvex);/* 对为访问的邻接顶点递归调用 */
    212.         p = p->next;
    213.      }
    214. }
    216. /* 邻接表的深度遍历操作 */
    217. void DFSTraverse(GraphAdjList GL)
    218. {
    219.     int i;
    220.      for(i = 0; i < GL->numVertexes; i++)
    221.          visited[i] = FALSE; /* 初始所有顶点状态都是未访问过状态 */
    222.     for(i = 0; i < GL->numVertexes; i++)
    223.          if(!visited[i]) /* 对未访问过的顶点调用DFS,若是连通图,只会执行一次 */ 
    224.             DFS(GL, i);
    225. }
    227. /* 邻接表的广度遍历算法 */
    228. void BFSTraverse(GraphAdjList GL)
    229. {
    230.     int i;
    231.     EdgeNode *p;
    232.     Queue Q;
    233.     for(i = 0; i < GL->numVertexes; i++)
    234.            visited[i] = FALSE;
    235.     InitQueue(&Q);
    236.        for(i = 0; i < GL->numVertexes; i++)
    237.        {
    238.         if (!visited[i])
    239.         {
    240.             visited[i]=TRUE;
    241.             printf("%c ",GL->adjList[i].data);/* 打印顶点,也可以其它操作 */
    242.             EnQueue(&Q,i);
    243.             while(!QueueEmpty(Q))
    244.             {
    245.                 DeQueue(&Q,&i);
    246.                 p = GL->adjList[i].firstedge;    /* 找到当前顶点的边表链表头指针 */
    247.                 while(p)
    248.                 {
    249.                     if(!visited[p->adjvex])    /* 若此顶点未被访问 */
    250.                      {
    251.                          visited[p->adjvex]=TRUE;
    252.                         printf("%c ",GL->adjList[p->adjvex].data);
    253.                         EnQueue(&Q,p->adjvex);    /* 将此顶点入队列 */
    254.                     }
    255.                     p = p->next;    /* 指针指向下一个邻接点 */
    256.                 }
    257.             }
    258.         }
    259.     }
    260. }
    262. int main(void)
    263. {    
    264.     MGraph G;  
    265.     GraphAdjList GL;    
    266.     CreateMGraph(&G);
    267.     CreateALGraph(G,&GL);
    269.     printf("\n深度遍历:");
    270.     DFSTraverse(GL);
    271.     printf("\n广度遍历:");
    272.     BFSTraverse(GL);
    273.     return 0;
    274. }