图的邻接表存储和遍历

图是一种经典的数据结构，在实际的生产过程中有广泛的应用，本文将结合代码简单介绍有关图的相关基础知识点。

基本概念

图(Graph)是一种较线性表和树更为复杂的结构。图有两个重要元素构成，顶点和弧边，弧边是相关顶点之间的连线，具有方向性，根据方向性的有无，图可以分为有向图和无向图。

(1) 无向图。在一个图中，如果任意两个顶点构成的偶对（vi, vj）∈E 是无序的，即顶点之间的连线是没有方向的，则称该图为无向图。如下图就是一个无向图。
(2) 有向图。在一个图中，如果任意两个顶点构成的偶对（vi, vj）∈E 是有序的，即顶点之间的连线是有方向的，则称该图为有向图。

无向图

抽象数据类型定义

ADT Graph{
数据对象：n=n是具有相同特征的数据元素集合，称为顶点集。
数据关系：DR={<v,w>|v,w∈n且<v,w>表示从v指向w的弧
}

邻接表存储

邻接表是图的一种主要存储结构，它由表头结点和表结点两部分组成，其中每个顶点均对应一个存储在数组中的表头结点。简言之，对图的每个顶点建立一个容器（n个顶点建立n个容器），第i个容器中的结点包含顶点Vi的所有邻接顶点。
在有向图中，描述每个点向别的节点连的边（点a->点b这种情况）；在无向图中，描述每个点所有的边(点a-点b这种情况)。

相比于邻接矩阵存储，邻接表更适用于 边稀疏 的情况，能节省很多空间。

邻接表

代码实现

顶点和弧边的定义

#define MAX_VERTEX_NUM 20

// 有向图，有向网，无向图，无向网
typedef enum { DG, DN, UDG, UDN } GraphKind;

// 顶点类型
typedef char VertexType;

// 边表节点
typedef struct ArcNode
{
    int adjvex; // 该边所指节点位置
    struct ArcNode *nextarc; //下一个邻接点（下一条弧）
    //InfoType *info;
    // 该边相关信息的指针，通常指带权图的权值，
    // 此处做一些简化，直接定义为权值
    int weight;
} ArcNode, *Arc;

// 顶点表节点
typedef struct VexNode
{
    VertexType data; // 节点
    ArcNode *firstarc; // 边表头节点指针
} VexNode, AdjList[MAX_VERTEX_NUM];

// 邻接表存储图
typedef struct
{
    AdjList vertices; // 顶点数组
    int vexnum, arcnum; // 顶点数、边数
    GraphKind kind; //图的种类标志
} ALGraph;

图的创建之节点插入

使用头插法添加节点

// 邻接表头插，(i,j)为弧的两个顶点，带权图增加一个w，记录权值
Status HeadInsertArc(ALGraph *G, int i, int j, int weight)
{
    ArcNode *e;
    e = (ArcNode *)malloc(sizeof(ArcNode));
    e->adjvex = j;
    e->weight = weight; // 对于带权图增加一个w，记录权值
    e->nextarc = G->vertices[i].firstarc;
    G->vertices[i].firstarc = e;
    return 0;
}

深度优先遍历

在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。

非递归深度搜索 DFS：

//深度搜索DFS--非递归（需要将之前访问过的邻接点存入栈）
void DFS_Non_Recursion(ALGraph *G, int i, int *visited)
{
    SqStack S; InitStack(&S);
    ArcNode *p;
    if (0 == visited[i])
    {
        visited[i] = 1;
        printf("(%d)%c ", i, G->vertices[i].data);
        PushStack(&S, i);
        while(!StackEmpty(&S))
        {
            // 栈顶为当前层的前驱
            p = G->vertices[GetTop(&S)].firstarc;
            while (p)
            {
                // 当前层该节点未访问，没有走到头则访问
                if (0 == visited[p->adjvex])
                {
                    visited[p->adjvex] = 1;
                    printf("(%d)%c ", p->adjvex, G->vertices[p->adjvex].data);
                    PushStack(&S, p->adjvex);
                    // 继续到下一层
                    p = G->vertices[p->adjvex].firstarc;
                }
                // 当前层该节点已访问，已经走到头，则访问该节点相同前驱的下一个节点
                else
                {
                    p = p->nextarc;
                }
            }
            // 当前层没有节点了或者当前层节点全部已访问
            // 栈顶未当前层的前驱（上一层），弹出栈顶，回到上一层
            PopStack(&S, &i);
        }
    }
}

递归深度搜索 DFS：

// 深度优先搜索DFS--递归
void DFS_Recursion(ALGraph *G, int i, int *visited)
{
    ArcNode *p;
    if (0 == visited[i])
    {
        visited[i] = 1;
        printf("(%d)%c ", i, G->vertices[i].data);
        p = G->vertices[i].firstarc;
        while (p)
        {
            DFS_Recursion(G, p->adjvex, visited);
            p = p->nextarc;
        }
    }
}

广度优先遍历

从图中某个顶点V0出发，并访问此顶点；然后访问V0的各个未曾访问的邻接点W1，W2，…,Wk;然后,依次从W1,W2,…,Wk出发访问各自未被访问的邻接点；重复步骤第二个步骤，直到全部顶点都被访问为止。

// 广度优先搜索BFS
void BFS(ALGraph *G, int i, int *visited)
{
    SqQueue Q; InitQueue(&Q);
    ArcNode *p;
    if (0 == visited[i])
    {
        visited[i] = 1;
        printf("(%d)%c ", i, G->vertices[i].data);
        EnQueue(&Q, i); // 记录顶点位置即可
        while(!QueueEmpty(&Q))
        {
            DeQueue(&Q, &i); // 复用i
            p = G->vertices[i].firstarc;
            while(p)
            {
                if (0 == visited[p->adjvex])
                {
                    visited[p->adjvex] = 1;
                    printf("(%d)%c ", p->adjvex, G->vertices[p->adjvex].data);
                    EnQueue(&Q, p->adjvex);
                }
                p = p->nextarc;
            }
        }
    }
}

完整代码可参见：GitHub

DONE！