1 深度優(yōu)先搜索算法

深度優(yōu)先搜索(Depth First Search)遍歷類似于樹的先序遍歷赖捌，是樹的先序遍歷的推廣。
采用的數(shù)據(jù)結構是(正)鄰接鏈表西采。

算法思想：
設初始狀態(tài)時圖中所有頂點未被訪問，則：
(1):從圖中某個頂點出發(fā)鞠柄，訪問;然后找到的一個鄰接頂點侦高；
(2):從出發(fā)，深度優(yōu)先搜索訪問和相鄰接且未被訪問的所有頂點厌杜。
(3):轉(1)矫膨，直到和相鄰接的所有頂點都被訪問為止；
(4):繼續(xù)選取圖中未被訪問的頂點作為起始頂點期奔，轉(1)侧馅，直到圖中所有頂點都被訪問為止。

算法實現(xiàn)：
由算法思想知呐萌，這是一個遞歸的過程馁痴。因此先設計一個從某個頂點為開始深度優(yōu)先搜索的函數(shù)，便于調用肺孤。
在遍歷整個圖時罗晕，可以對圖中每一個未訪問的頂點執(zhí)行所定義的函數(shù)。
定義一個全局變量赠堵，記錄每個結點是否訪問過小渊，初始為FALSE。

#include <stdio.h>
#include <stdlib.h>

#define MAX_VEX 30
typedef enum {
    DG, AG, WDG, WAG
} GraphKind;

typedef struct LinkNode {
    int adjvex;//鄰接點在頭結點數(shù)組中的位置(下標)
    int info;// 與邊或弧相關的信息, 如權值
    struct LinkNode *nextarc;//指向下一個表結點
} LinkNode;/*表結點類型定義 */

typedef struct VexNode {
    char data; // 頂點信息
    LinkNode *firstarc; // 指向第一個表結點
} VexNode;/* 頂點結點類型定義 */

typedef struct {
    GraphKind kind;/*圖的種類標志 */
    int vexnum;//頂點數(shù)
    VexNode AdjList[MAX_VEX];//鄰接表
} ALGraph;/* 圖的結構定義 */

int visited[MAX_VEX];//0未訪問茫叭，1已訪問

void DFS(ALGraph *G, int v) {
    LinkNode *p = G->AdjList[v].firstarc;//鏈表的第一個結點
    visited[v] = 1;//設置已訪問標志
    visit(v);//訪問頂點v
    while (p != NULL) {
        if (visited[p->adjvex] == 0) {//未訪問
            DFS(G, p->adjvex);
        }
        p = p->nextarc;//從v未訪問過的鄰接頂點出發(fā)深度優(yōu)先搜索
    }

}

void DFS_traverse_Graph(ALGraph *G) {//深度優(yōu)先搜索主函數(shù)
    for (int i = 0; i < G->vexnum; i++) {//訪問標志初始化
        visited[i] = 0;
    }
    for (int i = 0; i < G->vexnum; i++) {
        if (visited[i]) {
            DFS(G, i);
        }
    }
}

算法分析：
遍歷時酬屉，對圖的每個頂點至多調用一次DFS函數(shù)。
其實質就是對每個頂點查找鄰接頂點的過程揍愁，取決于存儲結構呐萨。
當圖有e條邊，其時間復雜度為O(e),總時間復雜度為O(n+e)莽囤。

2 廣度優(yōu)先搜索算法

廣度優(yōu)先搜索(Breadth First Search) 遍歷類似于樹的按層次遍歷的過程谬擦。

算法思想：
設初始狀態(tài)圖中的所有頂點未被訪問，則
(1)從圖中某個頂點出發(fā)朽缎，訪問惨远；
(2)訪問的所有相鄰接且未被訪問的所有頂點,,,；
(3)以,,,的次序话肖，以依次作為北秽，轉(1)；
(4)繼續(xù)選取圖中未被訪問頂點作為起始頂點狼牺，轉(1)羡儿，直到圖中所有頂點都被訪問為止。

算法實現(xiàn)：
為了標記圖中頂點是否被訪問過是钥，同樣需要一個訪問標記數(shù)組掠归；其次缅叠，為了依次訪問與相鄰接的各個頂點，需要附加一個隊列來保存訪問的相鄰接的頂點虏冻。

#include <stdio.h>
#include <stdlib.h>

#define MAX_VEX 30

int visited[MAX_VEX];

typedef struct Queue {
    int elem[MAX_VEX];
    int front, rear;
} Queue;//定義一個隊列保存將要訪問的頂點

typedef enum {
    DG, AG, WDG, WAG//有向圖肤粱，無向圖，帶權有向圖厨相，帶權無向圖
} GraphKind;

typedef struct LinkNode {
    int adjvex;//鄰接點在頭結點數(shù)組中的位置(下標)
    int info;// 與邊或弧相關的信息, 如權值
    struct LinkNode *nextarc;//指向下一個表結點
} LinkNode;/*表結點類型定義 */

typedef struct VexNode {
    char data; // 頂點信息
    LinkNode *firstarc; // 指向第一個表結點
} VexNode;/* 頂點結點類型定義 */

typedef struct {
    GraphKind kind;/*圖的種類標志 */
    int vexnum;//頂點數(shù)
    VexNode AdjList[MAX_VEX];//鄰接表
} ALGraph;/* 圖的結構定義 */

void visit(char c) {
    printf("%c ", c);
}

void BFS_traverse_graph(ALGraph *G) {
    int w;
    LinkNode *node;
    Queue *queue = (Queue *) malloc(sizeof(Queue));
    queue->front = queue->rear = 0;//建立空隊列并初始化
    for (int i = 0; i < G->vexnum; i++) {
        visited[i] = 0;//訪問標志初始化
    }
    for (int i = 0; i < G->vexnum; i++) {//非連通圖需要循環(huán)每個結點
        if (visited[i] == 0) {//沒有訪問過
            queue->elem[++queue->rear] = i;//i入隊
            while (queue->front != queue->rear) {//隊不空一直循環(huán)
                w = queue->elem[++queue->front];//出隊
                visited[w] = 1;//置訪問標志
                visit(G->AdjList[w].data);//進行訪問
                node = G->AdjList[w].firstarc;
                while (node != NULL) {
                    if (visited[node->adjvex] == 0) {
                        queue->elem[++queue->rear] = node->adjvex;
                    }
                    node = node->nextarc;
                }
            }
        }
    }
}

ALGraph *createGraph() {
    ALGraph *G = (ALGraph *) malloc(sizeof(ALGraph));
    printf("圖的種類標識：\n");
    scanf("%d", &G->kind);
    G->vexnum = 0;
    return G;
}

int locateVex(ALGraph *G, char ch) {
    for (int i = 0; i < G->vexnum; i++) {
        if (G->AdjList[i].data == ch) {
            return (i);
        }
    }
    return (-1);/* 圖中無此頂點*/
}

int addVex(ALGraph *G, char ch) {
    int k;
    if (G->vexnum >= MAX_VEX) {
        printf("Vertex Overflow !\n");
        return (-1);
    }
    if (locateVex(G, ch) != -1) {
        printf("Vertex has existed !\n");
        return (-1);
    }
    G->AdjList[G->vexnum].data = ch;
    G->AdjList[G->vexnum].firstarc = NULL;
    k = ++G->vexnum;
    return k;
}

int addArc(ALGraph *G, char ch1, char ch2, int weight) {
    int k = locateVex(G, ch1);
    int j = locateVex(G, ch2);
    if (k == -1 || j == -1) {
        printf("Arc’s Vertex do not exist!\n");
        return (-1);
    }
    LinkNode *p = (LinkNode *) malloc(sizeof(LinkNode));
    p->adjvex = k;
    p->info = weight;
    LinkNode *q = (LinkNode *) malloc(sizeof(LinkNode));
    p->adjvex = j;
    q->info = weight;
    if (G->kind == AG || G->kind == WAG) {//無向圖领曼，用頭插入法插入到兩個單鏈表
        p->nextarc = G->AdjList[k].firstarc;
        G->AdjList[k].firstarc = p;
        q->nextarc = G->AdjList[j].firstarc;
        G->AdjList[j].firstarc = q;
    } else {
        p->nextarc = G->AdjList[k].firstarc;
        G->AdjList[k].firstarc = p;   /*建立正鄰接鏈表用 */

//        q->nextarc = G->AdjList[j].firstarc;
//        G->AdjList[j].firstarc = q;/*建立逆鄰接鏈表用 */
    }
}

int main() {
    ALGraph *G = createGraph();
    addVex(G, 'a');
    addVex(G, 'b');
    addVex(G, 'c');
    addVex(G, 'd');
    addVex(G, 'e');
    addArc(G, 'a', 'b', 0);
    addArc(G, 'a', 'd', 0);
    addArc(G, 'b', 'c', 0);
    addArc(G, 'd', 'e', 0);
    addArc(G, 'c', 'e', 0);
    BFS_traverse_graph(G);
}

用廣度優(yōu)先搜索算法遍歷圖與深度優(yōu)先搜索算法遍歷圖的唯一區(qū)別是鄰接點搜索次序不同。
廣度優(yōu)先搜索算法遍歷圖的總時間復雜度是O(n+e)蛮穿。