图 图的存储
教程导读
学研发网的这篇信息学奥赛技术教程文章主要介绍了图 图的存储,现在分享给大家,供学习和参考。文章包含1224字,纯文字阅读大概需要4分钟。
教程信息
1、邻接矩阵
使用二维数组存储边的信息
对于一个 n 个点 m 条边的图,在使用邻接矩阵时,需要开一个n×n的数组,即空间复杂度O(n2) 。如需要得到图上所有的边,就需要遍历整个n×n数组,即遍历边时间复杂度O(n2) 。特别是当边比较少时,非常的不划算,因此适用于稠密图。
cin >> n; int v[n][n]; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> v[i][j]; // 存入每一对点之间的边权 for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (v[i][j] > 0) cout << "edge from point " << i << " to point " << j << " with length " << v[i][j] << '\n';
2、邻接表
每个顶点的相邻点用一个链表连接。解决了邻接矩阵空间浪费的问题,适用于稀疏图。
一般采用 vector 代替二维数组,使用 vector 存储第二维,从而减少空间占用。为了同时存储边的终点与边权,可以采用结构体。
对于一个 n 个点 m 条边的图,总的空间复杂度是 O(m) 的,即边的数目。
且遍历某个点相邻的节点的时间复杂度为 O(p) ,其中 p 为该点的出度,优于邻接矩阵。但如果需要指定查询或修改边<i,j>的边权,需要的时间复杂度为 O(p),不如邻接矩阵的 O(1)。
struct edge { int to, cost; // 记录边的终点,边权的结构体 }; int n, m; // 图有 n 个点 m 条边 vector < edge > p[MAXN]; // 邻接表 int v[MAXN][MAXN]; // 邻接矩阵 int main() { cin >> n >> m; for (int i = 1; i <= m; i++) { int u, v, l; cin >> u >> v >> l; //u和v之间有一条权值为l的边 p[u].push_back((edge) { v, l }); //p[v].push_back((edge){u, l}); 无向图邻接表要加一条反方向的边 } } //遍历邻接表,把邻接表转换为邻接矩阵 for (int i = 1; i <= n; i++) for (int j = 0; j < p[i].size(); j++) v[i][p[i][j].to] = p[i][j].cost;
教程咨询
如果章节内容看不懂,可以联系作者。
教程总结
以上是学研发网为您提供图 图的存储的全部内容,希望教程文章能够帮你了解学习图 图的存储,解决所遇到的问题。 如果觉得学研发网信息学奥赛教程内容还不错,欢迎将学研发网网站推荐给身边需要的人。
教程备注
版权声明:教程内容为学研发网整理和编写,如需转载请联系站长并附上文章原始链接和原始作者信息。
手机阅读
扫描二维码推送至手机访问。
本文链接:http://www.xueyanfa.com/xinaojiaocheng/xinaogaoji-298.html