图的基本概念

图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

1
2
3
4
5
6
7
8
# define MaxVertexNum 100   //顶点数目最大值
typedef char VertexType   //顶点对应的数据类型
typedef int EdgeType    //边对应的数据类型
typedef struct {
    VertexType vex[MaxVertexNum];   //顶点表
    EdgeType edge[MaxVertexNum][MaxVertexNum];      //边表
    int vernum , edgenum;           //图的当前顶点数与边数
}MGraph;
  1. 空间复杂度为O(n^2)，其中n为顶点的个数
  2. 当仅表示边是否存在时，可以用0\1的枚举类型定义边表
  3. 基于邻接矩阵度的计算
  • 无向图：结点i的度，为第i行非0\∞元素的个数
  • 有向图：结点i的出度，为i行非0\∞元素个数；结点i的入度，为第i列非0\∞元素的个数
  1. 用邻接矩阵很容易确定两个结点间是否有边；但确定总边数花费较大。
  2. 稠密图适合采用邻接矩阵
  3. 若一个图的邻接矩阵为A，则A^n[i][j]代表从结点i到结点j的路径长度为n的个数（参考离散数学）

邻接表法(adjacency list)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# define Max 100
typedef struct ArcNode{     //边表结点
    int adjvertex;    //该弧所指向的顶点的位置
    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 个顶点。
*/