大话数据结构07-图

本文最后更新于：2020年10月5日 下午

7.2 图的定义

图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常为G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

  • 顶点(Vertex)：图中数据元素
  • 若 V 是顶点的集合，则强调了顶点集合 V 有穷非空
  • 图中任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边表示

1. 各种图定义

  • 无向边：若顶点 vi 到 vj 之间的边没有方向，则称这条边为无向边，用无序偶对(vi,vj) 来表示
  • 无向图 (Undirected graphs)
  • 有向边：若从顶点 vi 到 vj 的边有方向，则称这条边为有向边，也称为弧(Arc)，用有序偶<vi.vj> 来表示，vi 称为弧尾(Tail)，vj 称为弧头(Head)
  • 有向图（Directed graphs）
  • 简单图：在图中，若不存在顶点到其自身的边，且同一条边不重复出现
  • 无向完全图：在无向图中，如果任意两个顶点之间都存在边
  • 含有 n 个顶点的无向完全图有 n*(n-1)/2 条边
  • 有向完全图：在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧
  • 含有 n 个顶点的有向完全图有 n*(n-1) 条边
  • 稀疏图：有很少条边或弧的图，反之称为稠密图
  • 权（Weight）：与图的边或弧相关的数
  • 假设有两个图 G=(V,{E}) 和 G’=(v’,{E’})，如果 V’属于V，且E’属于E，则称 G’为G的子图（Subgraph）

2. 图的顶点与边间关系

  • 对于无向图 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)
  • 简单路径：序列中顶点不重复出现的路径
  • 简单回路或简单环：除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路

3. 连通图相关术语

  • 在无向图G中，如果从顶点 v 到顶点 v’ 有路径，则称 v 和 v’ 是连通的
  • 连通图(Connected Graph)：如果对于图中任意两个顶点vi，vj 属于E，vi 和 vj 都是连通的，则称 G 是连通图
  • 无向图中的极大连通子图称为连通分量
  • 在有向图 G 中，如果对于每一对vi、vj 属于 V，vi 不等于 vj ，从 vi 到 vj 和从 vj 到 vi 都存在路径，则称 G 是强连通图。有向图中的极大强连通子图称做有向图的强连通分量
  • 一个连通图的生成树是一个极小的连通子图，它含有图中全部的 n 个顶点，只有足以构成一棵树的 n-1 条边
  • 如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为 1 ，则是一棵有向树
  • 一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧

7.3 图的抽象数据类型

1
2
3
4
5
ADT 图(Graph)
Data
    顶点的有穷非空集合和边的集合
Operation
    CreatGraph(*G, V, VR): 按照顶点集和边弧集VR的定义构造图G

7.4 图的存储结构

1. 邻接矩阵

图的邻接矩阵(Adjacency Matrix) 存储方式是用两个数组来表示图。

  • 一个一维数组存储图中顶点信息
  • 一个二维数组（称为邻接矩阵）存储图中的边或弧的信息
  • 无向图的边数组是一个对称矩阵

图的邻接矩阵存储的结构：

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

无向网图的创建代码：

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

n 个顶点和 e条边的无向网图的创建，时间复杂度为O(n+n*n+e)，其中对邻接矩阵的初始化耗费了O(n*n)的时间

2. 邻接表

邻接矩阵对于边数相对顶点较少的图，这种结构存在对存储空间的极大浪费

  • 邻接表(Adjacency List)：数组与链表相结合的存储方法
  • 图中顶点用一个一维数组存储，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便查找该顶点的边信息
  • 图中每个顶点 vi 的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储
  • 顶点表的各个结点由 data 和 firstedge 两个域表示，data 是数据域，存储顶点的信息，firstedge 是指针域，指向边表的第一个结点，即此顶点的第一个邻接点
  • 边表结点由 adjvex 和 next 两个域组成，adjvex 是邻接点域，存储某顶点的邻接点在顶点表中的下标；next 则存储指向边表中下一个结点的指针
  • 有时为了便于确定顶点的入度或以顶点为弧头的弧，可以建立一个有向图的逆邻接表，即对每个顶点 vi 都建立一个链接为 vi 为弧头的表

结点定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
typedef char VertexType;	//顶点类型由用户定义
typedef int EdgeType;		//边上的权值类型应由用户定义

typedef struct EdgeNode{	//边表结点
	int adjvex;				//邻接点域，存储该顶点对应的下标
    EdgeType weight;		//用于存储权值，对于非网图可以不需要
    struct EdgeNode *next;	//链域，指向下一个邻接点
}EdgeNode;

typedef struct VertexNode{	//顶点表结点
	VertexType data;		//顶点域，存储顶点信息
    EdgeNode *firstedge;	//边表头指针
}VertexNode, AdjList[MAXVEX];

typedef struct{
    AdjList adjList;
    int numVertexes, numEdges;	//图中当前顶点数和边数
}GraphAdjList;

无向图的邻接表创建代码：

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
//建立图的邻接表结构
void CreatALGraph(GraphAdjList *G)
{
    int i,i,k;
    EdgeNode *e;
    printf("输入顶点数和边数：\n");
    scanf("%d,%d",&G->numVertexes,&G->numEdges);
    for(i = 0; i < G->numVertexes; i++){	//读入顶点信息，建立顶点表
        scanf(&G->adjList[i].data);		//输入顶点信息
        G->adjList[i].firstedge = NULL；	//将边表置为空表
    }
    for(k = 0; k < G->numEdges; k++){	//建立边表
        printf("请输入边(vi, vj)上的顶点序号：\n");
        scanf("%d, %d",&i, &j);			//输入边(vi,vj)上的顶点序号
        e = (EdgeNode *)malloc(sizeof(EdgeNode));	//向内存申请空间，生成边表结点
        e->adjvex = j;					//邻接序号为 j
        e->next = G->adjList[i].firstedge;	//将 e 指针指向当前顶点的结点
        G->adjList[i].firstedge = e;		//将当前顶点的指针指向e
        
        e = (EdgeNode *)malloc(sizeof(EdgeNode));	//向内存申请空间，生成边表结点
        e->adjvex = i;					//邻接序号为 i
        e->next = G->adjList[j].firstedge;	//将 e 指针指向当前顶点的结点
        G->adjList[j].firstedge = e;		//将当前顶点的指针指向e
    }
}

本算法的时间复杂度，对于 n 个顶点 e条边来说为O(n+e)

3. 十字链表

邻接表解决了出度问题，逆邻接表解决了入度问题。

  • 把邻接表与逆邻接表结合起来得到：十字链表(Orthogonal List)

顶点表结点结构：

data firstin firstout

  • firstin：入边表头指针，指向该顶点的入边表中第一个结点

  • firstout：出边表头指针，指向该顶点的出边表中的第一个结点

边表结点结构：

tailvex headvex headlink taillink

  • tailvex：弧起点在顶点表的下标

  • headvex：弧终点在顶点表中的下标

  • headlink：入边表指针域，指向终点相同的下一条边

  • taillink：边表指针域，指向起点相同的下一条边

4. 邻接多重表

边表结点结构：

ivex ilink jvex jlink

  • ivex 和 jvex 是与某条边依附的两个顶点在顶点表中下标

  • ilink 指向依附顶点 ivex 的下一条边

  • jlink 指向依附顶点 jvex 的下一条边

5. 边集数组

边集数组是由两个一维数组构成。

一个是存储顶点的信息；另一个是存储边的信息，这个边数组每个数据元素由一条边的起点下标(begin)，终点下标(end)和权(weight)组成。

  • 边集数组关注的是边的集合，在边集数组中查找一个顶点的度需要扫描整个边数组，效率不高
  • 更适合对边依次进行处理的操作，而不适合对顶点相关的操作

7.5 图的遍历

1. 深度优先遍历(DFS)

Depth First Search

2. 广度优先遍历(BFS)

Breadth First Search

7.6 最小生成树

1. 普里姆(Prim)算法

2. 克鲁斯卡尔(Kruskal)算法

7.7 最短路径

1. 迪杰斯塔拉(Dijkstra)算法

2. 弗洛伊德(Floyd)算法

7.8 拓扑排序

7.9 关键路径