数据结构-图

图的基本概念

图G由顶点V和边E组成，记为G=(V,E)，V一定非空，E可以空。
V={v1,v2,……,vn}，|V|表示顶点个数
E={(u,v)|u∈V,v∈V}，|E|表示边的条数

有向图
<v,w>称为从v到w的弧，也称v邻接到w。v为弧尾，w为弧头。
无向图
(v,w)或者(w,v)说，w与v互为邻接点
简单图与多重图
简单图：1-不存在重复边（两个顶点的边数不多于一条）；2-不存在到自身的边
多重图：反之
完全图
若图的顶点数为n，如果|E|=n*(n-1)/2，称为无向完全图；如果|E|=n*(n-1)，称为有向完全图。
子图
设有两个图G=(V,E)，G’=(V’,E’)，若V’∈V，E’∈E,则称G’是G的子图。
生成子图
若满足V(G’) = V(G)，则称G’为G的生成子图
连通、连通图、连通分量（无向图范畴）
连通：两点之间存在路径
连通图：任意两点之间都是连通的
连通分量：无向图中的极大连通子图

若一个图有n个顶点，若边数小于n-1，则为非连通图；若它是非连通图，则边数最多为(n-1)(n-2)/2

强连通、强连通图、强连通分量（有向图范畴）
强连通：两点之间有双向路径
强连通图：任意两点之间都是强连通的
强连通分量：~

若一个有向图有n个顶点，若其为强连通图，最少需要n条边。

生成树
连通图的生成树：包含全部顶点的极小连通子图（顶点数若为n，则其边数为n-1）
生成森林：在非连通图中，连通分量的生成树构成了非连通图的生成森林

极大||极小 - 连通子图：前者：尽可能包含多的点与边；后者：尽可能少的包含边。

顶点的度、入度、出度
无向图中：度(TD)：依附于顶点的边的条数。度数和=边数*2。
有向图中：
- 入度(ID)：以顶点为终点的有向边的数目
- 出度(OD)：以顶点为起点的有向边的数目
- 度：结点的入度加出度
  
  入度之和等于出度之和等于边数
边的权、网
边上的权值。带权的图成为带权图，也成为网
弧
有向图的边
稠密图、稀疏图
只是模糊的相对的概念。一般当|E|<|V|log|V|时，将其视为稀疏图
路径、路径长度、回路
路径：指的是顶点序列（eg:v1,v2,v3）
路径长度：路径上边的数目
回路（环）：第一个顶点和最后一个顶点相同的路径。n个顶点的图中，若路径大于n-1，则存在回路。
简单路径、简单回路
简单路径：顶点不重复出现
简单回路：除第一个顶点、最后一个顶点，其他顶点不重复出现的回路。
距离
两个顶点间的最短路径，若不存在则为∞
有向树
有向图满足一个顶点入度为0，其余顶点入度均为1。

图的存储及其基本操作

邻接矩阵法(adjacency matrix)

404

# define MaxVertexNum 100   //顶点数目最大值
typedef char VertexType   //顶点对应的数据类型
typedef int EdgeType    //边对应的数据类型
typedef struct {
    VertexType vex[MaxVertexNum];   //顶点表
    EdgeType edge[MaxVertexNum][MaxVertexNum];      //边表
    int vernum , edgenum;           //图的当前顶点数与边数
}MGraph;

空间复杂度为O(n^2)，其中n为顶点的个数
当仅表示边是否存在时，可以用0\1的枚举类型定义边表
基于邻接矩阵度的计算

无向图：结点i的度，为第i行非0\∞元素的个数
有向图：结点i的出度，为i行非0\∞元素个数；结点i的入度，为第i列非0\∞元素的个数

用邻接矩阵很容易确定两个结点间是否有边；但确定总边数花费较大。
稠密图适合采用邻接矩阵
若一个图的邻接矩阵为A，则A^n[i][j]代表从结点i到结点j的路径长度为n的个数（参考离散数学）

邻接表法(adjacency list)

为减少邻接矩阵的浪费而生，采用顺序存储结合链式存储

# define Max 100

typedef struct ArcNode{     //边表结点
    int adjvertex;    //与头结点邻接的顶点编号
    struct ArcNode *nextarc;
    //InfoType info;        //权
}ArcNode;

/*
建议保留typedef中的标签，即typedef struct ArcNode中的ArcNode

如果省略标签（struct ArcNode 中的 ArcNode），则在结构体内部无法使用 struct ArcNode *nextarc，因为编译器不知道 ArcNode 是什么。
*/

typedef struct VNode{       //顶点表信息
    VertexType data;        //顶点**信息**
    struct ArcNode *firstarc;
}VNode,AdjList[Max];

/*
AdjList 是一个数组类型，表示一个包含 Max 个 VNode 的数组。AdjList[Max] 则表示一个具体的数组实例，数组的大小为 Max，每个元素都是一个 VNode 结构体。
*/

typedef struct {
    AdjList vertices;
    int vertexnum,edgenum;
}ALGraph;

/*
    AdjList vertices;
    vertices是一个数组
    例如：ALGraph a; a.vertices;假设图中有 3 个顶点（a.vertexnum = 3），边的数量为 2（a.edgenum = 2），那么：
    a.vertices[0] 表示第 1 个顶点。

    a.vertices[1] 表示第 2 个顶点。

    a.vertices[2] 表示第 3 个顶点。
*/