第 20 关 | 图算法 —— 中看不中用：2.白银挑战——图的存储与遍历-灵析社区

与前面的链表、树等相比，图的存储和遍历要复杂非常多，本文，我们就来看一下如何实现？

图的类型多、表示方式多，相关算法也很多，实现又过于复杂，多语言实现难度太大了。这些算法一般理解就好，不需要面试的时候手写，因此本文，我们只提供C/C++版本的实现。

1. 图的实现方式

图的表示方式比前面学习的几种结构都复杂，常见的有两种：二维数组表示(邻接矩阵)；链表表示(邻接表)。

邻接矩阵是表示图形中顶点之间相邻关系的矩阵，对于 n 个顶点的图而言，矩阵是的 row 和 col 表示的是 1....n个点，矩阵中的1表示有连线，0表示没有连线。

在上图的邻接矩阵需要为每个顶点都分配n个边的空间，其实有很多边都是不存在，因此存储效率比较低。如果图比较稀疏的话，会造成大量的空间浪费，比如在地铁图中，一个站点多的也就与几个站相连，少的只有一个，而使用邻接矩阵则需要为每个站点都分配N个空间。

邻接表的实现只关心存在的边，不关心不存在的边，因此没有空间浪费，邻接表由数组+链表组成。

如果表示方式不同，自然定义图和后续操作的方式也不一样，因此这也是图算法不经常出现面试中的原因之一。

1.1. 图的邻接矩阵表示法

所谓的邻接矩阵就是使用上述的二维矩阵的方式来存储图。在实际中为了方便管理，我们会增加一些额外的定义。

1.1.1. 基本结构定义

我们现在可以看到如何来实现各种类型的图吧。

#define MAX_VERtEX_NUM 20                   //顶点的最大个数
#define VRType int                          //表示顶点之间的关系的变量类型
#define InfoType char                       //存储弧或者边额外信息的指针变量类型
#define VertexType int                      //图中顶点的数据类型
typedef enum { DG, DN, UDG, UDN }GraphKind;       //枚举图的 4 种类型
typedef struct {
    VRType adj;                             //对于无权图，用 1 或 0 表示是否相邻；对于带权图，直接为权值。
    InfoType* info;                         //弧或边额外含有的信息指针
}ArcCell, AdjMatrix[MAX_VERtEX_NUM][MAX_VERtEX_NUM];

typedef struct {
    VertexType vexs[MAX_VERtEX_NUM];        //存储图中顶点数据
    AdjMatrix arcs;                         //二维数组，记录顶点之间的关系
    int vexnum, arcnum;                     //记录图的顶点数和弧（边）数
    GraphKind kind;                         //记录图的种类
}MGraph;

在不存在相同元素时，我们可以根据顶点本身数据，判断出顶点在二维数组中的位置，代码如下：

int LocateVex(MGraph* G, VertexType v) {
    //遍历一维数组，找到变量v
    for (int i = 0;int i = 0 i < G->vexnum; i++) {
        if (G->vexs[i] == v) {
            break;
        }
    }
    //如果找不到，输出提示语句，返回-1
    if (i == G->vexnum) {
        printf("no such vertex.\n");
        return -1;
    }
    return i;
}

如果我们想将图中所有元素都打印出来，方法如下：

void PrintGrapth(MGraph G)
{
    int i, j;
    for (i = 0; i < G.vexnum; i++)
    {
        for (j = 0; j < G.vexnum; j++)
        {
            printf("%d ", G.arcs[i][j].adj);
        }
        printf("\n");
    }
}

1.1.2. 构造有向图和无向图

图有有向和无向两种基本的方式，无向图如下所示，就是只要两个结点V1 和V2之间有连线，则就可以相互访问。

而有向图就是如下所示，带方向箭头的，例如V1 和V2之间有连线，则只能从V1到V2，而不能反向直接访问。

void CreateDG(MGraph* G) {
    int i, j;
    //输入图含有的顶点数和弧的个数
    scanf("%d,%d", &(G->vexnum), &(G->arcnum));
    //依次输入顶点本身的数据
    for (i = 0; i < G->vexnum; i++) {
        scanf("%d", &(G->vexs[i]));
    }
    //初始化二维矩阵，全部归0，指针指向NULL
    for (i = 0; i < G->vexnum; i++) {
        for (j = 0; j < G->vexnum; j++) {
            G->arcs[i][j].adj = 0;
            G->arcs[i][j].info = NULL;
        }
    }
    //在二维数组中添加弧的数据
    for (i = 0; i < G->arcnum; i++) {
        int v1, v2;
        int n, m;
        //输入弧头和弧尾
        scanf("%d,%d", &v1, &v2);
        //确定顶点位置
        n = LocateVex(G, v1);
        m = LocateVex(G, v2);
        //排除错误数据
        if (m == -1 || n == -1) {
            printf("no this vertex\n");
            return;
        }
        //将正确的弧的数据加入二维数组
        G->arcs[n][m].adj = 1;
    }
}

我们再看一下无向图的实现：

void CreateDN(MGraph* G) {
    int i, j;
    scanf("%d,%d", &(G->vexnum), &(G->arcnum));
    for (i = 0; i < G->vexnum; i++) {
        scanf("%d", &(G->vexs[i]));
    }
    for (i = 0; i < G->vexnum; i++) {
        for (j = 0; j < G->vexnum; j++) {
            G->arcs[i][j].adj = 0;
            G->arcs[i][j].info = NULL;
        }
    }
    for (i = 0; i < G->arcnum; i++) {
        int v1, v2;
        int n, m;
        scanf("%d,%d", &v1, &v2);
        n = LocateVex(G, v1);
        m = LocateVex(G, v2);
        if (m == -1 || n == -1) {
            printf("no this vertex\n");
            return;
        }
        G->arcs[n][m].adj = 1;
        G->arcs[m][n].adj = 1;//无向图的二阶矩阵沿主对角线对称
    }
}

1.1.3. 构造带权重的有向图和无向图

在上面小节，我们构造的图中的连线，每条线的权重都是一样的，都是1。但是在实际中这是不可能的 ，有些连线代价高一些。有些低一些，因此不同的线权重是不一样的。

例如，使用上述程序存储左图的有向网时，存储的两个数组如右图所示：

在程序中，构建无向网和有向网时，对于之间没有边或弧的顶点，相应的二阶矩阵中存放的是 0。目的只是为了方便查看运行结果，而实际上如果顶点之间没有关联，它们之间的距离应该是无穷大（∞）。

void CreateUDG(MGraph* G) {
    int i, j;
    scanf("%d,%d", &(G->vexnum), &(G->arcnum));
    for (i = 0; i < G->vexnum; i++) {
        scanf("%d", &(G->vexs[i]));
    }
    for (i = 0; i < G->vexnum; i++) {
        for (j = 0; j < G->vexnum; j++) {
            G->arcs[i][j].adj = 0;
            G->arcs[i][j].info = NULL;
        }
    }
    for (i = 0; i < G->arcnum; i++) {
        int v1, v2, w;
        int n, m;
        scanf("%d,%d,%d", &v1, &v2, &w);
        n = LocateVex(G, v1);
        m = LocateVex(G, v2);
        if (m == -1 || n == -1) {
            printf("no this vertex\n");
            return;
        }
        G->arcs[n][m].adj = w;
    }
}

我们再构造无向网，和无向图唯一的区别就是二阶矩阵中存储的是权值

void CreateUDN(MGraph* G) {
    int i, j;
    scanf("%d,%d", &(G->vexnum), &(G->arcnum));
    for (i = 0; i < G->vexnum; i++) {
        scanf("%d", &(G->vexs[i]));
    }
    for (i = 0; i < G->vexnum; i++) {
        for (j = 0; j < G->vexnum; j++) {
            G->arcs[i][j].adj = 0;
            G->arcs[i][j].info = NULL;
        }
    }
    for (i = 0; i < G->arcnum; i++) {
        int v1, v2, w;
        int m, n;
        scanf("%d,%d,%d", &v1, &v2, &w);
        m = LocateVex(G, v1);
        n = LocateVex(G, v2);
        if (m == -1 || n == -1) {
            printf("no this vertex\n");
            return;
        }
        G->arcs[n][m].adj = w;
        G->arcs[m][n].adj = w;//矩阵对称
    }
}

总结一下，本节主要详细介绍了使用数组存储图的方法，在实际操作中使用更多的是链式存储结构，例如邻接表、十字链表和邻接多重表，这三种存储图的方式放在下一节重点去讲。

1.2. 邻接表计算顶点的出度和入度

在有向图（网）中，顶点的入度指的是以当前顶点一端为弧头的弧的数量；顶点的出度指的是以当前顶点一端为弧尾的弧的数量。

在邻接表中计算某个顶点的出度是非常简单的，只需要在顺序表中找到该顶点，然后计算该顶点所在链表中其它结点的数量，即为该顶点的出度。例如，图 1b) 中为 V1 构建的链表中有 2 个结点，因此 V1 的出度就是 2。

在邻接表中计算某个顶点的入度，有两种实现方案：

1遍历顺序表，找到该顶点，获取该顶点所在顺序表中的下标（假设为 K）。然后遍历所有单链表中的结点，统计数据域为 K 的结点数量，即为该顶点的入度。

2建立一个逆邻接表，表中各个顶点的链表中记录的是以当前顶点一端为弧头的弧的信息。比如说，图 1a) 对应的逆邻接表如下图所示：

逆邻接表

以 V1 顶点为例，数据域为 3 的结点记录的是 <V4, V1> 这条弧。

对于具有 n 个顶点和 e 条边的无向图，邻接表中需要构建 n 个首元结点和 2e 个表示边的结点；对于具有 n 个顶点和 e 条弧的有向图，邻接表需要构建 n 个首元结点和 e 个表示弧的结点。

当图中边或者弧稀疏时，用邻接表比前一节介绍的邻接矩阵更加节省空间，边或弧相关信息较多时更是如此。

最后，用邻接表存储有向图的 C 语言程序如下所示：

#include<stdio.h>
#include<stdlib.h>
#define  MAX_VERTEX_NUM 20//最大顶点个数
#define  VertexType char//图中顶点的类型

typedef struct ArcNode {
    int adjvex;//存储弧，即另一端顶点在数组中的下标
    struct ArcNode* nextarc;//指向下一个结点
}ArcNode;

typedef struct VNode {
    VertexType data;//顶点的数据域
    ArcNode* firstarc;//指向下一个结点
}VNode, AdjList[MAX_VERTEX_NUM];//存储各链表首元结点的数组

typedef struct {
    AdjList vertices;  //存储图的邻接表
    int vexnum, arcnum;//图中顶点数以及弧数
}ALGraph;

void CreateGraph(ALGraph * graph) {
    int i, j;
    char VA, VB;
    ArcNode* node = NULL;
    printf("输入顶点的数目：\n");
    scanf("%d", &(graph->vexnum));
    printf("输入弧的数目：\n");
    scanf("%d", &(graph->arcnum));
    scanf("%*[^\n]"); scanf("%*c");
    printf("输入各个顶点的值：\n");
    for (i = 0; i < graph->vexnum; i++) {
        scanf("%c", &(graph->vertices[i].data));
        getchar();
        graph->vertices[i].firstarc = NULL;
    }
    //输入弧的信息，并为弧建立结点，链接到对应的链表上
    for (i = 0; i < graph->arcnum; i++) {
        printf("输入弧(a b 表示弧 a->b)：\n");
        scanf("%c %c", &VA, &VB);
        getchar();
        node = (ArcNode*)malloc(sizeof(ArcNode));
        node->adjvex = '#';
        node->nextarc = NULL;
        //存储弧另一端顶点所在顺序表中的下标
        for (j = 0; j < graph->vexnum; j++) {
            if (VB == graph->vertices[j].data) {
                node->adjvex = j;
                break;
            }
        }
        //如果未在顺序表中找到另一端顶点，则构建图失败
        if (node->adjvex == '#') {
            printf("弧信息输入有误\n");
            exit(0);
        }
        //将结点添加到对应的链表中
        for (j = 0; j < graph->vexnum; j++) {
            if (VA == graph->vertices[j].data) {
                //将 node 结点以头插法的方式添加到相应链表中
                node->nextarc = graph->vertices[j].firstarc;
                graph->vertices[j].firstarc = node;
                break;
            }
        }
        if (j == graph->vexnum) {
            printf("弧信息输入有误\n");
            exit(0);
        }
    }
}

//计算某个顶点的入度
int InDegree(ALGraph graph, char V) {
    int i, j, index = -1;
    int count = 0;
    //找到 V 在顺序表中的下标
    for (j = 0; j < graph.vexnum; j++) {
        if (V == graph.vertices[j].data) {
            index = j;
            break;
        }
    }
    if (index == -1) {
        return -1;
    }
    //遍历每个单链表，找到存储 V 下标的结点，并计数
    for (j = 0; j < graph.vexnum; j++) {
        ArcNode* p = graph.vertices[j].firstarc;
        while (p) {
            if (p->adjvex == index) {
                count++;
            }
            p = p->nextarc;
        }
    }
    return count;
}

//计算某个顶点的出度
int OutDegree(ALGraph graph, char V) {
    int j;
    int count = 0;
    for (j = 0; j < graph.vexnum; j++) {
        if (V == graph.vertices[j].data) {
            ArcNode* p = graph.vertices[j].firstarc;
            while (p) {
                count++;
                p = p->nextarc;
            }
            break;
        }
    }
    //如果查找失败，返回 -1 表示计算失败
    if (j == graph.vexnum) {
        return -1;
    }
    return count;
}

1.3. 图的其他存储方式

上面我们采用二维矩阵的方式存储图，除此之外还有两种方式也能存储，分别是邻接矩阵和十字链法，本小节，我们就来看一下。

1.3.1. 邻接表存储矩阵

邻接表（Adjacency List）是图的一种链式存储结构，既可以存储无向图（网），也可以存储有向图（网）。

邻接表存储图的核心思想是：将图中的所有顶点存储到顺序表中（也可以是链表），同时为各个顶点配备一个单链表，用来存储和当前顶点有直接关联的边或者弧（边的一端是该顶点或者弧的弧尾是该顶点）。

举个简单的例子，下图是一张有向图和它对应的邻接表：

有向图和它对应的邻接表

以顶点 V1 为例，它对应的单链表中有两个结点，存储的值分别是 2 和 1。2 是 V3 顶点在顺序表中的位置下标，存储 2 的结点就表示 <V1, V3> 这条弧；同理，1 是 V2 顶点在顺序表中的位置下标，存储 1 的结点就表示 <V1, V2> 这条弧。

也就是说，邻接表中存储边或弧的方法，就是存储边或弧另一端顶点在顺序表中的位置下标。

继续分析图 1b) 中的另外 3 个单链表：

●V2：由于图中不存在以 V2 为弧尾的弧，所以不需要为 V2 构建链表；

●V3：以 V3 为弧尾的弧只有 <V3, V4>，V4 在顺序表对应的下标为 3，因此单链表中只有 1 个结点，结点中存储 3 来表示 <V3, V4>。

●V4：以 V4 为弧尾的弧只有 <V4, V1>，V1 在顺序表对应的下标为 0，因此单链表中只有 1 个结点，结点中存储 0 来表示 <V4, V1>。

实际上，邻接表就是由一个顺序表和多个单链表组成的，顺序表用来存储图中的所有顶点，各个单链表存储和当前顶点有直接关联的边或弧。

存储顶点的顺序表，内部各个空间的结构如下图所示：

data 为数据域，用来存储各个顶点的信息；next 为指针域，用来链接下一个结点。

对于无向图或者有向图来说，单链表中存储边或弧的结点也可以用图 2 所示的结构来表示，data 数据域存储边或弧另一端顶点在顺序表中的下标，next 指针域用来链接下一个结点。对于无向网或者有向网来说，结点可以用下图所示的结构来表示：

adjvex 数据域用来存储边或弧另一端顶点在顺序表中的下标；next 指针域用来链接下一个结点；info 指针域用来存储有关边或弧的其它信息，比如边或弧的权值。

用 C 语言表示邻接表的实现代码如下：

#define  MAX_VERTEX_NUM 20//图中顶点的最大数量
#define  VertexType int//图中顶点的类型
#define  InfoType int*//图中弧或者边包含的信息的类型
typedef struct ArcNode{
    int adjvex;//存储边或弧，即另一端顶点在数组中的下标
    struct ArcNode * nextarc;//指向下一个结点
    InfoType info;//记录边或弧的其它信息
}ArcNode;
typedef struct VNode{
    VertexType data;//顶点的数据域
    ArcNode * firstarc;//指向下一个结点
}VNode,AdjList[MAX_VERTEX_NUM];//存储各链表首元结点的数组
typedef struct {
    AdjList vertices;//存储图的邻接表
    int vexnum,arcnum;//记录图中顶点数以及边或弧数
    int kind;//记录图的种类
}ALGraph;

以上各个结构体中的成员并非一成不变，根据实际场景的需要，可以修改它们的数据类型，还可以适当地删减。

基于上述定义，我们可以再次实现前面说的有向图、无向图、以及带权重的图等相关代码，这里我们就不再实现了。

1.3.2. 邻接表存储矩阵

存储有向图（网），可以使用邻接表或者逆邻接表结构，也可以使用本节讲解的十字链表结构。

用邻接表存储有向图（网），可以快速计算出某个顶点的出度，但计算入度的效率不高。反之，用逆邻接表存储有向图（网），可以快速计算出某个顶点的入度，但计算出度的效率不高。

那么有没有一种存储结构，可以快速计算出有向图（网）中某个顶点的入度和出度呢？答案是肯定的，十字链表就是这样的一种存储结构。

十字链表（Orthogonal List）是一种专门存储有向图（网）的结构，它的核心思想是：将图中的所有顶点存储到顺序表（也可以是链表）中，同时为每个顶点配备两个链表，一个链表记录以当前顶点为弧头的弧，另一个链表记录以当前顶点为弧尾的弧。

举个简单的例子，用十字链表结构存储图 1a) 中的有向图，图的存储状态如图 1b) 所示：

观察图 1b)，顺序表中的各个存储空间分为 3 部分，各个链表中的结点空间分为 4 部分。

顺序表中的空间用来存储图中的顶点，结构如下图所示：

图 2 存储顶点的结构

各部分的含义分别是：

●data 数据域：用来存储顶点的信息；

●firstin 指针域：指向一个链表，链表中记录的都是以当前顶点为弧头的弧的信息；

●firstout 指针域：指向另一个链表，链表中记录的是以当前顶点为弧尾的弧的信息。链表的结点用来存储图中的弧，结构如下图所示：

图 3: 存储弧信息的结点结构

各部分的含义分别是：

●tailvex数据域：存储弧尾一端顶点在顺序表中的位置下标；

●headvex 数据域：存储弧头一端顶点在顺序表中的位置下标；

●hlink 指针域：指向下一个以当前顶点作为弧头的弧；

●tlink 指针域：指向下一个以当前顶点作为弧尾的弧；

●info 指针：存储弧的其它信息，例如有向网中弧的权值。如果不需要存储其它信息，可以省略。在十字链表结构中，如果想计算某个顶点的出度，就统计 firstout 所指链表中的结点数量，每找到一个结点，再根据它的 tlink 指针域寻找下一个结点，直到最后一个结点。同样的道理，如果想计算某个顶点的入度，就统计 firstin 所指链表中的结点数量，每找到一个结点，再根据它的 hlink 指针域寻找下一个结点，直到最后一个结点。

以图 1b) 中的 V1 顶点为例，计算出度的过程是：

• 根据 V1 顶点的 firstout 指针，找到存储 <V1, V2> 弧的结点；
• 根据 <V1, V2> 弧结点中的 tlink 指针，找到存储 <V1, V3> 弧的结点；
• 由于 <V1, V3> 弧结点的 tlink 指针为 NULL，因此只找到了 2 个弧，V1 顶点的出度就为 2。计算 V1 顶点入度的过程是：
• 根据 V1 顶点的 firstin 指针，找到存储 <V4, V1> 弧的结点；
• 由于 <V4, V1> 弧结点的 hlink 指针为 NULL，因此只找到了 1 个弧，V1 顶点的入度就为 1。

如果你已经学会了邻接表和逆邻接表，可以将十字链表想象成邻接表和逆邻接表的结合体。

构建图的十字链表结构，对应的 C 语言代码如下：

#define  MAX_VERTEX_NUM 20 //图中顶点的最大数量
#define  InfoType int*     //表示弧额外信息的数据类型
#define  VertexType char    //图中顶点的数据类型
//表示链表中存储弧的结点
typedef struct ArcBox {
    int tailvex, headvex;          //弧尾、弧头对应顶点在顺序表中的位置下标
    struct ArcBox* hlik, * tlink;  //hlik指向下一个以当前顶点为弧头的弧结点；
    //tlink 指向下一个以当前顶点为弧尾的弧结点；
    //InfoType info;               //存储弧相关信息的指针
}ArcBox;

//表示顺序表中的各个顶点
typedef struct VexNode {
    VertexType data;              //顶点的数据域
    ArcBox* firstin, * firstout;  //指向以该顶点为弧头和弧尾的链表首个结点
}VexNode;

//表示十字链表存储结构
typedef struct {
    VexNode xlist[MAX_VERTEX_NUM];  //存储顶点的顺序表
    int vexnum, arcnum;             //记录图的顶点数和弧数
}OLGraph;

以图 1a) 为例，十字链表结构存储此图的完整 C 语言程序如下所示：

#include<stdio.h>
#define  MAX_VERTEX_NUM 20 //图中顶点的最大数量
#define  InfoType int*     //表示弧额外信息的数据类型
#define  VertexType char    //图中顶点的数据类型
//表示链表中存储弧的结点
typedef struct ArcBox {
    int tailvex, headvex;          //弧尾、弧头对应顶点在顺序表中的位置下标
    struct ArcBox* hlik, * tlink;  //hlik指向下一个以当前顶点为弧头的弧结点；
    //tlink 指向下一个以当前顶点为弧尾的弧结点；
    //InfoType info;               //存储弧相关信息的指针
}ArcBox;

//表示顺序表中的各个顶点
typedef struct VexNode {
    VertexType data;              //顶点的数据域
    ArcBox* firstin, * firstout;  //指向以该顶点为弧头和弧尾的链表首个结点
}VexNode;

//表示十字链表存储结构
typedef struct {
    VexNode xlist[MAX_VERTEX_NUM];  //存储顶点的顺序表
    int vexnum, arcnum;             //记录图的顶点数和弧数
}OLGraph;

int LocateVex(OLGraph* G, VertexType v) {
    int i;
    //遍历一维数组，找到变量v
    for (i = 0; i < G->vexnum; i++) {
        if (G->xlist[i].data == v) {
            break;
        }
    }
    //如果找不到，输出提示语句，返回 -1
    if (i > G->vexnum) {
        printf("no such vertex.\n");
        return -1;
    }
    return i;
}

//构建十字链表存储结构
void CreateDG(OLGraph* G) {
    int i, j, k;
    VertexType v1, v2;
    ArcBox* p = NULL;
    //输入有向图的顶点数和弧数
    scanf("%d %d", &(G->vexnum), &(G->arcnum));
    getchar();
    //使用一维数组存储顶点数据，初始化指针域为NULL
    for (i = 0; i < G->vexnum; i++) {
        scanf("%c", &(G->xlist[i].data));
        getchar();
        G->xlist[i].firstin = NULL;
        G->xlist[i].firstout = NULL;
    }
    //存储图中的所有弧
    for (k = 0; k < G->arcnum; k++) {
        scanf("%c %c", &v1, &v2);
        getchar();
        //确定v1、v2在数组中的位置下标
        i = LocateVex(G, v1);
        j = LocateVex(G, v2);
        //建立弧的结点
        p = (ArcBox*)malloc(sizeof(ArcBox));
        p->tailvex = i;
        p->headvex = j;
        //采用头插法插入新的p结点
        p->hlik = G->xlist[j].firstin;
        p->tlink = G->xlist[i].firstout;
        G->xlist[j].firstin = G->xlist[i].firstout = p;
    }
}

//计算某顶点的入度
int indegree(OLGraph* G, VertexType x) {
    int i;
    int num = 0;
    //遍历整个顺序表
    for (i = 0; i < G->vexnum; i++) {
        //找到目标顶点
        if (x == G->xlist[i].data) {
            //从该顶点的 firstin 指针所指的结点开始遍历
            ArcBox* p = G->xlist[i].firstin;
            while (p)
            {
                num++;
                //遍历 hlink 指针指向的下一个结点
                p = p->hlik;
            }
            break;
        }
    }
    if (i == G->vexnum) {
        printf("图中没有指定顶点\n");
        return -1;
    }
    return num;
}

//计算某顶点的出度
int outdegree(OLGraph* G, VertexType x) {
    int i;
    int num = 0;
    //遍历整个顺序表
    for (i = 0; i < G->vexnum; i++) {
        //找到目标顶点
        if (x == G->xlist[i].data) {
            //从该顶点的 firstout 指针所指的结点开始遍历
            ArcBox* p = G->xlist[i].firstout;
            while (p)
            {
                num++;
                //遍历 tlink 指针指向的下一个结点
                p = p->tlink;
            }
            break;
        }
    }
    if (i == G->vexnum) {
        printf("图中没有指定顶点\n");
        return -1;
    }
    return num;
}

//删除十字链表结构
//每个顶点配备两个链表，选定一个链表（比如 firstout 所指链表），删除每个顶点中 firstout 所指链表上的结点
void DeleteDG(OLGraph* G) {
    int i;
    ArcBox* p = NULL, * del = NULL;
    for (i = 0; i < G->vexnum; i++) {
        p = G->xlist[i].firstout;
        while (p) {
            del = p;
            p = p->tlink;
            free(del);
        }
        //将第 i 个位置的两个指针全部置为 NULL，能有效避免出现野指针
        G->xlist[i].firstout = NULL;
        G->xlist[i].firstin = NULL;
    }
}

2. 图的遍历

与树一样 ，图有深度优先和层次遍历两种方式，但是图没有根， 因此更多时候将层次遍历称为广度优先遍历BFS。

2.1. 图的深度优先搜索

深度优先搜索（Depth First Search）简称深搜或者 DFS，是遍历图存储结构的一种算法，既适用于无向图（网），也适用于有向图（网）。

所谓图的遍历，简单理解就是逐个访问图中的顶点，确保每个顶点都只访问一次。

首先通过一个样例，给大家讲解深度优先搜索算法是如何实现图的遍历的。

图 1 无向图的整个过程是：

1. 初始状态下，无向图中的所有顶点都是没有被访问过的，因此可以任选一个顶点出发，遍历整个无向图。
   
   假设从 V1 顶点开始，先访问 V1 顶点，如下图所示：

2.  紧邻 V1 的顶点有两个，分别是 V2 和 V3，它们都没有被访问过，从它们中任选一个，比如访问 V2，如下图所示：

3.  紧邻 V2 的顶点有三个，分别是 V1、V4 和 V5，尚未被访问的有 V4 和 V5，从它们中任选一个，比如访问 V4，如下图所示：

4.  紧邻 V4 的顶点有两个，分别是 V2 和 V8，只有 V8 尚未被访问，因此访问 V8，如下图所示：

5.  紧邻 V8 的顶点有两个，分别是 V4 和 V5，只有 V5 尚未被访问，因此访问 V5，如下图所示：

6.  和 V5 相邻的顶点有两个，分别是 V2 和 V8，它们都已经访问过了。也就是说，此时从 V5 出发，找不到任何未被访问的顶点了。

这种情况下，深度优先搜索算法会回退到之前的顶点，查看先前有没有漏掉的、尚未访问的顶点：

• 从 V5 回退到 V8，找不到尚未访问的顶点；
• 从 V8 回退到 V4，还是找不到尚未访问的顶点；
• 从 V4 回退到 V2，也还是找不到尚未访问的顶点；
• 从 V2 回退到 V1，发现 V3 还没有被访问。于是，下一个要访问的顶点就是 V3，如下图所示：

7.  紧邻 V3 的顶点有三个，分别是 V1、V6 和 V7，尚未访问的有 V6 和 V7，因此从它们中任选一个，比如访问 V6，如下图所示：

8.  紧邻 V6 的顶点有两个，分别是 V3 和 V7，只有 V7 还没有访问，因此访问 V7，如下图所示：

9.  紧邻 V7 顶点有 V6 和 V3，但它们都已经访问过了，此时面临的情况和第 6 步完全一样，深度优先搜索算法的解决方法也是一样的：

• 从 V7 回退到 V6，依然找不到尚未访问的顶点；
• 从 V6 回退到 V3，依然找不到尚未访问的顶点；
• 从 V3 回退到 V1，依然找不到尚未访问的顶点；V1 是遍历图的起始顶点，回退到 V1 还找不到尚未访问的顶点，意味着以 V1 顶点为突破口，能访问的顶点全部已经访问完了。这种情况下，深度优先搜索算法会从图的所有顶点中重新选择一个尚未访问的顶点，从该顶点出发查找尚未访问的其它顶点。

从图 9 可以看到，图中已经没有尚未访问的顶点了，此时深度优先搜索算法才执行结束。

对于连通图来说，深度优先搜索算法从一个顶点出发就能访问图中所有的顶点。但是对于非连通图来说，深度优先搜索算法必须从各个连通分量中选择一个顶点出发，才能访问到所有的顶点。

所谓深度优先搜索，就是从图中的某个顶点出发，不停的寻找相邻的、尚未访问的顶点：

• 如果找到多个，则任选一个顶点，然后继续从该顶点出发；
• 如果一个都没有找到，则回退到之前访问过的顶点，看看是否有漏掉的；假设从顶点 V 出发，则最终还会回退到顶点 V。此时，深度优先搜索算法会从所有顶点中重新找一个尚未访问的顶点，如果能找到，则以同样的方式继续寻找其它未访问的顶点；如果找不到，则算法执行结束。
  
  通常情况下，深度优先搜索算法访问图中顶点的顺序是不唯一的，即顶点的访问序列可能有多种（≥1）。

图的存储结构有很多种，大体上可以分为顺序存储和链式存储（又细分为邻接表结构、十字链表结构和邻接多重表结构），各个存储结构有自己的特点。选用不同的存储结构，深度优先搜索算法的具体实现不同，但算法的思想是不变的。

这里以图的顺序存储结构为例，深度优先搜索算法的 C 语言实现代码如下：

程序中，为了确保每个顶点只访问一次，借助了一个名为 visited 的一维数组，专门用来存储各个顶点的访问状态，用 0 表示未被访问，用 1 表示已经访问过。visited 数组中的访问状态和 vexs 数组中存储的顶点是一一对应的，比如 vexs[1] 顶点的访问状态就记录在 visited[1] 的位置。

2.2. 图的广度优先遍历

广度优先搜索（Breadth First Search）简称广搜或者 BFS，是遍历图存储结构的一种算法，既适用于无向图（网），也适用于有向图（网）。

所谓图的遍历，简单理解就是逐个访问图中的顶点，确保每个顶点都只访问一次。

首先通过一个样例，给大家讲解广度优先搜索算法是如何实现图的遍历的。

使用广度优先搜索算法，遍历图 1 中无向图的过程是：

1. 初始状态下，图中所有顶点都是尚未访问的，因此任选一个顶点出发，开始遍历整张图。
   比如从 V1 顶点出发，先访问 V1：

2.  从 V1 出发，可以找到 V2 和 V3，它们都没有被访问，所以访问它们：

注意：本图中先访问的是 V2，也可以先访问 V3。当可以访问的顶点有多个时，访问的顺序是不唯一的，可以根据找到各个顶点的先后次序依次访问它们。后续过程也会遇到类似情况，不再重复赘述。

3) 根据图 3 中的顶点访问顺序，紧邻 V1 的顶点已经访问过，接下来访问紧邻 V2 的顶点。

从 V2 顶点出发，可以找到 V1、V4 和 V5，尚未访问的有 V4 和 V5，因此访问它们：

4.  根据图 4 中的顶点访问顺序，接下来访问紧邻 V3 的顶点。

从 V3 顶点出发，可以找到 V1、V6 和 V7，尚未访问的有 V6 和 V7，因此访问它们：

5.  根据图 5 中的顶点访问顺序，接下来访问紧邻 V4 的顶点。

从 V4 顶点出发，可以找到 V2 和 V8，只有 V8 尚未访问，因此访问它：

6.  根据图 6 的顶点访问顺序，接下来访问紧邻 V5 的顶点。

观察图 6 中的无向图不难发现，与 V5 紧邻的 V2 和 V8 都已经访问过，无法再找到尚未访问的顶点。此时，广度优先搜索算法会直接跳过 V5，继续从其它的顶点出发。

7.  广度优先搜索算法先后从 V6、V7、V8 出发，寻找和它们紧邻、尚未访问的顶点，但寻找的结果都和 V5 一样，找不到符合要求的顶点。

8.  自 V8 之后，访问序列中再无其它顶点，意味着从 V1 顶点出发，无法再找到尚未访问的顶点。这种情况下，广度优先搜索算法会从图的所有顶点中重新选择一个尚未访问的顶点，然后从此顶点出发，以同样的思路继续寻找其它尚未访问的顶点。

本例中的无向图是一个连通图

，从 V1 出发可以找到所有的顶点，因此广度优先搜索算法继 V1 顶点之后无法再找到新的尚未访问的顶点，算法执行结束。

对于连通图来说，广度优先搜索算法从一个顶点出发就能访问图中所有的顶点。但是对于非连通图来说，广度优先搜索算法必须从各个连通分量中选择一个顶点出发，才能访问到所有的顶点。

所谓广度优先搜索，就是从图中的某个顶点出发，寻找紧邻的、尚未访问的顶点，找到多少就访问多少，然后分别从找到的这些顶点出发，继续寻找紧邻的、尚未访问的顶点。

当从某个顶点出发，所有和它连通的顶点都访问完之后，广度优先搜索算法会重新选择一个尚未访问的顶点（非连通图中就存在这样的顶点），继续以同样的思路寻找未访问的其它顶点。直到图中所有顶点都被访问，广度优先搜索算法才会结束执行。

图的存储结构有很多种，大体上可以分为顺序存储和链式存储（又细分为邻接表)结构、十字链表结构和邻接多重表结构），各个存储结构有自己的特点。选用不同的存储结构，广度优先搜索算法的具体实现不同，但算法的思想是不变的。

这里以图的顺序存储结构为例，广度优先搜索算法的 C 语言实现代码如下：

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERtEX_NUM 20                   //顶点的最大数量
#define VRType int                          //表示顶点之间关系的数据类型
#define VertexType int                      //顶点的数据类型
typedef enum { false, true }bool;           //定义bool型常量
bool visited[MAX_VERtEX_NUM];               //设置全局数组，记录每个顶点是否被访问过

//队列链表中的结点类型
typedef struct Queue {
    VertexType data;
    struct Queue* next;
}Queue;

typedef struct {
    VRType adj;                             //用 0 表示不相邻，用 1 表示相邻
}ArcCell, AdjMatrix[MAX_VERtEX_NUM][MAX_VERtEX_NUM];

typedef struct {
    VertexType vexs[MAX_VERtEX_NUM];        //存储图中的顶点
    AdjMatrix arcs;                         //二维数组，记录顶点之间的关系
    int vexnum, arcnum;                     //记录图的顶点数和弧（边）数
}MGraph;

//判断 v 顶点在二维数组中的位置
int LocateVex(MGraph* G, VertexType v) {
    int i;
    //遍历一维数组，找到变量v
    for (i = 0; i < G->vexnum; i++) {
        if (G->vexs[i] == v) {
            break;
        }
    }
    //如果找不到，输出提示语句，返回-1
    if (i > G->vexnum) {
        printf("no this vertex\n");
        return -1;
    }
    return i;
}

//构造无向图
void CreateDN(MGraph* G) {
    int i, j, n, m;
    int v1, v2;
    scanf("%d,%d", &(G->vexnum), &(G->arcnum));
    for (i = 0; i < G->vexnum; i++) {
        scanf("%d", &(G->vexs[i]));
    }
    for (i = 0; i < G->vexnum; i++) {
        for (j = 0; j < G->vexnum; j++) {
            G->arcs[i][j].adj = 0;
        }
    }
    for (i = 0; i < G->arcnum; i++) {
        scanf("%d,%d", &v1, &v2);
        n = LocateVex(G, v1);
        m = LocateVex(G, v2);
        if (m == -1 || n == -1) {
            printf("no this vertex\n");
            return;
        }
        G->arcs[n][m].adj = 1;
        G->arcs[m][n].adj = 1;
    }
}

int FirstAdjVex(MGraph G, int v)
{
    int i;
    //对于数组下标 v 处的顶点，找到第一个和它相邻的顶点，并返回该顶点的数组下标
    for (i = 0; i < G.vexnum; i++) {
        if (G.arcs[v][i].adj) {
            return i;
        }
    }
    return -1;
}

int NextAdjVex(MGraph G, int v, int w)
{
    int i;
    //对于数组下标 v 处的顶点，从 w 位置开始继续查找和它相邻的顶点，并返回该顶点的数组下标
    for (i = w + 1; i < G.vexnum; i++) {
        if (G.arcs[v][i].adj) {
            return i;
        }
    }
    return -1;
}

//初始化队列，这是一个有头结点的队列链表
void InitQueue(Queue** Q) {
    (*Q) = (Queue*)malloc(sizeof(Queue));
    (*Q)->next = NULL;
}

//顶点元素v进队列
void EnQueue(Queue** Q, VertexType v) {
    Queue* temp = (*Q);
    //创建一个存储 v 的结点
    Queue* element = (Queue*)malloc(sizeof(Queue));
    element->data = v;
    element->next = NULL;
    //将 v 添加到队列链表的尾部
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = element;
}

//队头元素出队列
void DeQueue(Queue** Q, int* u) {
    Queue* del = (*Q)->next;
    (*u) = (*Q)->next->data;
    (*Q)->next = (*Q)->next->next;
    free(del);
}

//判断队列是否为空
bool QueueEmpty(Queue* Q) {
    if (Q->next == NULL) {
        return true;
    }
    return false;
}

//释放队列占用的堆空间
void DelQueue(Queue* Q) {
    Queue* del = NULL;
    while (Q->next) {
        del = Q->next;
        Q->next = Q->next->next;
        free(del);
    }
    free(Q);
}

//广度优先搜索
void BFSTraverse(MGraph G) {
    int v, u, w;
    Queue* Q = NULL;
    InitQueue(&Q);
    //将用做标记的visit数组初始化为false
    for (v = 0; v < G.vexnum; ++v) {
        visited[v] = false;
    }
    //遍历图中的各个顶点
    for (v = 0; v < G.vexnum; v++) {
        //若当前顶点尚未访问，从此顶点出发，找到并访问和它连通的所有顶点
        if (!visited[v]) {
            //访问顶点，并更新它的访问状态
            printf("%d ", G.vexs[v]);
            visited[v] = true;
            //将顶点入队
            EnQueue(&Q, G.vexs[v]);
            //遍历队列中的所有顶点
            while (!QueueEmpty(Q)) {
                //从队列中的一个顶点出发
                DeQueue(&Q, &u);
                //找到顶点对应的数组下标
                u = LocateVex(&G, u);
                //遍历紧邻 u 的所有顶点
                for (w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w)) {
                    //将紧邻 u 且尚未访问的顶点，访问后入队
                    if (!visited[w]) {
                        printf("%d ", G.vexs[w]);
                        visited[w] = true;
                        EnQueue(&Q, G.vexs[w]);
                    }
                }
            }
        }
    }
    DelQueue(Q);
}
int main() {
    MGraph G;
    //构建图
    CreateDN(&G);
    //对图进行广度优先搜索
    BFSTraverse(G);
    return 0;
}

程序中，广度优先搜索算法的实现借助了队列存储结构，用来存储访问过的顶点。每次出队一个顶点，从该顶点出发寻找和它紧邻、尚未访问的顶点，然后将找到的顶点全部入队。

3. 最小生成树问题

3.1. 什么是最小生成树

这两组算法本身又有一定的区别：

1. “普里姆算法” ，主要解决最小生成树问题。
2. “克鲁斯卡尔算法”，主要解决加权树的最小生成树问题。

接下来我们就来具体看一下。

一个连通图对应的生成树往往有很多种，例如：

如果为连通图中的每条边赋予一个权值（可以理解为一个整数），这样的连通图又称为连通网。

各个生成树包含的边不相同，因此它们的总权值（所有边的权值之和）也不相等。所谓最小生成树，指的就是总权值最小的生成树。

注意，一个连通网对应的最小生成树可能有多个，图 2 就是一个很好的范例，图 2a) 连通网对应的最小生成树有两个。

最小生成树可以用来解决一些实际问题。仍以图 2a) 为例，假设 A、B、C、D 这 4 个顶点各自代表一座城市，各个边表示两座城市之间可以铺设网线，边的权值表示铺设网线需要耗费的经费。如果想为这 4 座城市建立通信联络网，最节省经费的方案就是按照总权值为 7 的生成树铺设网线。

对于给定的连通网，求最小生成树常用的算法有两个，分别叫做普里姆Prim算法和克鲁斯卡尔Kruskal算法。

3.2. 普利姆算法

先看一个应用场景的问题-修路问题:
1) 有胜利乡有7个村庄 (A,B,C,D,E,F,G) ，现在需要修路把7个村庄连通2) 各个村庄的距离用边线表示 ( 权 ) ，比如 A – B 距离 5 公里3) 问:如何修路保证各个村庄都能连通，并且总的修建公路总里程最短**?

思路 : 将10条边，连接即可，但是总的里程数不是最小，那如何尽可能的选择少的路线，并且每条路线最小，保证总里程数最少呢？
最小生成树修路问题本质就是就是最小生成树问题， 先介绍一下最小生成树 (Minimum Cost Spanning Tree) ，简称 MST。 给定一个带权的无向连通图，如何选取一棵生成树，使树上所有边上权的总和为最小 , 这叫最小生成树。

我们可以知道，如果最小，那么生成树一定满足：N 个顶点，最少 N-1 条边就可以将所有顶点连接起来。求最小生成树的算法主要是普里姆算法和克鲁斯卡尔算法。

普利姆(Prim)算法求最小生成树，也就是在包含 n 个顶点的连通图中，找出只有(n-1)条边包含所有 n 个顶点的 连通子图，也就是所谓的极小连通子图。

普利姆的算法如下:

1. 设G=(V,E)是连通网，T=(U,D)是最小生成树，V,U是顶点集合，E,D是边的集合。
2. 若从顶点u开始构造最小生成树，则从集合V中取出顶点u放入集合U中，标记顶点v的visited[u]=1。
3. 若集合U中顶点Ui与集合V-U中的顶点Vj之间存在边，则寻找这些边中权值最小的边，但不能构成回路，将顶点 vj 加入集合 U 中，将边(ui,vj)加入集合 D 中，标记 visited[vj]=1。
4. 重复步骤2，直到U与V相等，即所有顶点都被标记为访问过，此时D中有n-1条边。
5. 提示: 单独看步骤很难理解，我们通过代码来讲解，比较好理解。
6. 图解普利姆算法
7. 从A顶点开始，处理，选择距离最短的，显然到G最短为2,如图1。 从{A,G}里选连接其他元素最短的哪个，并且不能出现环，此时A还有5和7，而G有3、4和6连接，显然3连B最小，如图2。 从{A，B，G}继续找连接外部元素最短的那个，很明显是4连E，如图3。 从{A，B，G，E}继续找连接外部元素最短的那个，此时就是F了，如图4。 从{A，B，G，E，F}继续找连接外部元素最短的那个，此时就是D了，如图5。 最后是A伸出的7连接C，结束。

3.3. 克鲁斯卡尔算法

克鲁斯卡尔方法也是为了解决最小连通，克鲁斯卡尔(Kruskal)算法，是用来求加权连通图的最小生成树的算法。

基本思想:按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路。

具体做法:首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止。

克鲁斯卡尔算法图解说明，以城市公交站问题来图解说明 克鲁斯卡尔算法的原理和步骤:在含有 n 个顶点的连通图中选择 n-1 条边，构成一棵极小连通子图，并使该连通子图中 n-1 条边上权值之和达到 最小，则称其为连通网的最小生成树。

克鲁斯卡尔算法图解，以上图 G4 为例，来对克鲁斯卡尔进行演示(假设，用数组 R 保存最小生成树结果)。

第 1 步:将边<E,F>加入 R 中。 边<E,F>的权值最小，因此将它加入到最小生成树结果 R 中。
第 2 步:将边<C,D>加入 R 中。 上一步操作之后，边<C,D>的权值最小，因此将它加入到最小生成树结果 R 中。
第 3 步:将边<D,E>加入 R 中。 上一步操作之后，边<D,E>的权值最小，因此将它加入到最小生成树结果 R 中。
第 4 步:将边<B,F>加入 R 中。 上一步操作之后，边<C,E>的权值最小，但<C,E>会和已有的边构成回路;因此，跳过边<C,E>。同理，跳过边<C,F>。将边<B,F>加入到最小生成树结果 R 中。 
第 5 步:将边<E,G>加入 R 中。上一步操作之后，边<E,G>的权值最小，因此将它加入到最小生成树结果 R 中。
第 6 步:将边<A,B>加入 R 中。上一步操作之后，边<F,G>的权值最小，但<F,G>会和已有的边构成回路;因此，跳过边<F,G>。同理，跳过边<B,C>。将边<A,B>加入到最小生成树结果R中。
此时，最小生成树构造完成!它包括的边依次是:<E,F> <C,D> <D,E> <B,F> <E,G> <A,B>。

这个过程过与繁琐，我们就不再提供代码了

4. 最短路径问题

4.1. 什么是最短路径问题

在图结构中，一个顶点到另一个顶点的路径可能有多条，最短路径指的就是顶点之间“最短”的路径。

在不同的场景中，路径“最短”的含义也有所差异，比如途径顶点数量最少、总权值最小等。提到最短路径，往往指的是总权值最小的路径，所以常常在网结构（带权的图）中讨论最短路径问题，包括有向网和无向网。

举个简单的例子：

图 1 有向网

图 1 是一张有向网，其中从 V0 到 V5 的路径有多条，包括：

• V0 -> V5，总权值为 100
• V0 -> V4 -> V5，总权值为 30+60 = 90
• V0 -> V4 -> V3 -> V5，总权值为 30+20+10 = 60
• V0 -> V2 -> V3 -> V5，总权值为 10+50+10 = 70

通过比较这些路径的总权值，最终可以找到一条从 V0 到 V5 的最短路径。

现如今，大家出行再也不用担心找不到路了，车上有车载导航，手机上也可以安装各种导航 App，只要输入目的地，导航会自动帮我们规划一条距离最短的路线，这是最短路径在实际生活中的典型应用之一。

在指定的一张网中查找最短路径，该如何编码实现呢？

解决最短路径问题，最常用的方案有两种，分别叫做迪杰斯特拉算法和弗洛伊德算法：

• 迪杰斯特拉算法：查找某个顶点到其它顶点之间的最短路径；
• 弗洛伊德算法：查找任意两个顶点之间的最短路径。

1. “迪杰斯特拉算法”，图中两个点的最短路径问题
2. “弗洛伊德算法”，图中每个顶点到其他所有顶点的最短路径。

4.2. 迪杰特斯拉算法