探索图论:无向图、有向图、加权图与无权图

简介: 引言图论是数学中的一个精彩分支,通过图这种数据结构,我们可以更好地理解和分析现实世界中事物之间的关系。在图论中,有四种基本的图类型:无向图、有向图、加权图和无权图。本文将深入探讨这些图的概念,并通过C++代码示例帮助读者更加清晰地理解它们在抽象世界和实际问题中的应用。

图论索引

引言

图论是数学中的一个精彩分支,通过图这种数据结构,我们可以更好地理解和分析现实世界中事物之间的关系。在图论中,有四种基本的图类型:无向图、有向图、加权图和无权图。本文将深入探讨这些图的概念,并通过C++代码示例帮助读者更加清晰地理解它们在抽象世界和实际问题中的应用。


无向图:节点的对等关系

无向图是最简单的图类型之一,它描述了节点之间的对等关系。在无向图中,节点之间的连接是没有方向的,这意味着连接节点 A 和节点 B 的边与连接节点 B 和节点 A 的边是等价的。换句话说,无向图是一种没有箭头的图,它强调的是节点之间的连接而不关心流向。

#include

#include

#include


class UndirectedGraph {

public:

   void add_edge(int node1, int node2) {

       graph[node1].push_back(node2);

       graph[node2].push_back(node1);

   }


private:

   std::unordered_map> graph;

};

有向图:节点间的单向关系

有向图中,边是有方向的,这意味着连接节点 A 和节点 B 的边与连接节点 B 和节点 A 的边是不同的。有向图常用于表示一种单向的关系,例如在社交网络中,其中用户之间的关注关系就可以用有向图来表示。

#include

#include

#include


class DirectedGraph {

public:

   void add_edge(int node1, int node2) {

       graph[node1].push_back(node2);

   }


private:

   std::unordered_map> graph;

};

加权图:赋予边以权重

加权图是在边上赋予了权重的图,这些权重可以代表不同的信息,如距离、成本或其他度量。在加权图中,边不仅表示连接,还携带了额外的重要信息,这使得加权图在求解最短路径、最小生成树等问题中有着广泛的应用。


#include

#include

#include

#include


class WeightedGraph {

public:

   void add_edge(int node1, int node2, int weight) {

       graph[node1].emplace_back(node2, weight);

       graph[node2].emplace_back(node1, weight);

   }


private:

   std::unordered_map>> graph;

};

无权图:简洁连接关系

无权图是最简单的图类型,它只关注节点之间是否相连,而不考虑连接的强度或其他属性。无权图常常用于描述简单的关系,如朋友关系、交通路线等,它们强调的是节点之间的连接本身。

#include

#include

#include


class UnweightedGraph {

public:

   void add_edge(int node1, int node2) {

       graph[node1].push_back(node2);

       graph[node2].push_back(node1);

   }


private:

   std::unordered_map> graph;

};

结论

图论作为数学和计算机科学领域的重要分支,为我们提供了一种强大的工具来研究和解决各种问题。无向图、有向图、加权图和无权图作为图论中的基本图类型,在不同的领域和场景中扮演着重要角色。通过本文的介绍和C++代码示例,希望读者能够更加深入地理解这些图的概念及其应用,从而为解决实际问题提供新的思路和方法。

目录
相关文章
|
6月前
|
存储
第5章 图的遍历
第5章 图的遍历
|
7月前
|
存储 算法
有向图和无向图的表示方式(邻接矩阵,邻接表)
有向图和无向图的表示方式(邻接矩阵,邻接表)
395 0
|
7月前
|
算法
图的应用(最小生成树,最短路径,有向无环图)
图的应用(最小生成树,最短路径,有向无环图
54 0
|
7月前
|
人工智能 算法 测试技术
【图论】【拓扑排序】1857. 有向图中最大颜色值
【图论】【拓扑排序】1857. 有向图中最大颜色值
|
7月前
|
NoSQL 容器 消息中间件
图、图的遍历及图的拓扑排序
图、图的遍历及图的拓扑排序
|
存储
图操作之邻接矩阵与邻接表的深度优先遍历
图操作之邻接矩阵与邻接表的深度优先遍历
211 0
|
机器学习/深度学习
有向图,无向图的邻接矩阵和邻接表模板
有向图,无向图的邻接矩阵和邻接表模板
204 0
有向图,无向图的邻接矩阵和邻接表模板

热门文章

最新文章