1.邻接矩阵

1.1 基本概念

用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息。

顶点的保存：直接存在一个一维数组里面。

边的存储：每一行代表一个顶点与其他顶点之间边的存在关系。结点数为n的图G=(V, E)的邻接矩阵A是n*n的。若Vi与Vj之间存在一条边，那么就在i行j列让这个邻接矩阵A[i][j] = 1，如果不存在，A[i][j] = 0 （带权图不存在使用∞）。

易错点：

带权图，为什么不能用零（0）表示带权图的边不存在？
0会代表权值，认为0这个权值是存在的，所以0不能用来表示边是否存在。
认定权值是不可能为一个巨大的数，权值越大代表代价越大。这个巨大的数字代表边不存在。

1.2 邻接矩阵数据结构

计算机之中，图的信息不仅仅包括弧信息、顶点的信息，对图有一个宏观的信息。

图的拓扑信息：微观信息和图的宏观信息。

图的宏观信息：有多少条边arcnum，有多少个顶点vexsnum，图是什么类型GraphKind（一共是4中类型：有（无）向图、（不）带权图）。

图的微观信息：顶点与顶点之间边的关系（弧）

1.2.1 图的类型

// 图的类型
typedef enum GraphKind
{
    DG,     // directed Graph，有向不带权图
    UDG,    // undirected Graph，无向不带权图
    DN,     // directed Network，有向带权图（有向网)
    UDN,    // undirected Network，无向带权图（无向网）
}GraphKind;

1.2.2 顶点

图中顶点最大数量

#define MXA_VERTEX 100

顶点数据类型

typedef int VertexType;

1.2.3 弧

注意：弧不仅仅只有权值，还可能有其他信息。如北京到天津的铁路抽象成依附于被北京和天津两个城市顶点,不仅仅是这个铁路有多长，额外信息:客流量、次数

弧的权值类型及权值无穷定义

// 有权图中的无穷大，使用C语言中的最大值宏定义
#define INFINITY INT_MAX

弧结构体定义

typedef struct ArcCell
{
    int weight = 0;  //不带权图时的权值
    // int weight = INFINITY;  //带权图时的权值

    // InfoType* info;
}ArcCell;

1.2.4 邻接矩阵

图的拓扑信息，不仅仅有弧信息，顶点信息，宏观信息

typedef struct
{
    // 顶点信息，默认顶点编号从1开始
    VertexType vexs[MXA_VERTEX];
    // 弧信息
    ArcCell arcs[MXA_VERTEX][MXA_VERTEX];
    int vexnum;     // 图当前顶点数
    int arcnum;     // 图当前弧数（边数）
    GraphKind kind; // 图的类型
}MGraph;

2.邻接表

2.1 基本概念

将公共的顶点作为链表的头结点，多条共源点的弧依附的源点都存在链表的头结点中。

每个顶点都会存到头结点中，这些头结点都是相同的数据类型。将其打包成为一个数组。这样就可以通过索引直接访问每个头结点(顶点<=>源点)。链表知道头结点就能知道整条链。

使用头插法插入较为简单。

顶点的类型：

是源点，不是源点（以源点开始出发（头结点）顺--->邻接表）；
是终点，不是终点（以终点开始出发（头结点）逆--->逆邻接表）。

2.2 邻接表数据结构

2.2.1 边表结点

注意：弧不仅仅只有权值，还可能有其他信息

// 图结点（边表结点）
typedef struct ArcNode
{
    // 一般顶点默认是数组编号，所以跟索引一一对应，顶点编号即索引
    int adjvex;     // 目的结点的编号，目的顶点对应头结点在数组中的编号
    struct ArcNode* next;   // 指向下一条弧的指针

    // 权值
    int weight;

    // InfoType* info;      // 网的权值信息
}ArcNode;

2.2.2 顶点表结点

// 顶点表结点
typedef struct VNode
{
    VertexType data;    // 顶点信息
    // 只是为了区分指针是从弧结点获得，还是头结点获得
    ArcNode* first;     // 指向第一条依附该顶点的弧的指针
}VNode, AdjList[MAX_VERTEX];

2.2.3 邻接表

// 以邻接表存储的图
typedef struct
{
    AdjList vertices;   // 邻接数组，用于存顶点信息（头结点）

    int vexnum;         // 图当前顶点数
    int arcnum;         // 图当前弧数（边数）
    GraphKind kind;     // 图的类型
}ALGraph;