图的遍历包括广度优先搜索和深度优先搜索。

广度优先搜索

广度优先搜索类似于树的层次遍历，利用队列实现

队列结构设计：

1
2
3
4
5
typedef struct QueueNode{
    struct AdjNode* node;   /*顶点*/
    struct QueueNode* next;
    struct QueueNode* pre;
}QueueNode;

队列相关操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/*循环队列*/
QueueNode* initQueue()
{
    QueueNode* Q=(QueueNode*)malloc(sizeof(QueueNode*));
    Q->next=Q;
    Q->pre=Q;
    Q->node=NULL;
    return Q;
}
int isEmpty(QueueNode *Q)
{
    if(Q->next==Q)
        return 1;
    else
        return 0;
}
/*入队列*/
void enqueue(QueueNode *Q,AdjNode *node)
{
    /*在队列头入队列*/
    QueueNode* queuenode=(QueueNode*)malloc(sizeof(QueueNode*));
    queuenode->node=node;

    queuenode->next=Q->next;
    queuenode->pre=Q;
    Q->next->pre=queuenode;
    Q->next=queuenode;
}
/*出队列*/
QueueNode* dequeue(QueueNode *Q)
{
    if(!isEmpty(Q)){
        struct QueueNode* node=Q->next;
        Q->next=Q->next->next;
        Q->next->pre=Q;
        return node;
    }
    return NULL;
}

广度优先搜索实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/*宽度优先搜索*/
void bfs(Graph *graph,QueueNode* Q,char start,int *visited){
   
    struct AdjNode* adjnode=findNode(graph,start);
    if(!adjnode){
        return;
    }
    enqueue(Q,adjnode);
    while(!isEmpty(Q)){
        struct QueueNode* qnode=dequeue(Q);
        struct AdjNode* node=qnode->node;
        /*访问邻边*/
        for(;node;node=node->next){
            int index=findNodeIndex(graph,node->vtxname);
            if(visited[index]!=1){
                printf("%c->",graph->list[index]->vtxname);//访问节点
                enqueue(Q,findNode(graph,node->vtxname));                
                visited[index]=1;
            }
        }
    }
    printf("\n");
}
void graphBfs(Graph *graph,char start){
    int visited[graph->vtxnum];/*记录顶点是否被访问*/
    memset(visited, 0, sizeof(int) * graph->vtxnum);/*初始化visited数组*/
    QueueNode *Q=initQueue();
    bfs(graph,Q,start,visited);
    for(int i=0;i<graph->vtxnum;i++){
        if(visited[i]==0){
            bfs(graph,Q,graph->list[i]->vtxname,visited);//环图
        }
    }
}

宽度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*深度优先搜索*/
void dfs(Graph *graph,char start,int *visited){
    struct AdjNode* node=findNode(graph,start);
    for(;node;node=node->next){
        int index=findNodeIndex(graph,node->vtxname);
        if(visited[index]==0){
             printf("%c->",node->vtxname);
             visited[index]=1;
            dfs(graph,node->vtxname,visited);
        }
   }
}
void graphDfs(Graph *graph,char start){
    int visited[graph->vtxnum];/*记录顶点是否被访问*/
    memset(visited, 0, sizeof(int) * graph->vtxnum);/*初始化visited数组*/
    dfs(graph,start,visited);
    for(int i=0;i<graph->vtxnum;i++){
        if(visited[i]==0){
            dfs(graph,graph->list[i]->vtxname,visited);//环图
        }
    }
}