什么是图（Graph）？

  • 表示“多对多”的关系
  • 包含：
    • 一组顶点：通常用V（Vertex） 表示顶点集合
    • 一组边：通常用E（Edge）表示边的集合
    • 边是顶点对：（v,w）属于 E ，其中 v,w 属于 V 有向边 <v,w> 表示从v指向w的边（单行线） 不考虑重边和自回路

抽象数据类型定义

类型名称：图（Graph）

数据对象集：G(V,E)由一个非空的有限顶点集合V和一个有限边集合E组成。

操作集：对于任意图 G 属于（\(/in\)） Graph，以及 v 属于 V, e 属于 E

  • Graph Create()： 建立并返回空图；
  • Graph InsertVertex(Graph G, Vertex v)： 将v插入G；
  • Graph InsertEdge(Graph G, Edge e)： 将e插入G；
  • void DFS(Graph G, Vertex v)： 从顶点v出发深度优先遍历图G；
  • void BFS(Graph G, Vertex v)： 从顶点v出发宽度优先遍历图G；
  • void ShortestPath(Graph G, Vertex v, int Dist[])：计算图G中顶点v到任意其他顶点的最短距离；
  • void MST(Graph G)： 计算图G的最小生成树；
  • ……

图的表示

邻接矩阵：

二维数组直接表示：直接用一个二维数组G[N][N]表示一个图，也就相当于一个方阵，顶点之间是否连接通过1，0 来表示，也就是说G[i][j] 的值为 1 ，说明 i j 两个顶点联通，之间存在边，如果为0，则不连通

二维数组表示的缺点：如此表示无向图（边没有方向）有些浪费空间，G[i][j] 与 G[j][i] 表示的内容是相同的，即i 与 j 之间联通

改进：用长度为 N(N+1)/2 的一维数组A存储

一维数组直接表示法：只取原矩阵的下三角或者上三角矩阵，从左到右从上到下依次存入

如何判断两顶点之间是否联通：我们以下三角矩阵为例，发现二维数组之中的 G[i][j] 对应A的下标为 ( i * (i + 1)/2 + j )，所以，判断 i j 之间是否连通，直接查看对应下标的值即可

建图代码：代码的思路很简单，首先图包括顶点和边，所以我们将之分离，因为顶点的建立很方便，所以我们可以先初始化一个没有边的图，之后再插入边。 有了这个思路，我们首先将数据类型名称重新设定一番，使之可以见名知意

代码：一切之前

1
2
3
4
5
6
7
8
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 /* 设定数组最大容量 */
#define INFINITY 65535 /* 双字节无符号整数最大值 */

typedef int Vertex; /* 用顶点下标表示顶点 为整型*/
typedef int WeightType; /* 边的权值为整型 */
typedef char DataType; /* 顶点储存的数据类型为字符串 */

接下来我们需要两个结构，也就是边和图的结构

代码：结构的设立

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct ENode *PtrToENode;
struct ENode{ // 边的定义
    Vertex V1,V2; // 有向边v1, v2
    WeightType Weight; // 权重
};
typedef PtrToENode Edge;

typedef struct GNode *PtrToGNode;
struct GNode{ // 图结点的定义
    int Nv; // 顶点数
    int Ne; // 边数
    WeightType G[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
    DataType Data[MAX_VERTEX_NUM]; // 存顶点的数据，此项可根据具体情况省去或添加
};
typedef PtrToGNode MGraph;

之后创建一个函数，进行图的初始化，也就是只有顶点没有边的图

代码：初始化图

1
2
3
4
5
6
7
8
9
10
11
/* 初始化有VertexNum个顶点但没有边的图 */
MGraph CreateGraph(int VertexNum){
    Vertex V, W;
    MGraph Graph;
    Graph = (MGraph)malloc(sizeof(struct GNode)); // 建立图
    Graph->Nv = VertexNum; // 设立顶点数
    Graph->Ne = 0; // 设立边数
    for (V = 0; V < Graph->Nv; V++)
        for (W = 0; W < Graph->Nv; W++)
            Graph->G[V][W] = INFINITY; // 初始化数组
    return Graph;

既然建图之时需要插入边，所以需要一个插入边的函数

代码：插入边

1
2
3
4
5
/* 插入边 */
void InsertEdge(MGraph Grape, Edge E){    
    Grape->G[E->V1][E->V2] = E->Weight;    
    Grape->G[E->V2][E->V1] = E->Weight; // 无向图还需反向插入
}

准备工作做完之后就可以创建完整的图了

代码：建立完整的图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* 建立完整的图 */
MGraph BuildGraph(){
    MGraph Graph;
    Edge E;
    Vertex V;
    int Nv, i;
    scanf("%d", &Nv); // 读入顶点数
    Graph = CreateGraph(Nv);
    scanf("%d", &(Graph->Ne)); // 输入图的边数
    if (Graph->Ne != 0){
        E = (Edge)malloc(sizeof(struct ENode)); // 新建边结点
        for (i = 0; i < Graph->Ne; i++) { // 读入边
            // 输入格式 “起点 终点 权重”
            scanf("%d %d %d", &E->V1, &E->V2, &E->Weight);
            InsertEdge(Graph, E); // 向图中插入边
        }
    }
    for (V=0; V < Graph->Nv; V++) // 输入顶点值 若没有顶点值可以不写
        scanf("%c", &(Graph->Data[V]));
    return Graph;
}

邻接矩阵的缺点：面对稀疏图，我们的邻接矩阵就会有些浪费空间了，大量的0占据了大量空间

改进：用邻接表表示

邻接表

G[N] 为指针数组，对应矩阵每行一个链表，只存非0元素，如果是网络，结构之中要增加权重的域

建图代码： 我们的实现方案和邻接矩阵一样，先建立一个只有顶点没有边的图，之后再插入边以形成一个完整的图，所以一些代码完全和邻接矩阵相同 准备工作和定义边的代码与邻接矩阵相同

之后，定义邻接点结构

代码：

1
2
3
4
5
6
7
/* 邻接点的定义 */
typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode{
    Vertex AdjV; //邻接点下标
    WeightType Weight; // 边权重
    PtrToAdjVNode Next; // 指向下一个邻接点的指针
};

为方便操作，定义表头结点

代码：

1
2
3
4
5
/* 顶点表头结点的定义 */typedef struct Vnode{    
    PtrToAdjVNode FirstEdge; // 边表头指针    
    DataType Data; // 存顶点的数据     
    /* 注意：很多情况下，顶点无数据，此时Data可以不用出现 */
} AdjList[MaxVertexNum]; // AdjList是邻接表类型

重新以邻接表的方式定义图结点

代码：

1
2
3
4
5
6
7
8
/* 图结点的定义 */
typedef struct GNode *PtrToGNode;
    struct GNode{
    int Nv; // 顶点数
    int Ne; // 边数
    AdjList G; // 邻接表
};
typedef PtrToGNode LGraph;

初始化一个只有顶点没有边的初识图

代码：

1
2
3
4
5
6
7
8
9
10
11
/* 初始化一个有VertexNum个顶点但没有边的图 */
LGraph CreateGraph( int VertexNum ) { 
    Vertex V;
    LGraph Graph;
    Graph = (LGraph)malloc( sizeof(struct GNode) ); // 建立图
    Graph->Nv = VertexNum;
    Graph->Ne = 0; // 初始化邻接表头指针      /* 注意：这里默认顶点编号从0开始，到(Graph->Nv - 1) */
    for (V=0; V<Graph->Nv; V++)
        Graph->G[V].FirstEdge = NULL; // 初始化 VertexNum 个表头结点，指针为空
    return Graph;
}

设计插入函数

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void InsertEdge( LGraph Graph, Edge E ) {    
    PtrToAdjVNode NewNode; // 插入边 <V1, V2>    
    
    /* 为V2建立新的邻接点 */    
    NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));    
    NewNode->AdjV = E->V2;    
    NewNode->Weight = E->Weight;    
    
    /* 将V2插入V1的表头 */    
    NewNode->Next = Graph->G[E->V1].FirstEdge;    
    Graph->G[E->V1].FirstEdge = NewNode; /* 若是无向图，还要插入边 <V2, V1> */    
    /* 为V1建立新的邻接点 */    
    NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));    
    NewNode->AdjV = E->V1;    
    NewNode->Weight = E->Weight; // 将V1插入V2的表头    
    NewNode->Next = Graph->G[E->V2].FirstEdge;    
    Graph->G[E->V2].FirstEdge = NewNode;
}

写出建立完整图的函数

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
LGraph BuildGraph() {
    LGraph Graph;
    Edge E;
    Vertex V;
    int Nv, i;
    scanf("%d", &Nv); // 读入顶点个数
    Graph = CreateGraph(Nv); // 初始化有Nv个顶点但没有边的图
    scanf("%d", &(Graph->Ne)); // 读入边数
    if ( Graph->Ne != 0 ) { // 如果有边
        E = (Edge)malloc( sizeof(struct ENode) ); // 建立边结点
        /* 读入边，格式为"起点 终点 权重"，插入邻接矩阵 */
        for (i=0; i<Graph->Ne; i++) {
            scanf("%d %d %d", &E->V1, &E->V2, &E->Weight);
            /* 注意：如果权重不是整型，Weight的读入格式要改 */
            InsertEdge( Graph, E );
        }
    }
    /* 如果顶点有数据的话，读入数据 */
    for (V=0; V<Graph->Nv; V++)
        scanf(" %c", &(Graph->G[V].Data));
    return Graph;
}

缺点：此种表示方法缺点多多，首先图一定要足够稀疏才行，否则的话是不如矩阵节省空间的，其次这样表示不方便进行检查两顶点之间是否存在边