1. /*
    2.     在采用邻接表存储的图上进行广度优先遍历/深度优先遍历
    3.     分析：我们知道邻接表上的顶点所连接的节点都是它的相邻节点，而对于广度优先遍历来说，类似于层次遍历，就是要把所有的邻接点进行访问，
    4.           所以我们需要从第一个节点开始访问它的所有邻接点，还有需要注意的是，当我们把邻接点访问后，需要依次访问邻接点的邻接点，这就需要
    5.           用队列将我们访问过得邻接点入队，这和层次遍历一样，也只有这样，我们才能访问所有的节点。当然，在这个过程中，会有重复访问的情况，
    6.           所以我们需要用一个数组来记录节点的访问情况，已访问置true
    8.           对于深度优先遍历，顾名思义，我们会把每一个节点“榨干”，“顺藤摸瓜”，同样我们需要一个访问标记数组，而对于深度优先遍历，
    9.           我们将采用递归的方式来进行。
    10. */
    11. //创建邻接表图结构  分为边表节点结构 顶点表节点结构 图结构
    13. #define MAXSIZE 100
    14. #define TYPE int
    15. //边表结构 
    16. typedef struct EdgeNode {//边表结点
    17.     int index;//该边所指向的顶点的位置,在顶点数组里面的位置信息
    18.     int weight;//权值
    19.     EdgeNode *next;//下一个邻接边
    20. }EdgeNode;
    22. typedef struct VertexNode {//顶点表节点
    23.     int info;//顶点信息
    24.     EdgeNode *firstEdge;//指向第一条依附该顶点的边的指针
    25. }VertexNode, Adjlist[MAXSIZE];
    27. typedef struct {
    28.     Adjlist adjlist;//顶点数组
    29.     int numE, numV;//边数、顶点数
    30. }ALGraph;
    31. //队列结构(我们采用顺序队列)
    32. struct Squeue {
    33.     TYPE *arr;
    34.     int front, rear;
    35. };
    36. #include <stdio.h>
    37. #include <stdlib.h>
    38. void BFSBegin(ALGraph *G) {
    39.     void BFS(ALGraph *, int *, int);
    40.     int *visited = (int *)malloc(sizeof(int)*G->numV);//设置标记数组
    41.     for (int i = 0; i < G->numV; i++) {
    42.         visited[i] = 0;
    43.     }
    44.     for (int i = 1; i < G->numV; i++) {//从第一个节点开始
    45.         if (!visited[i]) {
    46.             BFS(G, visited, i);
    47.         }
    48.     }
    49. }
    50. void BFS(ALGraph *G, int *visited, int v) {//开始广度遍历
    51.     //声明有关队列的函数
    52.     Squeue *createQueue(int);
    53.     bool isEmpty(Squeue *);
    54.     bool enQueue(Squeue *, TYPE, int);
    55.     bool deQueue(Squeue *sq, TYPE *data, int maxSize);
    56.     Squeue *sq;
    57.     sq = createQueue(G->numV);//创建队列
    58.     printf("%c ", G->adjlist[v].info);//访问传进来的顶点
    59.     enQueue(sq, v, G->numV);//入队
    60.     visited[v] = 1;//置为已访问
    61.     while (!isEmpty(sq)) {//队列不空，取出队首元素，进行访问
    62.         TYPE top;
    63.         deQueue(sq, &top, G->numV);
    64.         for (EdgeNode *w = G->adjlist[top].firstEdge; w; w = w->next) {//依次将当前节点的边表入队，和层次遍历一致
    65.             if (!visited[w->index]) {
    66.                 printf("%c ", G->adjlist[w->index].info);
    67.                 visited[w->index] = 1;
    68.                 enQueue(sq, w->index, G->numV);
    70.             }
    71.         }
    72.     }
    74. }
    75. void DFSBegin(ALGraph *G) {
    76.     void DFS(ALGraph *, int *, VertexNode *, int);
    77.     int *visited = (int *)malloc(sizeof(int)*G->numV);//设置标记数组
    78.     for (int i = 0; i < G->numV; i++) {
    79.         visited[i] = 0;
    80.     }
    81.     for (int i = 0; i < G->numV; i++) {//从第一个节点开始“顺藤摸瓜”
    82.         if (!visited[i]) {
    83.             DFS(G, visited, &G->adjlist[i], i);
    84.         }
    85.     }
    86. }
    87. void DFS(ALGraph *G, int *visited, VertexNode *v, int index) {
    88.     printf("%c ", v->info);//打印传入的节点
    89.     visited[index] = 1;//置访问为1
    90.     for (EdgeNode *w = v->firstEdge; w; w = w->next) {
    91.         if (w) {//如果有邻接点，传入DFS
    92.             if (!visited[w->index]) {//未访问
    93.                 DFS(G, visited, &G->adjlist[w->index], w->index);
    94.             }
    95.         }
    97.     }
    98. }
    99. int main() {
    100.     ALGraph *graph = (ALGraph *)malloc(sizeof(ALGraph *));
    101.     //声明函数
    102.     void createGraph(ALGraph *);
    103.     void createGraphInFile(ALGraph *);
    104.     void dispGraph(ALGraph *);
    105.     //创建图
    106.     createGraphInFile(graph);
    107.     //打印图
    108.     dispGraph(graph);
    109.     //广度优先遍历
    110.     //BFSBegin(graph);
    111.     //深度优先遍历
    112.     DFSBegin(graph);
    113.     return 0;
    114. }