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

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。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
秋招最新大模型算法面试，熬夜都要肝完它

秋招最新大模型算法面试，熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候，不知道面试完会不会复盘、总结，做笔记的习惯，这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助，都附有完整答案，熬夜也要看完，祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN，还有完整版的大模型 AI 学习资料，朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
dp算法练习题【8】

dp算法练习题【8】

不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。 示例 1： 输入：n = 3输出：5 示例 2： 输入：n = 1输出：1 class Solution {public int numTrees(int n) {int[] dp = new int
阅读更多...
Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数，每次操作将其分成2^q份，对于每一份内部的数进行翻转(逆序)，每次操作完后输出操作后新序列的逆序对数。 图一：  划分子问题。 图二： 分而治之，=>  合并 。 图三： 回溯：
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2