1. 概念
图是一种复杂的非线性结构。图G由两个集合V(顶点Vertex)和E(边Edge)组成，定义为G=(V，E)
2. 分类
2.1 按照边的类型分类
图的边有两种类型：
| No. | 边的类型 | 说明 |
|---|---|---|
| 1 | 无向边(Undirected Edge) | 顶点V1到顶点V2的边没有方向。用无序偶对 |
| 2 | 有向边/弧(Directed Edge)/(Arc) | 顶点V1到顶点V2的边有方向。用有序偶对 |
权(Weight)：与图的边或者弧关联的数值(权值可正可负可为零)
按照边的类型，图可以分为三类：
-
无向图(Undigraph)：任意两顶点之间的边都是无向边
- 无向图表示：
- 顶点集合：
- 边集：
- 无向图表示：
-
有向图(Digraph)：任意两顶点之间的边都是有向边
- 无向图表示：
- 顶点集合：
- 边集：
- 无向图表示：
混合图(Mixed Graph)：有向边与无向边同时存在的图。
2.2 按照边上是否带有数值
- 有权图/网(Network)：图的边或者弧有关联的数值
- 无权图：图的边或者弧有关联的数值
2.3 按照边数多少分类
稀疏图(Sparse Graph)
有很少条边或弧(边数远小于顶点数平方
)
稠密图(Dense Graph)
有很多条边或弧(边数
2.4 其他
图的种类
-
简单图(Simple Graph)：没有自环边没有平行边的图。
- 自环边：指向自己的边称为自环边。
- 平行边：两个节点之间的多条边成为平行边。
完全图(Complete Graph):每对顶点之间都恰连有一条边的图。
完全图通常使用，其中
表示定点数，例如
。
完全图属于简单图的特例。多重图(Multigraph)：含有平行边不含有自环边的图。
伪图(Pseudograph)：含有平行边和自环边的图。
二分图/二部图/偶图(Bipartite graph): 顶点可以分成两个不相交的集使得在同一个集内的顶点不相邻（没有共同边）的图。
一个图所有的节点不一定全部相连。
图的连通性：一个图可以有多个群体，群体中的点是连同的，不同群体间的点不连通；
2.5 总结
在计算机中通常讨论的图是稀疏的简单图。所以一般只分析以下四种。
| No. | 分类 | 简写 |
|---|---|---|
| 1 | 无方向/无权重 | U/U |
| 2 | 无方向/有权重 | U/W |
| 3 | 有方向/无权重 | D/U |
| 4 | 有方向/有权重 | D/W |
3. 表示法
3.1 对象顶点和边关系
图由顶点和边构成，这样就存在两种关系。
- 邻接关系(Adjacency)：顶点与顶点的关系
- 关联关系(Incidence)：顶点以及与它相关的边的关系
顶点的度(degree)：顶点相邻边数。
3.2 表示法
图的表示法有以下三种
- 邻接表(Adjacency List)
- 邻接矩阵(Adjacency Matrix)
- 关联矩阵(Incidence Matrix)
图的表示法
说明
- 无向图边数组是对称矩阵。
- 邻接矩阵和关联矩阵合适稠密图；邻接表合适稀疏图。实际中多数情况的图都是稀疏图。
- 邻接矩阵和关联矩阵使用数值
1表示顶点存在边，数值0表示顶点不存在边；网(Network)使用权值表示存在边，使用∞表示不存在边。 - 简单图的邻接矩阵主对角线全是
0
3.3 存储方式
| No. | 类型 | C++表示方式 |
|---|---|---|
| 1 | 邻接矩阵(Adjacency Matrix) | 顶点数据类型 [顶点数][顶点数] |
| 2 | 邻接表(Adjacency List) | vector<顶点数据类型>[顶点数] |
| 3 | 关联矩阵(Incidence Matrix) | 顶点数据类型 [顶点数][边数] |
- 无向图邻接表
#include <bits/stdc++.h>
using namespace std;
int main(){
int n = 0; // 顶点数
int m = 0; // 边数
scanf("%d%d",&n,&m);
vector<int> vec[n+1]; // 邻接表，下标表示顶点
for(int i=0;i<m;++i){
int u = 0;
int v = 0;
scanf("%d%d",&u,&v);
vec[u].push_back(v);
vec[v].push_back(u);// 无向图两个顶点要各记录一次
}
return 0;
}
- 有向图邻接表
#include <bits/stdc++.h>
using namespace std;
int main(){
int n = 0; // 顶点数
int m = 0; // 边数
scanf("%d%d",&n,&m);
vector<int> vec[n+1]; // 邻接表，下标表示顶点
for(int i=0;i<m;++i){
int u = 0;
int v = 0;
scanf("%d%d",&u,&v);
vec[u].push_back(v);
}
return 0;
}
一般情况通常使用邻接表存储图。*
3.4 通用接口
| No. | 操作 | 接口 |
|---|---|---|
| 1 | 获取边数 | int GetEdgeCount() |
| 2 | 获取顶点数 | int GetVertexCount() |
| 3 | 判断两点两点有边/相邻 | bool HashEdge(int v,int w) |
| 4 | 获取顶点v的度 |
int GetDegree(int v) |
| 5 | 获取顶点v的邻接顶点 |
vector<int> GetAdjVertex(int v) |
4. 图的遍历(Traversing Graph)
4.1 基本原理
- 深度优先遍历(DFS:Depth First Search)
- 广度优先遍历(BFS:Breadth First Search)
4.2 基本框架
| 遍历 | 技术 |
|---|---|
| DFS | 栈/递归(LIFO,先进先出) |
| BFS | 队列(FIFO,先进先出) |
DFS基本流程
- 流程说明
- 标记当前访问的顶点。
- 遍历当前的所有邻接顶点，如果未被访问，继续1。
- 基本框架
非递归方式
递归方式void DFS(int v,vector<int>* vec,int n){ bool visited[n]; // 定义标记顶点是否已访问 fill_n(visited,n,false); // 初始化为未访问 stack<int> s; // 使用栈 s.push(v); while(!s.empty()){ int now = s.top(); visited[now] = true;// 出栈时记录已被访问 s.pop(); for(int i=0;i<vec[now].size();++i){ int post = vec[now][i]; if(!visited[post]){ s.push(post); } } } }... bool visited[n]; fill_n(visited,n,false); // 初始化为未访问 ... int DFS(int v,vector<int>* vec){ visited[v] = true; // 标记v已经访问 for (int i = 0; i < vec[v].size(); i++) { // 遍历v的邻接点 int post = vec[v][i]; if (!visited[post]) { // 判断邻接点是否访问 DFS(post, vec); // 访问邻接点 } } } - 标记访问
经常使用布尔值数组表示是否被访问。
BFS基本流程
-
流程说明
- 标记起始顶点已访问，并入队起始顶点
- 队列判空，非空则出队。
- 遍历出队顶点的邻接点，依次判断是否已被访问。如果未被访问，标记已访问，并且入队。
-
基本框架
void BFS(int v,vector<int>* vec,int n){ queue<int> q; // 定义队列 bool visited[n]; // 定义标记顶点是否已访问 fill_n(visited,n,false); // 初始化为未访问 visited[v] = true; // 标记v已经访问 q.push(v); // 入队v while (!q.empty()) { // 队列非空 int now = q.front(); // 取出队首元素 q.pop(); // 队首元素出队 for (int i = 0; i < vec[now].size(); i++) { // 遍历v的邻接点 int post = vec[now][i];// 取出邻接点 if (!visited[post]) { // 判断邻接点是否访问 visited[post] = true;// 标记邻接点已访问 q.push(post); // 邻接点入队 } } } } 说明
入队表示等待访问它的邻接点;
出队表示马上访问它的邻接点;标记访问
经常使用布尔值数组表示是否被访问。注意
有时直接使用数组下标作为顶点的标识，所以需要注意顶点是否从0开始。
应用
获取图DFS和BFS后的元素序列。把二维网状结构转变成一维线性结构
vector<int> bfs(vector<int>* vec, int v){
vector<int> res;
queue<int> q; // 使用队列
res.push_back(v);
q.push(v);
while(!q.empty()){
int now = q.front();
q.pop();
for(int i=0;i<vec[now].size();++i){
int post = vec[now][i];
if(find(res.begin(),res.end(),post) == res.end()){
res.push_back(post); // 入队时记录已被访问
q.push(post);
}
}
}
return res;
}
vector<int> dfs(vector<int>* vec, int v){
vector<int> res;
stack<int> s; // 使用栈
s.push(v);
while(!s.empty()){
int now = s.top();
res.push_back(now);// 出栈时记录已被访问
s.pop();
for(int i=0;i<vec[now].size();++i){
int post = vec[now][i];
if(find(res.begin(),res.end(),post) == res.end()){
s.push(post);
}
}
}
return res;
}
1971. 寻找图中是否存在路径
class Solution {
vector<vector<int>> graph;
set<int> visited;
public:
// 递归DFS
bool DFS(int source, int destination) {
if(visited.count(source)) return false; // 访问过的节点
visited.insert(source);
if(source == destination) return true;
bool res = false;
for(auto m:graph[source]){
res |= DFS(m,destination);
}
return res;
}
// 迭代DFS
bool DFS(int source, int destination) {
stack<int> s;
s.push(source);
while(!s.empty()){
int n = s.top();s.pop();
if(visited.count(n)) continue; // 访问过的节点
visited.insert(n);
if(n == destination) return true;
for(auto m:graph[n]) s.push(m);
}
return false;
}
// 迭代BFS
bool BFS(int source, int destination) {
queue<int> q;
q.push(source);
while(!q.empty()){
int n = q.front();q.pop();
if(visited.count(n)) continue; // 访问过的节点
visited.insert(n);
if(n == destination) return true;
for(auto m:graph[n]) q.push(m);
}
return false;
}
bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
// 构造邻接表
graph.resize(n);
for(auto edge:edges){
auto v = edge[0];
auto u = edge[1];
graph[v].push_back(u);
graph[u].push_back(v);
}
return DFS(source,destination);
}
};
