数据结构笔记：图

各种图定义
- 图(Graph)是由顶点的有穷非空**集合和顶点之间边的集合组成，通常表示为：G(VE),其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
- 顶点（Vertex）：图中的数据元素
- 若顶点vi到vj之间的边没有方向，则称这条边为无向边（Edge），用无序偶对（vi,vj）来表示。
- 如果图中任意两个顶点之间的边都是无向边，则称该图为**无向图(Undirected graphs)**。
- 若从顶点v到v的边有方向，则称这条边为有向边，也称为弧（Arc）。用有序偶对<vi,vj>来表示，v1称为弧尾（Tail），v2称为弧头（Head）。
- 如果图中任意两个顶点之间的边都是有向边，则称该图为有向图（Directed graphs）。
- 在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。
  含有n个顶点的无向完全图有nx(n-1)/2条边。
- 在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。
  含有n个顶点的有向完全图有n×(n-1)条边。
- 有很少条边或弧的图称为稀疏图，反之称为稠密图。（相对概念）
- 有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做**权(Weight)**。这些权可以表示从一个顶点到另一个顶点的距离或耗费。
- 这种带权的图通常称为**网(Network)**。
- 假设有两个图G=(V,{B})和G′= (V′,{E′})，如果V′⊆V且E′⊆E，则称G为G的**子图(Subgraph)**。
图的顶点与边间关系
- 对于无向图G=(V{E})，如果边(v,v′)∈E，则称顶点v和v互为**邻接点(Adjacent)**，即v和v′相邻接。边(v,v′)**依附（incident)于顶点v和v′，或者说(v,v’)与顶点v和v’相关联。顶点v的度(Degree)是和v相关联的边的数目，记为TD (v)**。
- 对于有向图G=(V,{E})，如果弧<v,v′>∈E，则称顶点v邻接到顶点v′，顶点v′邻接自顶点v。弧<v,v′>和顶点 v,v′相关联。以顶点v为头的弧的数目称为v的**入度(InDegree)，记为ID(v)；以v为尾的弧的数目称为v的出度(OutDegree)，记为OD(v)；顶点v的度为TD(v)=ID(v)+OD(v)**。
- 无向图G=(V,{E})中从顶点v到顶点v′的**路径(Path)**是一个顶点序列(v=vi,0,vi,1,…,vi,m=v′)，其中(vi,j-1,vi,j)∈E，1≤j≤m。
- 路径的长度是路径上的边或弧的数目。
- 第一个顶点到最后一个顶点相同的路径称为回路或环（Cycle）。
- 序列中顶点不重复出现的路径称为简单路径。
- 除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。
连通图相关术语
- 在无向图G中，如果从顶点v到顶点v′有路径，则称v和v′是连通的。如果对于图中任意两个顶点 vi、vj∈E, vi和vj都是连通的，则称G是**连通图(Connected Graph)**。
- 无向图中的极大连通子图称为连通分量。
  注意连通分量的概念，它强调：
  \0. 子图要是连通的
  \1. 子图要是连通的
  \2. 连通子图含有极大顶点数
  \3. 具有极大顶点数的连通子图包含依附于这些顶点的所有边
- 在有向图G中，如果对于每一对vi、vj∈V、vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。有向图中的极大强连通子图称做有向图的强连通分量。
- 一个连通图的生成树是一个极小的连通子图，它含有图中全部的n个顶点，但只有足以构成一棵树的n-1条边。
- 如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一棵有向树。
- 一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。如图1是一棵有向图。去掉一些弧后，它可以分解为两棵有向树，如图2和图3，这两棵就是图1有向图的生成森林。

图的抽象数据类型

ADT 图（Graph）
Data
    顶点的有穷非空集合和边的集合。
Operation
    CreateGraph(*G, V, VR): 按照顶点集V和边弧集VR的定义构造图G。
    DestroyGraph(*G): 图G存在则销毁。
    LocateVex(G, u): 若图G中存在顶点u，则返回图中的位置。
    GetVex(G, v): 返回图G中顶点v的值。
    PutVex(G, v, value): 将图G中顶点v赋值value。
    FirstAdjVex(G, *v): 返回顶点v的一个邻接顶点，若顶点在G中无邻接顶点返回空。
    NextAdjVex(G, V, *w): 返回顶点v相对于顶点w的下一个邻接顶点，若w是v的最后一个邻接点则返回“空”。
    InsertVex(*G, v): 在图G中增添新顶点v。
    DeleteVex(*G, v): 删除图G中顶点v及其相关的弧。
    InsertArc(*G, v, w): 在图G中增添弧<v, w>，若G是无向图，还需要增添对称弧<w, v>。
    DFSTraverse(G): 对图G中进行深度优先遍历，在遍历过程中对每个顶点调用。
    BFSTraverse(G): 对图G中进行广度优先遍历，在遍历过程中对每个顶点调用。
endADT

图的存储结构

邻接矩阵（Adjacency Matrix）

这种存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。

设图G有n个顶点，则邻接矩阵是一个n×n的方阵，定义为：

一个无向图及其邻接矩阵：

一个有向图及其邻接矩阵：

设图G是网图，有n个顶点，则邻接矩阵是一个n×n的方阵，定义为：

一个有向网图及其邻接矩阵：

邻接矩阵存储的结构代码：

1 typedef char VertexType; // 顶点类型应由用户定义
2 typedef int EdgeType; // 边上的权值类型应由用户定义
3 #define MAXVEX 100 // 最大顶点数，应由用户定义
4 #define INFINITY 65535 // 用65535来代表∞
5 typedef struct {
6     VertexType vexs[MAXVEX]; // 顶点表
7     EdgeType arc[MAXVEX][MAXVEX]; // 邻接矩阵，可看作表
8     int numVertexes, numEdges; // 图中当前的顶点数和边数
9 } MGraph;

创建无向网图：

 1 // 建立无向网图的邻接矩阵表示
 2 void CreateMGraph(MGraph *G) {
 3     int i, j, k, w;
 4     printf("输入顶点数和边数：\n");
 5     scanf("%d,%d", &G->numVertexes, &G->numEdges);
 6     for (i = 0; i < G->numVertexes; i++) // 读入顶点信息，建立顶点表
 7         scanf(&G->vexs[i]);
 8     for (i = 0; i < G->numVertexes; i++)
 9         for (j = 0; j < G->numVertexes; j++)
10             G->arc[i][j] = INFINITY; // 邻接矩阵初始化
11     for (k = 0; k < G->numEdges; k++) { // 读入numEdges条边，建立邻接矩阵
12         printf("输入边(vi,vj)上的下标i，下标j和权w:\n");
13         scanf("%d,%d,%d", &i, &j, &w); // 输入边(vi,vj)上的权w
14         G->arc[i][j] = w;
15         G->arc[j][i] = G->arc[i][j]; // 因为是无向图，矩阵对称
16     }
17 }

邻接表（Adjacency List）

这种存储方式将数组与链表相结合。

一个无向图及其邻接表：

我们是以顶点为弧尾来存储边表的，因此可以很容易地得到每个顶点的出度。对于有向图的邻接表，有时为了便于确定顶点的入度或以顶点为弧头的弧，我们可以建立一个

有向图的逆邻接表

，即对每个顶点v

都建立一个链接为弧头的表。如下图所示：

对于带权值的网图，可以在边表结点定义中再增加一个weight的数据域，存储权值信息即可。如下图所示：

邻接表的结点定义：

 1 typedef char VertexType; // 顶点类型应由用户定义
 2 typedef int EdgeType; // 边上的权值类型应由用户定义
 3 
 4 typedef struct EdgeNode { // 边表结点
 5     int adjvex; // 邻接点域，存储该顶点对应的下标
 6     EdgeType weight; // 用于存储权值，对于非网图可以不需要
 7     struct EdgeNode *next; // 链域，指向下一个邻接点
 8 } EdgeNode;
 9 
10 typedef struct VertexNode { // 顶点表结点
11     VerterType data; // 顶点域，存储顶点信息
12     EdgeNode *firstedge; // 边表头指针
13 } VertexNode, AdjList[MAXVEX];
14 
15 typedef struct {
16     AdjList adjList;
17     int numVertexes, numEdges; // 图中当前顶点数和边数
18 } GraphAdjList;

创建无向图的邻接表：

 1 // 建立图的邻接表结构
 2 void CreateALGraph(GraphAdjList *G) {
 3     int i, j, k;
 4     EdgeNode *e;
 5     printf("输入顶点数和边数：\n");
 6     scanf("%d,%d", &G->numVertexes, &G->numEdges); // 输入顶点数和边数
 7     for (i = 0; i < G->numVertexes; i++) { // 读入顶点信息，建立顶点表
 8         scanf(&G->adjList[i].data); // 输入顶点信息
 9         G->adjList[i].firstedge = NULL; // 将边表置为空表
10     }
11     for (k = 0; k < G->numEdges; k++) { // 建立边表
12         printf("输入边(vi,vj)上的顶点序号：\n");
13         scanf("%d,%d", &i, &j); // 输入边(vi,vj)上的顶点序号
14         e = (EdgeNode *)malloc(sizeof(EdgeNode)); // 向内存申请空间，生成边表结点
15 
16         e->adjvex = j; // 邻接序号为j
17         e->next = G->adjList[i].firstedge; // 将e指针指向当前顶点指向的结点
18         G->adjList[i].firstedge = e; // 将当前顶点的指针指向e
19 
20         e = (EdgeNode *)malloc(sizeof(EdgeNode)); // 向内存申请空间，生成边表结点
21 
22         e->adjvex = i; // 邻接序号为i
23         e->next = G->adjList[j].firstedge; // 将e指针指向当前顶点指向的结点
24         G->adjList[j].firstedge = e; // 将当前顶点的指针指向e
25     }
26 }

第14至第24行代码，应用了单链表创建中的头插法。由于对于无向图，一条边对应的是两个顶点，所以在循环中，一次就针对i和j分别进行了插入。

十字链表（Orthogonal List）
这种存储方式将邻接表与逆邻接表结合起来。

顶点表结点结构：

其中firstin表示入边表头指针，指向该顶点的入边表中第一个结点，firstout表示出边表头指针，指向该顶点的出边表中的第一个结点。

边表结点结构：

其中 tailvex是指弧起点在顶点表的下标，headvex是指弧终点在顶点表中的下标，headlink是指入边表指针域，指向终点相同的下一条边，taillink是指边表指针域，指向起点相同的下一条边。如果是网，还可以再增加一个weight域来存储权值。
就是长这样：
邻接多重表（针对无向图，方便边的操作）
边表结点结构：

其中ivex和jvex是与某条边依附的两个顶点在顶点表中下标。ilink指向依附顶点ivex的下一条边，jlink指向依附顶点jvex的下一条边。
长这样：

由于是无向图，所以ivex是0、jvex是1还是反过来都无所谓。不过为了绘图方便，将ivex值都设置得与一旁的顶点下标相同。
连线后它就长这样：
边集数组

边集数组由两个一维数组构成。一个存储顶点的信息；另一个存储边的信息，这个边数组中每个数据元素由一条边的起点下标（begin）、终点下标（end）和权（weight）组成，如下图所示：

定义的边数组结构如下表所示：

其中begin存储起点下标，end存储终点下标，weight存储权值。