面向考试复习数据结构2.0版正式上线了

本文将整理后三章的相关知识点，并对例题习题进行整合梳理，存在不足，欢迎补充。

第四章图

图的基本概念

图是由一个顶点集V和一个弧集(或边集)构成的数据结构，是一种非线性数据结构

网：带权的图。在不会引起歧义时，网也直接称为图。

路径长度：路径上边的数目（两个点之间的距离即路径上除了起点，包括终点的顶点个数）

简单路径：顶点不重复出现的路径（边可以重复）

关于图的顶点和边数目

我们用 n 表示图中顶点数目；m表示图中边(或者弧)的数目；

对于无向图：0≤m≤n(n-1)/2 m=n(n-1)/2的无向图称为完全图

对于有向图：0≤m≤n(n-1) m=n(n-1)的有向图称为有向完全图

n=0: V为空集；m=0: 或许有1个顶点（平凡图）。

例一：设某个非连通无向图有28条边，则该图至少有(9)个顶点。

解：此题的要点是非连通的无向图

由上方公式可得，8*7/2=28，正好为8个顶点的完全图的边数

但题目中要求是非连通的，所以在边不加的情况下，至少加一个孤立点，即至少有9个顶点

举一反三：若某个连通无向图有28条边，则该图至少有(8)个顶点。

关于图的度数

什么是邻接点？

什么是度数？

1.对于无向图，顶点v的度就是和顶点v相邻接的边的数目，记为TD(v)

2.对于有向图，入度ID(v)是箭头指向v的弧的个数， 出度OD(v)是箭头远离v的弧的个数

顶点v的度TD(v)=ID(v)+OD(v)

3.握手定理：

$\begin{equation*} 2m = \sum_{n=1}^nTD(v_i) \end{equation*}$

关于图的连通性

两个顶点间连通，等价于两个顶点之间有路径。

连通图：无向图中任意两个顶点都连通（不存在孤立点）

连通分量：无向图中的极大连通子图

强连通图/强连通分量：对于有向图，概念类似上两个。

生成树

对于连通图G，若其有n个顶点，则含有G中所有顶点，且边数为n-1的连通图称为G的一棵生成树。

关键：原图是连通图，生成树有其全部n个顶点，有且仅有n-1条边。

提示

有n个顶点和n-1条边的图不一定是生成树

在有n个顶点的图中,如果边多于n-1条,则一定有环，如果边少于n-1条,则是非连通图。

图的存储结构

图的邻接矩阵

从邻接矩阵判断度数

对于无向图，顶点Vi的度为邻接矩阵中第i行（或第i列）元素个数之和（防止带权干扰）。

对于有向图，第i行的元素个数之和为Vi的出度（从Vi到其他顶点）

第i列的元素个数之和为Vi的入度（从其他顶点到Vi）

时间复杂度和空间复杂度

用邻接矩阵存储图，占用的存储空间大小与顶点数有关，与边数无关。

时间复杂度为O(n²)

图的邻接表

概念定义：

邻接表是图的一种链式存储结构，图中的每一个顶点对应一个结点，并由所有顶点结点构成一个顺序表结构（竖着的链）

图中每一个顶点建立一条链，该链由它的所有邻接点构成（横着的链）

代码定义

typedef struct Anode
{	int Vi; //邻接点在顺序表中的位置
	int Wi; //权值(用于网。图可省略)
	struct Anode *next; //指向下一个邻接点
} ALink; //邻接点存储结构
typedef struct Vnode
{	Type data;
	ALink *Vh; //邻接点链表头指针
} Vnode; //链表头指针结构
typedef struct
{	Vnode V [N];  //链表头顺序表
	int n,m;  //实际顶点数，边或弧数
	int visited[N];  //访问标识
} AList; //图的邻接表存储结构

从邻接表判断度数

无向图：顶点的度=邻接点链表中结点的数目

有向图：顶点的出度=邻接点链表中结点的数目

时间复杂度和空间复杂度

用邻接表存储图，占用的存储空间大小与顶点数和边数都有关。

时间复杂度为O(n²)

图的遍历

深度优先搜索遍历(更适用于找一条路径)

基本思想：

①从图中某个顶点v出发，访问该顶点

②查找顶点v的第一个未被访问的邻接点v1，访问该顶点。

③重复第二步操作，直到图中没有未被访问的顶点为止。

广度优先搜索遍历(更适用于找最优路径)

基本思想：

（1）从连通图中某个顶点v出发，访问该顶点，并置visited[v]的值为true，然后将v进队。

（2）只要队列不空，则重复下述处理：

①队头顶点u出队

②依次检查u的所有邻接点w，如果visited[w]的值为false，则访问w，并置visited[w]的值为true，然后将w进队。

代码

void BFS(AList G, int k)
{	G.visited[N]={0};	//访问标识初始化
	Visit(k);	//访问顶点k（或者写cout<<k<<endl;也可以）
	G.visited[k-1]=1;	//顶点k已访问
	f=0,r=0,Q[N]={0}; //队列Q[]初始化
	Q[r++]=k-1;  //入队, r:队尾指针
	while(r>=f)	//当队列非空时
	{	i=Q[f++];  //出队, f:队首指针
        p=G.V[i].Vh;//p是V[i]的链表头指针
		while(p)//顺序访问链表的各个结点
		{	
            j=p->Vi; // j是邻接点在顺序表中的位置
			if(!G.visited[j])
			{	Visit(j+1); //访问顶点j+1
				visited[j]=1;
				Q[r++]=j; //入队
			}
          	p=p->next;
		}
	}
} //算法结束

以邻接表作存储结构时，深搜和广搜的时间复杂度都为O(n+e)

最小生成树

定义：无向图G的所有生成树中各边权值之和最小的一颗生成树。

Prim算法：加点法

任取一个顶点v作为生成树的根，然后往生成树上添加新顶点u，顶点u满足其与生成树上某个顶点连通，并且在所有与生成树连通的边中权值最小，不断往生成树上添加顶点至生成树包含所有顶点为止。

K算法：加边法

为使生成树上边的权值之和达到最小，应使生成树中每一条边的权值尽可能地小(都能最小则最佳)。

例：请描述出用K算法得到最小生成树的步骤

①先构造一个只含n个顶点的子图S

②然后从权值最小的边开始，若它的添加不使S中产生回路，则在S上加上这条边

③如此重复，直至加上n-1条边为止。

拓扑排序

拓扑排序的一般操作方法：

(1)从有向图中选取一个入度为0的顶点，输出它;

(2)从有向图中删去该顶点以及所有以它为尾的弧;

重复上述两步，直至图空或者找不到入度为0的顶点为止。

时间复杂度为O(n+m)

数据结构期末复习

第四章图