1 深度优先搜索算法

深度优先搜索(Depth First Search)遍历类似于树的先序遍历，是树的先序遍历的推广。
采用的数据结构是(正)邻接链表。

算法思想：
设初始状态时图中所有顶点未被访问，则：
(1):从图中某个顶点出发，访问;然后找到的一个邻接顶点；
(2):从出发，深度优先搜索访问和相邻接且未被访问的所有顶点。
(3):转(1)，直到和相邻接的所有顶点都被访问为止；
(4):继续选取图中未被访问的顶点作为起始顶点，转(1)，直到图中所有顶点都被访问为止。

算法实现：
由算法思想知，这是一个递归的过程。因此先设计一个从某个顶点为开始深度优先搜索的函数，便于调用。
在遍历整个图时，可以对图中每一个未访问的顶点执行所定义的函数。
定义一个全局变量，记录每个结点是否访问过，初始为FALSE。

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

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

typedef struct LinkNode {
    int adjvex;//邻接点在头结点数组中的位置(下标)
    int info;// 与边或弧相关的信息, 如权值
    struct LinkNode *nextarc;//指向下一个表结点
} LinkNode;/*表结点类型定义 */

typedef struct VexNode {
    char data; // 顶点信息
    LinkNode *firstarc; // 指向第一个表结点
} VexNode;/* 顶点结点类型定义 */

typedef struct {
    GraphKind kind;/*图的种类标志 */
    int vexnum;//顶点数
    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未访问过的邻接顶点出发深度优先搜索
    }

}

void DFS_traverse_Graph(ALGraph *G) {//深度优先搜索主函数
    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函数。
其实质就是对每个顶点查找邻接顶点的过程，取决于存储结构。
当图有e条边，其时间复杂度为O(e),总时间复杂度为O(n+e)。

2 广度优先搜索算法

广度优先搜索(Breadth First Search) 遍历类似于树的按层次遍历的过程。

算法思想：
设初始状态图中的所有顶点未被访问，则
(1)从图中某个顶点出发，访问；
(2)访问的所有相邻接且未被访问的所有顶点,,,；
(3)以,,,的次序，以依次作为，转(1)；
(4)继续选取图中未被访问顶点作为起始顶点，转(1)，直到图中所有顶点都被访问为止。

算法实现：
为了标记图中顶点是否被访问过，同样需要一个访问标记数组；其次，为了依次访问与相邻接的各个顶点，需要附加一个队列来保存访问的相邻接的顶点。

#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;//邻接点在头结点数组中的位置(下标)
    int info;// 与边或弧相关的信息, 如权值
    struct LinkNode *nextarc;//指向下一个表结点
} LinkNode;/*表结点类型定义 */

typedef struct VexNode {
    char data; // 顶点信息
    LinkNode *firstarc; // 指向第一个表结点
} VexNode;/* 顶点结点类型定义 */

typedef struct {
    GraphKind kind;/*图的种类标志 */
    int vexnum;//顶点数
    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++) {//非连通图需要循环每个结点
        if (visited[i] == 0) {//没有访问过
            queue->elem[++queue->rear] = i;//i入队
            while (queue->front != queue->rear) {//队不空一直循环
                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);
}

用广度优先搜索算法遍历图与深度优先搜索算法遍历图的唯一区别是邻接点搜索次序不同。
广度优先搜索算法遍历图的总时间复杂度是O(n+e)。