Algorithm第四版算法 C++实现(十二)——使用邻接矩阵法构造无向图
2021/8/7 17:06:47
本文主要是介绍Algorithm第四版算法 C++实现(十二)——使用邻接矩阵法构造无向图,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
图是一种非常常见的数学模型。图在各种应用中都有非常重要的作用
我们今天要介绍的图叫做无向图,在无向图中,边仅仅起到链接两个顶点的作用。这是一种简单的图模型。
术语解释:
- 自环:一条链接一个顶点与他自身的边
- 平行边(无向图):两条及以上关联同一对顶点的无向边
- 多重图:有平行边的图
- 简单图:无平行边的图
- 度数(度):点作为边端点的次数
//邻接矩阵法构造无向图 class graph { private: int v; //顶点数 int e; //边数 std::vector<std::vector<int>> adj; public: graph(int v) { this->v = v; this->e = 0; adj.resize(v); } int numv() { return this->v; } int nume() { return e; } void add_edge(int v, int w) //这个插入方法还不够健壮,如果输入的参数比v要大会出错 { /* if(v<0||v>this->v) { printf("%a"); return; } if(w<0||w>this->v) { printf("%a"); return; } */ adj[v].push_back(w); adj[w].push_back(v); //无向图,所以两个顶点都需要处理 std::unique(adj.begin(), adj.end()); e++; } std::vector<int> *iterator(int v) //返回一个指向对应节点的数组的指针 { return &adj[v]; } int degree(int v) //返回度数 { int degree = 0; for (auto w : adj[v]) { degree++; } return degree; } int max_degree() //获取最大度 { int max = 0; for (unsigned int i=0;i<adj.size();i++) { if (degree(i) > max) max = degree(i); } return max; } int selfloop_num() //返回自反顶点的数量 { int count = 0; for (int i = 0; i < v; i++) { for (unsigned int j = 0; j < adj[i].size(); j++) { if (i == j) { count++; break; } } } return count; } std::string tostring() //获取矩阵信息的字符串 { std::string s; s = std::to_string(v) + " verticers" + std::to_string(e) + " edges\n"; for (unsigned int i=0;i<adj.size();i++) { s += std::to_string(i) + ":"; for (auto j:adj[i]) { s += std::to_string(j) + " "; } s += "\n"; } return s; } };
学过离散数学的读者可能还记得图邻接矩阵的定义,所以上述代码构造图的方式与我们当初接触的邻接矩阵是有区别的。对于这种方式,其优势是占用内存小,缺点则是相比之下更慢。
我个人更偏向第二种,但是此处书中貌似使用的是第一种。
运行结果
这篇关于Algorithm第四版算法 C++实现(十二)——使用邻接矩阵法构造无向图的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-20MongoDB教程:从入门到实践详解
- 2024-11-17执行 Google Ads API 查询后返回的是空数组什么原因?-icode9专业技术文章分享
- 2024-11-17google广告数据不同经理账户下的凭证可以获取对方的api数据吗?-icode9专业技术文章分享
- 2024-11-15SendGrid 的 Go 客户端库怎么实现同时向多个邮箱发送邮件?-icode9专业技术文章分享
- 2024-11-15SendGrid 的 Go 客户端库怎么设置header 和 标签tag 呢?-icode9专业技术文章分享
- 2024-11-12Cargo deny安装指路
- 2024-11-02MongoDB项目实战:从入门到初级应用
- 2024-11-01随时随地一键转录,Google Cloud 新模型 Chirp 2 让语音识别更上一层楼
- 2024-10-25Google Cloud动手实验详解:如何在Cloud Run上开发无服务器应用
- 2024-10-24AI ?先驱齐聚 BAAI 2024,发布大规模语言、多模态、具身、生物计算以及 FlagOpen 2.0 等 AI 模型创新成果。