稠密图和稀疏图（外加图例题）*

2024-07-10 05:17| 来源: 网络整理| 查看: 265

用n表示图中顶点数目，用e表示图中边或弧的数目（若图中边或弧上有权，则该图称为网）

稀疏图: e < nlogn 邻接表存储稠密图: e > nlogn 邻接矩阵存储

原因： 1. 邻接表只存储非零节点，而邻接矩阵则要把所有的节点信息(非零节点与零节点)都存储下来。 2. 稀疏图的非零节点不多，所以选用邻接表效率高，如果选用稠密图就会造成很多空间的浪费，矩阵中大多数都会是零节点！稠密图的非零界点多，零节点少，选用邻接矩阵是最适合不过！

//有向图拓扑排序 vector e; vector deg; vector topsort(int n, vector &cond) { e.clear(); e.resize(n + 1, vector()); deg.clear(); deg.resize(n + 1); for (auto &vec : cond) { e[vec[0]].push_back(vec[1]); deg[vec[1]]++; } queue q; for (int i = 1; i

【本文地址】

公司简介

联系我们