基础知识
图是一种网状数据结构，用于描述对象的集合以及对象之间的关系。其中，对象用顶点表示，也称为节点，简称点。对象之间的关系用连接顶点的边表示。若图中的每条边是单向的，则该图称为有向图；若图中的每条边是双向的，则该图称为无向图；若图中的每条边有权重，则该图称为加权图。研究图的数学分支被称为图论，这个我们以后会深入讲解。
图的表示
邻接矩阵
用一个二维数组标记两个节点是否相邻，$G_{i, j}$ 表示节点 $i$ 能否到达节点 $j$。若该图为加权图，则 $G_{i, j}$ 标记节点 $i$ 与节点 $j$ 之间的边权，如果没有边的话通常设置其为无穷大或 $-1$。
实现方式
int G[3500][3500];//声明部分
int n, m;//点数与边数
int main()
{cin >> n >> m;for (int i = 1; i <= m; ++ i){int u, v, w;cin >> u >> v;//不加权//cin >> w;//加权G[u][v] = true;//有向图//G[v][u] = true;//无向图//G[u][v] = w;//有向加权图//G[v][u] = w;//无向加权图}return 0;
}
邻接表
用邻接表更节省空间。其中 $G_i$ 存储节点 $i$ 能直接到达的节点。
实现方式
不加权图
vector<int> G[3500];//声明部分
int n, m;//点数与边数
int main()
{cin >> n >> m;for (int i = 1; i <= m; ++ i){int u, v;cin >> u >> v;//不加权G[u].push_back(v)//有向图//G[v].push_back(u)//无向图}return 0;
}
加权图
struct Node{int v, w;
};
vector<Node> G[3500];//声明部分
int n, m;//点数与边数
int main()
{cin >> n >> m;for (int i = 1; i <= m; ++ i){int u, v, w;cin >> u >> v;cin >> w;//加权G[u].push_back({v, w})//有向图//G[v].push_back({u, w})//无向图}return 0;
}
其实还有一种叫链式前向星的表示方式，后面会讲到。
连通图的遍历
深度优先遍历
选择一个顶点为起点（通常为 $1$ 号节点），并递归遍历其所有的邻接节点。为了防止一个节点被重复访问，我们需要一个 $vis$ 数组来标记一个节点有没有被访问过。
实现方式
void dfs(int u)
{cout << u << " ";vis[u] = true;for (auto v : G[u]){if (vis[v] == true){continue;}dfs(v);}
}
广度优先遍历
选择一个顶点为起点，再按照与起点的距离从小到大进行遍历，与广度优先搜索类似。
实现方式
void bfs(int s)
{queue<pair<int,int> > q;vis[s] = true;q.push({s, 0});while (!q.empty()){pair<int,int> t = q.front();q.pop();dis[t.first] = t.second;for(auto v:G[t.first]){if (vis[v] == true){continue;}vis[v] = true;cout << v << " ";}}
}
习题
基础
P5318 【深基18.例3】查找文献
P3916 图的遍历
P1113 杂务
拓展
P1807 最长路
P1363 幻象迷宫