一、图的基本概念
1.1 图的定义
图G由顶点集V和边集E组成，记为G = (V, E)，其中V(G)表示图G中顶点的有限非空集；E(G)表示图G中顶点之间的关系(边集合)。若V={v1, v2...vn}，则用|V|表示图G中顶点的个数，E={(u, v)| u∈V, v ∈ V}，用|E|表示图G中的边数。
1.1.1 有向图
不多解释，有方向指向的图。
1.1.2 无向图
同上。
1.1.3 简单图、多重图
如果一个图满足：
- 不存在重复的边；
- 不存在顶点到自身的边。
那么该图就称为简单图。若图G中两个顶点之间的边数大于1条，又允许顶点通过一条边和自身相连，则图G称为多重图。
1.1.4 完全图
对于无向图，任意两个顶点之间都存在边。对于有向图，表述则是：总能从一个顶点到达另一个顶点。
1.1.5 子图
有两个图G = (V, E)和G1 = (V1, E1)，若V1是V的子集，且E1是E的子集，则称图G1是图G的子图。
1.1.6 通道、连通图和连通分量
在无向图中，若顶点v到顶点w有路径存在，则称v和w是连通的。若图G中任意两个顶点都是连通的，则称图G为连通图，否则称为非连通图。无向图中的极大连通子图，称为连通分量。
1.1.7 强连通图、强连通分量
在有向图中，若一对顶点w和v，若可从w到v、可从v到w。那么w和v之间是强连通的。其余概念与上述连通图相同。
1.1.8 生成树、生成森林
对于一个连通图G，若其一个子图G1是一颗包含G所有顶点的树，则该子图称为G的生成树。生成树是包含图G所有顶点的极小连通子图。
1.1.9 顶点的度、入度和出度
在无向图中，顶点v的度是指依附于顶点v的边的条数。
在有向图中，出度是从v出发的边数，入度是到达v的边数。
1.1.10 边、权和网
在图中，每条边上都可以标上某种数值，该数值被称为边的权值。这种边上带权值的图称为带权图，也称为网。
1.1.11 稀疏图、稠密图
边很少的图叫稀疏图，边很多的图叫稠密图。一般当图G满足|E|<|V|log|V|，可以将图G是为稀疏图。
1.1.12 路径、路径长度和回路
顶点vp到顶点vq之间的一条路径是指顶点序列vp...vi...vq。路径上边的数目称为路径长度。第一个顶点和最后一个顶点相同的路径，称为回路或环。
1.1.13 简单路径、简单回路
顶点不重复，即简单。
1.1.14 距离
从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。若不存在路径，则距离为无穷。
1.1.15 有向树
一个顶点入度为0，其余顶点的入度均为1的有向图，称为有向树。
二、图的存储及基本操作
2.1 邻接矩阵法
用一个一维数组存放图中的顶点信息，用一个二维数组存放图中的边的信息。存储顶之间邻接关系的二维数组称为邻接矩阵。
struct MGraph
{
int vertex[num];
int graph[num][num];
int vexnum, arcnum;
// 当前节点的顶点数 和 弧数
};
在上述图中，我们可以通过graph[1][3] = 1表示从vertex[1]可以到达vertex[3]（下标）；同样，使用[2][1] = 0表示不可到达。这里需要区分有向图和无向图，无向图是对称的，有向图则不是。
2.2 邻接表法
为了解决邻接矩阵利用率低的问题，这里使用邻接表来完成。
// 邻接节点
struct ArcNode
{
int adjvex; // 邻接节点编号
ArcNode* next; // 指向下一个节点
}
// 邻接表
struct AdjList
{
std::list<ArcNode*> ArcList; // 顶点列表
int vexnum, arcnum;
// 当前节点的顶点数 和 弧数
}
为了更好地理解邻接表与邻接矩阵之间的转化，我们给出如下例题：
Description
给一个带权有向图的邻接矩阵表示，将之转换为邻接表的表示，并输出对应的邻接表
Input
第一行：两个整数m（图的节点数），n（图的边数）（0 < n,m < 100,）。余下n行：n*n矩阵，代表矩阵表示下的图（其中以非零表示有链接,数字间以空格隔开）
Output
输出有m行，对应m个节点的邻接表示下的节点连接情况
Sample Input
6 10
0 5 0 7 0 0
0 0 4 0 0 0
8 0 0 0 0 0
0 0 5 0 0 6
0 0 5 0 0 0
3 0 0 0 1 0
Sample Output
0:1 3
1:2
2:0
3:2 5
4:2
5:0 4
2.3 十字链表与邻接多重表
p 208; 后面要考再补充。
三、图的遍历
3.1 广度优先搜索 BFS
题目描述
图的广度优先搜索类似于树的按层次遍历，即从某个结点开始，先访问该结点，然后访问该结点的所有邻接点，再依次访问各邻接点的邻接点。如此进行下去，直到所有的结点都访问为止。在该题中，假定所有的结点以“A”--“Z”中的若干字符表示，且要求结点的访问顺序根据录入的顺序进行访问。如果结点录入的顺序为HUEAK，要求从H开始进行广度优先搜索，则可能的搜索结果为：H->E->A->U->K.
输入
第一行为一个整数n，表示顶点的个数，第二行为n个大写字母构成的字符串，表示顶点，接下来是为一个n*n大小的整数矩阵，表示图的邻接关系。数字为0表示不邻接，否则为相应的边的长度。最后一行为一个字符，表示要求进行广度优先搜索的起始顶点。
输出
用一行输出广度优先搜索结果，起始点为给定的顶点。
样例输入
5
HUEAK
0 0 2 3 0
0 0 0 7 4
2 0 0 0 0
3 7 0 0 1
0 4 0 1 0
H
样例输出
HEAUK
#include <iostream>
#include <vector>
#include <string>
#include <deque>
// 节点元素
struct Node
{
int id; // 节点序号
bool flag; // 是否访问过
char ele; // 存储的元素
std::vector<int>list; // 当前节点的路径, 0表示不可到达[i]节点, n表示可到达[i]节点
// 构造函数
Node():
flag{ true }, ele{ '\0' }
{ }
};
/*
BFS搜索函数
返回值：BFS遍历的结果
参数1：顶点数组
参数2：搜索起点
*/
std::string BFS(std::vector<Node> Vertex,
Node Begin);
int main()
{
/* ========== Section I : 数据准备 ========== */
// 图的大小
int size{ 0 };
// 顶点元素
std::string Vertex_ele;
// 顶点
std::vector<Node> Vertex;
// 录入大小和顶点
std::cin >> size >> Vertex_ele;
// 顶点大小改变
Vertex.resize(size);
// 读入数据
for (int i = 0; i < size; ++i)
{
// ele赋值
Vertex[i].ele = Vertex_ele.at(i);
Vertex[i].id = i;
// list赋值
for (int j = 0; j < size; ++j)
{
int input{ 0 };
std::cin >> input;
Vertex[i].list.push_back(input);
}
}
// 开始搜索的元素，即搜索起点
char BeginCh;
std::cin >> BeginCh;
/* ========== Section II : BFS ========== */
// 定位搜索起点
for (int i = 0; i < size; ++i)
{
if(Vertex[i].ele == BeginCh)
{
std::cout << BFS(Vertex, Vertex[i]);
break;
}
}
return 0;
}
std::string BFS(std::vector<Node> Vertex, Node Begin)
{
// BFS遍历队列
std::deque<Node> Trans;
Trans.push_back(Begin);
// 返回值
std::string re;
// 开始遍历
while(!Trans.empty())
{
// 队首
Node head = Trans.front();
Trans.pop_front();
// 访问元素 这里需要判断是否可以访问
if (Vertex[head.id].flag == true)
{
re.push_back(head.ele);
}
else
{
continue;
}
// 队首节点flag置0
Vertex[head.id].flag = false;
// 查找head可到达的节点
for (int i = 0; i < Vertex.size(); ++i)
{
if (head.list[i] != 0 // 可到达
&& Vertex[i].flag == true) // 未访问
{
Trans.push_back(Vertex[i]);
}
}
}
return re;
}
3.1.1 BFS性能分析
空间复杂度
O(vertex)，需要至多size == vertex的队列。
时间复杂度
O(vertex)，最坏情况下每个点都要入队一次。
3.1.2 BFS最短路径
利用广度优先搜索总是按距离遍历的特性，我们可以利用它来求最短路径。下面我们计算从vBegin到vEnd的距离，即我们只需要在while循环里面加入一个distence++即可。但是需要注意的是，我们这里遍历，不再是每次取出头结点遍历，而是取出队列里面所有节点（即一层）循环一次，即我们使用层次遍历计算距离。
int BFS(std::vector<Node> Vertex, Node Begin)
{
// BFS遍历队列
std::deque<Node> Trans;
Trans.push_back(Begin);
// 返回值
std::string re;
int distance = 0;
// 开始遍历 - 每次循环遍历一层
while(!Trans.empty())
{
// 取出队列所有元素
std::list<Node> nodes = all nodes in deque(Trans);
// 判断节点是否可以遍历
for (auto node : nodes)
{
// 判断是否可以遍历
if (node.flag == true)
{
// node flag置0，并随后访问
node.flag = false;
}
else if (node.flag == false)
{
// node 移除出list
nodes.remove(node);
}
}
// 访问所有节点
for (auto node : nodes)
{
// 访问，并将其可到达的节点压入队列
if (node.list[i] != 0 // 可到达
&& Vertex[i].flag == true) // 未访问
{
Trans.push_back(Vertex[i]);
}
}
// 每一层的距离
distance++;
}
return distance;
}
3.2 深度优先搜索 DFS
题目描述
图的深度优先搜索类似于树的先根遍历，即从某个结点开始，先访问该结点，然后深度访问该结点的第一棵子树，依次为第二顶子树。如此进行下去，直到所有的结点都访问为止。在该题中，假定所有的结点以“A”至“Z”中的若干字符表示，且要求结点的访问顺序根据录入的顺序进行访问。如果结点录入的顺序为HUEAK，从H开始进行深度优先搜索，则可能的搜索结果为：H->A->K->U>E.
输入
第一行为一个整数n，表示顶点的个数，第二行为n个大写字母构成的字符串，表示顶点，接下来是为一个n*n大小的整数矩阵，表示图的邻接关系。数字为0表示不邻接，否则为相应的边的长度。最后一行为一个字符，表示要求进行深度优先搜索的起始顶点。
输出
用一行输出深度优先搜索结果，起始点为给定的顶点。
样例输入
5
HUEAK
0 0 2 3 0
0 0 0 7 4
2 0 0 0 0
3 7 0 0 1
0 4 0 1 0
H
样例输出
HEAUK
#include <iostream>
#include <vector>
#include <string>
#include <deque>
// 节点元素
struct Node
{
int id; // 节点序号
bool flag; // 是否访问过
char ele; // 存储的元素
std::vector<int>list; // 当前节点的路径, 0表示不可到达[i]节点, n表示可到达[i]节点
// 构造函数
Node():
flag{ true }, ele{ '\0' }
{ }
};
std::string ans; // 遍历结果
/*
DFS搜索函数
返回值：void
参数1：顶点数组
参数2：当前节点
*/
void DFS(std::vector<Node>& Vertex, Node& node);
int main()
{
/* ========== Section I : 数据准备 ========== */
// 图的大小
int size{ 0 };
// 顶点元素
std::string Vertex_ele;
// 顶点
std::vector<Node> Vertex;
// 录入大小和顶点
std::cin >> size >> Vertex_ele;
// 顶点大小改变
Vertex.resize(size);
// 读入数据
for (int i = 0; i < size; ++i)
{
// ele赋值
Vertex[i].ele = Vertex_ele.at(i);
Vertex[i].id = i;
// list赋值
for (int j = 0; j < size; ++j)
{
int input{ 0 };
std::cin >> input;
Vertex[i].list.push_back(input);
}
}
// 开始搜索的元素，即搜索起点
char BeginCh;
std::cin >> BeginCh;
/* ========== Section II : BFS ========== */
// 定位搜索起点
for (int i = 0; i < size; ++i)
{
if(Vertex[i].ele == BeginCh)
{
DFS(Vertex, Vertex[i]);
break;
}
}
std::cout << ans << std::endl;
return 0;
}
void DFS(std::vector<Node>& Vertex, Node& node)
{
// false 则返回
if (!node.flag) return;
// 访问元素
ans.push_back(node.ele);
// 标记flag为flase
node.flag = false;
// 遍历可到达的点
for (int i = 0; i < Vertex.size(); i++)
{
if (node.list[i] != 0)
{
DFS(Vertex, Vertex[i]);
}
}
}
3.2.1 DFS性能分析
空间复杂度
O(vertex)，需要借助栈实现提柜。
时间复杂度
以邻接矩阵表示时，查找每个顶点所需的时间为O(vertex)，总时间复杂度为O(vertex2)；以邻接表储存时，查找所有顶点所需时间为O(Edge)，总时间为O(Edge2)。
四、图的应用
4.1 最小生成树
4.1.1 Prim算法
void Prim(G, T)
{
/*
T : 树
U : 用于统计顶点是否全部加入树中
*/
T = nullptr; // 初始化树，使其为空
U = { w }; // 将任意一点w，添加入树
while (U.size() != G.size())
{
step 1: 寻找当前T集合与G图之间权值最小的两个点，即Tn和Gn。
step 2: 边Tn-Gn 加入 T中。
step 3: 顶点Gn 加入 U中。
}
}
4.1.2 Kruskal算法
void Kruskal(V, T)
{
/*
E : 边集合，用于存放所有的边以及其长度
*/
T = V; // 初始化树，仅含顶点
CC = n; // 联通分量 = 顶点数
while (CC > 1)
{
step 1: 从E中选出最短的边v-u。
step 2: 如果 u和v属于T中不同的联通分量，则此边加入T树、联通分量数CC--。
}
}
4.1.3 比较
在Prim算法中，时间复杂度为O(V2)；在Kruskal算法中，时间复杂度为O(E*logE)。