【数据结构与算法】图论-你曾虐我千百遍，我却待你如初恋

2024-02-26 02:40
文章标签 算法 数据结构 图论 千百遍 初恋

本文主要是介绍【数据结构与算法】图论-你曾虐我千百遍，我却待你如初恋，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

作为数据结构中最难的一个结构，图。可以说是折磨了笔者整个大学时光。本想着终于可以摆脱了，谁能想到阴差阳错的，要去做这个DAG。

基础概念

有向无环图

有向无环图指的是一个没有回路的有向图，简单的说就是没有撤退可言。在图论中，如果一个人有向图无法从某个顶点出发，经过若干条边回到该顶点，则这个图是一个有向无环图（DAG图）。那么现在一个小的问题来了。什么是有向图？什么是图？

图

图G由顶点集V和边集E组成，记为G=(V,E)，其中V(G)表示图G中顶点的有限非空集；E(G)表示图G中顶点之间的关系(边)的集合。

概念这玩意从来是让人看的。我知道大家有人肯定没看懂。但这个没关系，我来解释就好了。先看下面的这张图:

现在我们再来看这个概念，什么叫顶点集，图中的 A,B,C,D,E,F ,这就是一个顶点集，也就是一个V的集合。集合内的元素是A,B,C,D,E,F。再来看什么叫做边集。我们可以看到，A->B,是不是有一个连线，去连接AB？这条线就是边。边组成的集合，我们称为边集。也就是说，一个E的集合。集合内元素是 AB,AC,BE,EF,EG 组成的集合。

这就是图的概念。图的概念理解后，现在就是有哪些图了。一般我们会根据图是否是闭合的，分为有环图和无环图。无环图就是指，无论你从哪个顶点走，你都不会回来的。根据我们的边的是否有方向分为有向图和无向图。这里我们讨论有向图。

有向图

前面说了图的概念，现在来看有向图。由于有向图的边是有方向性的，所以我们在表示有向图的时候，需要注意我们的方向不要错了。前面的举的例子，就是一个有向图，而且是无环的。

相关术语

这里的关于图的术语，会比较多，遇到了参考下就好了，一般用用就会了。

  • 顶点：图中的一个点
  • 边：连接两个顶点的线段叫做边，edge
  • 相邻的：一个边的两头的顶点称为是相邻的顶点
  • 度数：由一个顶点出发，有几条边就称该顶点有几度，或者该顶点的度数是几，degree
  • 路径：通过边来连接，按顺序的从一个顶点到另一个顶点中间经过的顶点集合
  • 简单路径：没有重复顶点的路径
  • 环：至少含有一条边，并且起点和终点都是同一个顶点的路径
  • 简单环：不含有重复顶点和边的环
  • 连通的：当从一个顶点出发可以通过至少一条边到达另一个顶点，我们就说这两个顶点是连通的
  • 连通图：如果一个图中，从任意顶点均存在一条边可以到达另一个任意顶点，我们就说这个图是个连通图
  • 无环图：是一种不包含环的图
  • 稀疏图：图中每个顶点的度数都不是很高，看起来很稀疏
  • 稠密图：图中的每个顶点的度数都很高，看起来很稠密
  • 二分图：可以将图中所有顶点分为两部分的图、
    在 有向图 中，我们一般还会有这样的术语：
  • 出度：由一个顶点出发的边的总数
  • 入度：指向一个顶点的边的总数

接着，由于有向图的方向性，一条边的出发点称为头，指向点称为尾。

  • 有向路径：图中的一组顶点可以满足从其中任意一个顶点出发，都存在一条有向边指向这组顶点中的另一个。

  • 有向环：至少含有一条边的起点和终点都是同一个顶点的一条有向路径。

  • 简单有向环：一条不含有重复顶点和边的环。

  • 路径或环的长度就是他们包含的边数。

算法实现

这里我使用的是Java语言。仅供大家参考。
首先看我的程序的基本结构：

大家看到这个结构图，也能知道DAGGraph里面是什么，所以这个接口我就不贴出了。BFS和 DFS是我的两个内部实现类，目前DFS还处于编写状态，但是怎么写，笔者还不确定。如果网友有思路可以和我交流一下。
AbsDGraph.java

/*** @author Mr.Sun* @version v.1.0* @title AdjacencyListDGraph* @description 邻接链表实现的有向图* @date 2020/3/23 9:38*/
public abstract class AbsDGraph<V> {private static Logger log = Logger.getLogger(AbsDGraph.class);/*** 构建一个顶点列表*/protected List<VRoot> vRootList ;public List<VRoot> getVRootList() {return vRootList;}public void setVRootList(List<VRoot> vRootList) {this.vRootList = vRootList;}/*** 获取根节点** @param v* @return*/public VRoot getVRoot(V v) {if (v != null) {for (VRoot vRoot : vRootList) {if (vRoot.root != null && v.equals(vRoot.root)) {return vRoot;}}}return null;}/*** 判断节点是否存在** @param v* @param vIterator* @return*/public boolean vinList(V v, Iterator<V> vIterator) {if (v != null && vIterator != null) {while (vIterator.hasNext()) {V next = vIterator.next();if (next != null && v.equals(next)) {return true;}}}return false;}/*** 删除顶点* @param v* @return*/public VRoot removeRoot(V v) {if (v != null) {for (VRoot vRoot : vRootList) {if (vRoot.root != null && v.equals(vRoot.root)){vRootList.remove(vRoot);return vRoot;}}}return null;}public void removeRootEdge(V v){if (v != null ){for (VRoot vRoot : vRootList) {vRoot.removeEdge(v);}}}
}

DGraph.java

/*** @author Mr.Sun* @version v.1.0* @title DGraph* @description* @date 2020/3/23 14:29*/
public class DGraph<V> extends AbsDGraph<V> implements DAGGraph<V> {private static Logger log = Logger.getLogger(DGraph.class);public DGraph(){List<VRoot> vRootList = new LinkedList<VRoot>();setVRootList(vRootList);}@Overridepublic int add(V v) {int index = -1;if (v != null) {VRoot vRoot = new VRoot(v);getVRootList().add(vRoot);index = getVRootList().indexOf(vRoot);}return index;}@Overridepublic void add(Edge<V> e) {if (e != null) {VRoot vRoot = getVRoot(e.getStart());if (vRoot != null) {vRoot.addEdge(e);} else {System.out.println(System.out.printf("error: can not find v: %s", e.getStart()));}}}@Overridepublic V remove(V v) {VRoot vRoot = removeRoot(v);if (vRoot != null) {removeRootEdge(v);return (V) vRoot.root;}return null;}@Overridepublic Edge<V> remove(Edge<V> e) {if (e != null) {VRoot vRoot = getVRoot(e.getStart());if (vRoot != null) {return vRoot.removeEdge(e.getEnd());}}return null;}@Overridepublic V get(int index) {if (index >= 0 || index < getVRootList().size()) {VRoot vRoot = getVRootList().get(index);if (vRoot != null) {return (V) vRoot.root;}}return null;}@Overridepublic Edge<V> get(int start, int end) {V v1 = get(start);V v2 = get(end);if (v1 != null && v2 != null) {VRoot vRoot = getVRoot(v1);if (vRoot != null) {return vRoot.getEdge(v2);}}return null;}@Overridepublic Iterator<V> iterator(int type, V root) {Iterator<V> vIterator = null;if (type == TRAVERSAL_TYPE_BFS) {vIterator = new BFS(root);}else if (type == TRAVERSAL_TYPE_DFS){vIterator = new DFS(root);}return vIterator;}@Overridepublic boolean convertDAG() {return false;}/*** 广度遍历（队列实现）*/private class BFS implements Iterator<V> {/*** 已经访问过的顶点列表*/private List<V> vList = null;/*** 待访问的顶点队列*/private Queue<V> vQueue = null;public BFS(V root) {this.vList = new LinkedList<V>();this.vQueue = new LinkedList<V>();// 初始节点进入队列vQueue.offer(root);}@Overridepublic boolean hasNext() {if (vQueue.size() > 0) {return true;}return false;}@Overridepublic V next() {V poll = vQueue.poll();if (poll != null) {VRoot vRoot = getVRoot(poll);if (vRoot != null) {List<Edge<V>> list = vRoot.getRootEdgeList();for (Edge<V> vEdge : list) {V end = vEdge.getEnd();if (!vinList(end, vList.iterator()) && !vinList(end, vQueue.iterator())) {vQueue.offer(end);}}}vList.add(poll);}return poll;}}private class DFS implements Iterator<V> {/*** 已经访问过的顶点列表*/private List<V> vList = null;/*** 待访问的顶点队列*/private Stack<V> vStack = null;public DFS(V root){this.vList = new LinkedList<V>();this.vStack = new Stack<V>();// 初始节点进入栈vStack.push(root);}@Overridepublic boolean hasNext() {if (vStack.size() > 0) {return true;}return false;}@Overridepublic V next() {return null;}}
}

这里面，我会用到一个顶点类 VRoot.java

/*** @author Mr.Sun* @version v.1.0* @title VRoot* @description* @date 2020/3/23 10:40*/
public class VRoot<V> extends AbsDGraph {private static Logger log = Logger.getLogger(VRoot.class);/*** 当前顶点*/public V root;/*** 以此点为起点的边的集合*/public List<Edge<V>> rootEdgeList;public VRoot(V root) {this.root = root;this.rootEdgeList = new LinkedList<Edge<V>>();System.out.println(System.out.printf("the VRoot construct: %s ", root));}public List<Edge<V>> getRootEdgeList() {return rootEdgeList;}@Overridepublic String toString() {return "VRoot{" +"root=" + root +", rootEdgeList=" + rootEdgeList +'}';}/*** 添加边** @param e* @return*/public void addEdge(Edge<V> e) {if (getEdge(e.getEnd()) == null) {rootEdgeList.add(e);}else {System.out.println("edge is exit .");}}/*** 获取边** @param end* @return*/public Edge<V> getEdge(V end) {Edge<V> temp = null;if (end != null) {for (Edge<V> vEdge : rootEdgeList) {if (vEdge.getEnd() != null && end.equals(vEdge.getEnd())) {temp = vEdge;break;}}}return temp;}/*** 删除边* @param end* @return*/public Edge<V> removeEdge(V end) {if (end != null) {for (Edge<V> vEdge : rootEdgeList) {if (vEdge != null && end.equals(vEdge.getEnd())) {rootEdgeList.remove(end);return vEdge;}}}return null;}
}

表是边的类： Edge.java ,这里面是对Edge做的一个简单的封装，相关方法大家看就好了。

    /*** 定义边的起点*/private V start ;/*** 定义边的终点*/private V end ;/*** 定义权值*/private double weight ;

这里我在贴一下我的测试主类:

TestGraph.java

        DGraph dGraph = new DGraph();System.out.println("添加端点");dGraph.add("1");dGraph.add("2");dGraph.add("3");dGraph.add("4");dGraph.add("5");dGraph.add("6");dGraph.add("7");dGraph.add("8");System.out.println("添加边");dGraph.add(new Edge<String>("1" , "2"));dGraph.add(new Edge<String>("1" , "3"));dGraph.add(new Edge<String>("2" , "4"));dGraph.add(new Edge<String>("2" , "5"));dGraph.add(new Edge<String>("4" , "6"));dGraph.add(new Edge<String>("5" , "7"));dGraph.add(new Edge<String>("4" , "8"));Iterator<String> iterator = dGraph.iterator(DAGGraph.TRAVERSAL_TYPE_BFS, "1");while (iterator.hasNext()){String next = iterator.next();System.out.println(next + " ");}Iterator<String> iterator1 = dGraph.iterator(DAGGraph.TRAVERSAL_TYPE_BFS, "2");while (iterator1.hasNext()){String next = iterator1.next();System.out.println(next + " ");}Edge edge = dGraph.get(0, 1);System.out.println(edge);

基本上一个广度优先遍历的图的创建到使用，我都贴出来了。其中关于深度遍历这块笔者还在纠结这个怎么去确定左右孩子（就是孩子的顺序，有可能不止两个孩子）的问题。这块笔者还没想明白。后面笔者在进行补充。

结论

笔者也是因为工作需要，才来看这个图方面的知识的。必须要承认一点，就是笔者在大学时代对于数据结构与算法没有好好的去学习，现在想起来，还是比较想骂自己的。如果看这篇文章里面有正在学习数据结构的朋友呢，还是建议好好学这门课，其实还是挺有意思的。

这篇关于【数据结构与算法】图论-你曾虐我千百遍，我却待你如初恋的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/747492。

相关文章

代码随想录算法训练营：12/60

代码随想录算法训练营：12/60

非科班学习算法day12 | LeetCode150:逆波兰表达式 ，Leetcode239: 滑动窗口最大值  目录 介绍 一、基础概念补充： 1.c++字符串转为数字 1. std::stoi, std::stol, std::stoll, std::stoul, std::stoull（最常用） 2. std::stringstream 3. std::atoi, std
阅读更多...
人工智能机器学习算法总结神经网络算法(前向及反向传播)

人工智能机器学习算法总结神经网络算法(前向及反向传播)

1.定义，意义和优缺点 定义: 神经网络算法是一种模仿人类大脑神经元之间连接方式的机器学习算法。通过多层神经元的组合和激活函数的非线性转换，神经网络能够学习数据的特征和模式，实现对复杂数据的建模和预测。(我们可以借助人类的神经元模型来更好的帮助我们理解该算法的本质，不过这里需要说明的是，虽然名字是神经网络，并且结构等等也是借鉴了神经网络，但其原型以及算法本质上还和生物层面的神经网络运行原理存在
阅读更多...
【数据结构】线性表：顺序表

【数据结构】线性表：顺序表

文章目录 1. 线性表2. 顺序表2.1 概念及结构2.2 接口实现2.3 顺序表的问题及思考 1. 线性表 线性表是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式
阅读更多...
数据结构9——排序

数据结构9——排序

一、冒泡排序 冒泡排序（Bubble Sort），顾名思义，就是指越小的元素会经由交换慢慢“浮”到数列的顶端。 算法原理 从左到右，依次比较相邻的元素大小，更大的元素交换到右边；从第一组相邻元素比较到最后一组相邻元素，这一步结束最后一个元素必然是参与比较的元素中最大的元素；按照大的居右原则，重新从左到后比较，前一轮中得到的最后一个元素不参4与比较，得出新一轮的最大元素；按照上述规则，每一轮结
阅读更多...
大林 PID 算法

大林 PID 算法

Dahlin PID算法是一种用于控制和调节系统的比例积分延迟算法。以下是一个简单的C语言实现示例： #include <stdio.h>// DALIN PID 结构体定义typedef struct {float SetPoint; // 设定点float Proportion; // 比例float Integral; // 积分float Derivative; // 微分flo
阅读更多...
LeetCode 算法：二叉树的中序遍历 c++

LeetCode 算法：二叉树的中序遍历 c++

原题链接🔗：二叉树的中序遍历 难度：简单⭐️ 题目 给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。 示例 1： 输入：root = [1,null,2,3] 输出：[1,3,2] 示例 2： 输入：root = [] 输出：[] 示例 3： 输入：root = [1] 输出：[1] 提示： 树中节点数目在范围 [0, 100] 内 -100 <= Node.
阅读更多...
【Java算法】滑动窗口 下

【Java算法】滑动窗口 下

​ ​    🔥个人主页： 中草药 🔥专栏：【算法工作坊】算法实战揭秘 🦌一.水果成篮 题目链接：904.水果成篮 ​ 算法原理 算法原理是使用“滑动窗口”（Sliding Window）策略，结合哈希表（Map）来高效地统计窗口内不同水果的种类数量。以下是详细分析： 初始化：创建一个空的哈希表 map 用来存储每种水果的数量，初始化左右指针 left
阅读更多...
ROS2从入门到精通4-4：局部控制插件开发案例(以PID算法为例)

ROS2从入门到精通4-4：局部控制插件开发案例(以PID算法为例)

目录 0 专栏介绍1 控制插件编写模板1.1 构造控制插件类1.2 注册并导出插件1.3 编译与使用插件 2 基于PID的路径跟踪原理3 控制插件开发案例(PID算法)常见问题 0 专栏介绍 本专栏旨在通过对ROS2的系统学习，掌握ROS2底层基本分布式原理，并具有机器人建模和应用ROS2进行实际项目的开发和调试的工程能力。 🚀详情：《ROS2从入门到精通》 1 控制插
阅读更多...
算法与数据结构面试宝典——回溯算法详解（C#，C++）

算法与数据结构面试宝典——回溯算法详解（C#，C++）

文章目录 1. 回溯算法的定义及应用场景2. 回溯算法的基本思想3. 递推关系式与回溯算法的建立4. 状态转移方法5. 边界条件与结束条件6. 算法的具体实现过程7. 回溯算法在C#，C++中的实际应用案例C#示例C++示例 8. 总结回溯算法的主要特点与应用价值 回溯算法是一种通过尝试各种可能的组合来找到所有解的算法。这种算法通常用于解决组合问题，如排列、组合、棋盘游
阅读更多...
【图像识别系统】昆虫识别Python+卷积神经网络算法+人工智能+深度学习+机器学习+TensorFlow+ResNet50

【图像识别系统】昆虫识别Python+卷积神经网络算法+人工智能+深度学习+机器学习+TensorFlow+ResNet50

一、介绍 昆虫识别系统，使用Python作为主要开发语言。通过TensorFlow搭建ResNet50卷积神经网络算法（CNN）模型。通过对10种常见的昆虫图片数据集（‘蜜蜂’, ‘甲虫’, ‘蝴蝶’, ‘蝉’, ‘蜻蜓’, ‘蚱蜢’, ‘蛾’, ‘蝎子’, ‘蜗牛’, ‘蜘蛛’）进行训练，得到一个识别精度较高的H5格式模型文件，然后使用Django搭建Web网页端可视化操作界面，实现用户上传一
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2