【C/C++ 数据结构 】无向图和有向图的差异

简介: 【C/C++ 数据结构 】无向图和有向图的差异

无向图和有向图的主要区别确实在于边的方向,但这个区别导致了它们在许多方面的不同,包括它们的应用、性质和解决问题的方法。以下是一些主要的不同点:

边的方向

  • 无向图:边没有方向。如果存在一条边 ( (u, v) ),则 ( u ) 和 ( v ) 是相邻的,可以从 ( u ) 到 ( v ) 或从 ( v ) 到 ( u )。
  • 有向图:边有方向。如果存在一条边 ( (u, v) ),则可以从 ( u ) 到 ( v ),但不一定能从 ( v ) 到 ( u )。

度数

  • 无向图:每个顶点有一个度数,等于与其相连的边的数量。
  • 有向图:每个顶点有入度和出度两个度数,入度是指向该顶点的边的数量,出度是从该顶点出发的边的数量。

路径和连通性

  • 无向图:如果存在一条从顶点 ( A ) 到顶点 ( B ) 的路径,则必定存在一条从顶点 ( B ) 到顶点 ( A ) 的路径。
  • 有向图:从顶点 ( A ) 到顶点 ( B ) 的路径的存在并不保证从顶点 ( B ) 到顶点 ( A ) 也有路径。

应用

  • 无向图:常用于表示双向关系,如社交网络中的友谊关系。
  • 有向图:常用于表示单向关系,如网页之间的超链接关系。

算法

  • 由于这些差异,无向图和有向图在算法处理上也有很大的不同,如在寻找最短路径、判断图的连通性等问题上。

总的来说,虽然无向图和有向图的主要区别在于边的方向,但这个区别导致了它们在许多方面的显著不同。

C++ 实现上的差异

在C++中实现有向图和无向图时,最大的差异体现在边的存储和操作上。以下是一些主要的区别:

边的存储

  • 无向图:每条边存储两次。如果存在一条边 ( (u, v) ),那么在邻接表或邻接矩阵中,你需要在 ( u ) 的邻接列表中添加 ( v ),并在 ( v ) 的邻接列表中添加 ( u )。
  • 有向图:每条边只存储一次。如果存在一条从 ( u ) 到 ( v ) 的边,那么你只需要在 ( u ) 的邻接列表中添加 ( v )。

边的操作

  • 无向图:添加或删除边时,需要对两个顶点进行操作。
  • 有向图:添加或删除边时,只需要对一个顶点进行操作。

示例代码

以下是使用邻接列表实现无向图和有向图的简单示例:

无向图
#include <iostream>
#include <vector>
using namespace std;
class UndirectedGraph {
public:
    vector<vector<int>> adjList;
    UndirectedGraph(int vertices) {
        adjList.resize(vertices);
    }
    void addEdge(int u, int v) {
        adjList[u].push_back(v);
        adjList[v].push_back(u); // 无向图,需要添加两次
    }
};
有向图
#include <iostream>
#include <vector>
using namespace std;
class DirectedGraph {
public:
    vector<vector<int>> adjList;
    DirectedGraph(int vertices) {
        adjList.resize(vertices);
    }
    void addEdge(int u, int v) {
        adjList[u].push_back(v); // 有向图,只需要添加一次
    }
};

在这两个示例中,你可以看到无向图在添加边时需要对两个顶点进行操作,而有向图只需要对一个顶点进行操作。这是它们在实现方式上的主要差异。当然,这只是一个简单的示例,实际应用中可能还需要考虑更多的因素,如边的权重、图的稀疏性/密集性等。

结语

在我们的编程学习之旅中,理解是我们迈向更高层次的重要一步。然而,掌握新技能、新理念,始终需要时间和坚持。从心理学的角度看,学习往往伴随着不断的试错和调整,这就像是我们的大脑在逐渐优化其解决问题的“算法”。

这就是为什么当我们遇到错误,我们应该将其视为学习和进步的机会,而不仅仅是困扰。通过理解和解决这些问题,我们不仅可以修复当前的代码,更可以提升我们的编程能力,防止在未来的项目中犯相同的错误。

我鼓励大家积极参与进来,不断提升自己的编程技术。无论你是初学者还是有经验的开发者,我希望我的博客能对你的学习之路有所帮助。如果你觉得这篇文章有用,不妨点击收藏,或者留下你的评论分享你的见解和经验,也欢迎你对我博客的内容提出建议和问题。每一次的点赞、评论、分享和关注都是对我的最大支持,也是对我持续分享和创作的动力。

目录
相关文章
|
3天前
|
设计模式 算法 搜索推荐
C++数据结构设计:理解并选择策略模式与模板特化
C++数据结构设计:理解并选择策略模式与模板特化
47 2
|
3天前
|
算法 Go 数据库
数据结构/C++:位图 & 布隆过滤器
数据结构/C++:位图 & 布隆过滤器
12 0
|
3天前
|
存储 算法 C++
数据结构/C++:哈希表
数据结构/C++:哈希表
9 2
|
3天前
|
存储 算法 Java
数据结构/C++:红黑树
数据结构/C++:红黑树
15 3
|
3天前
|
存储 算法 C++
数据结构/C++:AVL树
数据结构/C++:AVL树
10 2
|
3天前
|
存储 C语言 C++
数据结构/C++:二叉搜索树
数据结构/C++:二叉搜索树
13 1
|
3天前
|
存储 数据库 C++
高效处理大规模数据集的概率型数据结构—— 布隆过滤器 [C++入门]
高效处理大规模数据集的概率型数据结构—— 布隆过滤器 [C++入门]
16 0
|
3天前
|
安全 程序员 编译器
【C/C++ 常用关键字使用指南】C++ 关键字 在头文件和源文件中函数声明与定义使用上的差异
【C/C++ 常用关键字使用指南】C++ 关键字 在头文件和源文件中函数声明与定义使用上的差异
96 0
|
3天前
|
存储 算法 调度
【C/C++ 数据结构 优先队列】了解学习`std::priority_queue`的使用
【C/C++ 数据结构 优先队列】了解学习`std::priority_queue`的使用
49 3
|
3天前
|
Linux API C++
【C++ 线程包裹类设计】跨平台C++线程包装类:属性设置与平台差异的全面探讨
【C++ 线程包裹类设计】跨平台C++线程包装类:属性设置与平台差异的全面探讨
57 2