算法通关第二十关-青铜挑战认识图结构

2023-12-25 07:04

本文主要是介绍算法通关第二十关-青铜挑战认识图结构,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

大家好我是苏麟 , 今天来聊聊图结构 .

我们平时在工作、学习中会大量使用图结构,不过呢在使用代码进行具体实现的时候极少使用图,主要是图里容易产生环,难以处理。
在算法里,考察图也不是很多,主要是图的表示非常复杂,初始化一个图就需要几十行代码,非常不利于面试。不过呢,在笔试、校招等场景还是可能考察图,所以为了提高自己的胜算,我们有必要掌握必要的图问题。

前面我们学了线性表和树,线性表局限于一个直接前驱和一个直接后继的关系,树也只能有一个直接前驱也就是父节点,当我们需要表示多对多的关系时,就用到了图。

图,是一种比树更为复杂的数据结构。树的节点之间是一对多的 关系,并且存在父与子的层级划分;而图的顶点(注意,这里不叫节点)之间是多对多的关系,并且所有顶点都是平等的,无所谓谁是父 谁是子。

在生活中,图这种数据结构的应用比比皆是。在交通当中,也常常涉及图的应用。

假设某个城市的地铁线路如下:

这些许许多多地铁站所组成的交通网络,也可被认为是数据结构当中的图。

图的定义与术语总结

  1. 图按照有无方向分为无向图和有向图。无向图自顶点和边构成,有向图由顶点和弧何成。弧有弧尾和弧头之分。
  2. 图按照边或弧的多少分稀疏图和稠密图。如果任意两个顶点之间都存在边叫完全图,有向的叫有向完全图。若无重复的边或顶点到自身的边则叫简单图。
  3. 图中顶点之间有邻接点、依附的概念。无向图顶点的边数叫做度,有向图顶点分为入度和出度。
  4. 图上的边或弧上带权则称为网。
  5. 图中顶点间存在路径,两顶点存在路径则说明是连通的,如果路径最终回到起始点则称为环,当中不重复叫简单路径。若任意两顶点都是连通的,则图就是连通图,有向则称强连通图。图中有子图,若子图极大连通则就是连通分量,有向的则称强连通分量。
  6. 无向图中连通旦n个顶点n-l条边叫生成树。有向图中一顶点入度为。其余顶点入度为1的叫有向树。一个有向固自若干棵有向树构成生成森林。

图的基本概念

为了方便处理,我们会将图抽象为只有顶点(vertex)和边的结构(edge),如下图所示

根据边是否有向,可以将图分为有向图和无向图。而根据顶点之间的边是否有权重,又分为带权图和不带权的图。

而不同顶点之间能够连通的线路就称为路径(Path),例如在上述中间有向图中C到D的路径为”C->B>D“,但是从D到C则没有路径,这称为两个结点不可达。

图结构常用来存储逻辑关系为“多对多”的数据。比如说,一个学生可以同时选择多门课程,而一门课程可以同时被多名学生选择,学生和课程之间的逻辑关系就是“多对多”。再举个例子, {V1,V2,V3,V4} 中各个元素之间具有的逻辑关系如下图所示 :

上图中,从V1可以找到V3、V4、V2,从 V3、V4、V2也可以找到 V1,因此元素之间具有“多对多”的逻辑关系,存储它们就需要用到图结构。

和链表不同,图中存储的各个元素被称为顶点(而不是节点)。拿上图来说,图中含有4个顶点,分别为顶点V1、V2、V3 和 V4。

通常情况下,我们习惯用 Vi 表示图中的顶点,且所有顶点构成的集合通常用 V 表示。比如说,上图中顶点的集合为 V={V1,V2,V3,V4}。

上图中各个顶点之间的关系都是双向的,这种情况下我们更习惯用下图来表示各个元素之间的关系 :

由 V1 可以找到 V2,同样由 V2 也可以找到 V1。类似上图这样,各个元素之间的联系都是双向的,这样的图结构称为无向图。如果元素之间存在单向的联系,那么这样的图结构称为有向图,例如:

从上面几个图,我们可以得到两个重要的结论 :

  • 图中各个顶点的地位是一样的,各个边的地位也是一样的。我们知道树是有根节点的,其他结点都要严格的满足树的要求,而图中各个顶点的等价的,你可以将任何一个视为起始点,任何一个视为终点
  • 对于无向图,如果一个图有n个顶点,那么最少需要n-1条边,最多有n(n-1)/2条边。例如,n=5时最少和最多的边如下:

弧头和弧尾
有向图中,无箭头一端的顶点通常被称为"初始点"或"孤尾",箭头一端的顶点被称为"终端点"或"孤头"

入度和出度
对于有向图中的一个顶点 V 来说,箭头指向 V 的的数量为 V 的入度 (InDegree,记为 ID(V));箭头远离 V 的孤的数量为 V 的出度 (OutDegree,记为OD(V)) 。拿图中的顶点 V1来说,该顶点的入度为1,出度为 2,该顶点的度为 3.

(V1,V2) 和 <V1,V2> 的区别
无向图中描述两顶点 V1和 V2 之间的关系可以用(V1,V2) 来表示

有向图中描述从 V1 到 V2 的"单向"关系可以用 <V1,V2>来表示。


 

由于图存储结构中顶点之间的关系是用线来表示的,因此(V1,V2)还可以用来表示无向图中连接 V1 和 V2的线,又称为边:同样,<V1.V2> 也可用来表示有向图中从 V1 到 V2 带方向的线,又称为弧

集合VR
图中习惯用 VR 表示图中所有顶点之间关系的集合。

例如,图中无向图的集合 VR={(v1,v2),(v1,v4),(v1,v3),(v3,v4)}

图中有向图的集合 VR={<v1,v2>,<v1,v3>,<v3.v4>,<v4.v1>}.

路径和回路
无论是无向图还是有向图,从一个顶点到另一顶点途经的所有顶点组成的序列(包含这两个顶点),称为条路径。如果路径中第一个顶点和最后一个顶点相同,则此路径称为"回路”(或"环")。
在此基础上,若路径中各顶点都不重复,此路径被称为"简单路径",若回路中的顶点互不重复,此回路被称为"简单回路”(或简单环)。


拿图来说,从 V1 存在一条路径还可以回到 V1,此路径为{V1,V3,V4,V1},这是一个回路(环),而目还是一个简单回路 (简单环) .
在有向图中,每条路径或回路都是有方向的 .

权和网
有些场景中,可能会为图中的每条边赋予一个实数表示一定的含义,这种与边(或弧)相匹配的实数被称为"权",而带权的图通常称为网。例如:

子图
指的是由图中一部分顶点和边构成的图,称为原图的子图

连通图
前面讲过,图中从一个顶点到达另一顶点,若存在至少一条路径,则称这两个顶点是连通着的。例如图中,虽然V1 和 V3 没有直接关联,但从 V1 到 V3 存在两条路径,分别是 V1-V2-V3 和 V1-V4-V3,因此称 V1 和 V3 之间是连通的。

无向图中,如果任意两个顶点之间都能够连通,则称此无向图为连通图。例如,图中的无向图就是一个连通图,因为此图中任意两顶点之间都是连通的。

强连通图
有向图中,若任意两个顶点 Vi 和 Vj,满足从 V到 V 以及从 V到 Vi 都连通,也就是都含有至少一条通路,则称此有向图为强连通图。如图所示就是一个强连通图。

与此同时,若有向图本身不是强连通图,但其包含的最大连通子图具有强连通图的性质,则称该子图为强连通分量。

强连通分量如上图所示,整个有向图虽不是强连通图,但其含有两个强连通分量。

这期就到这里 , 下期见!

这篇关于算法通关第二十关-青铜挑战认识图结构的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/534626

相关文章

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

Java中switch-case结构的使用方法举例详解

《Java中switch-case结构的使用方法举例详解》:本文主要介绍Java中switch-case结构使用的相关资料,switch-case结构是Java中处理多个分支条件的一种有效方式,它... 目录前言一、switch-case结构的基本语法二、使用示例三、注意事项四、总结前言对于Java初学者

结构体和联合体的区别及说明

《结构体和联合体的区别及说明》文章主要介绍了C语言中的结构体和联合体,结构体是一种自定义的复合数据类型,可以包含多个成员,每个成员可以是不同的数据类型,联合体是一种特殊的数据结构,可以在内存中共享同一... 目录结构体和联合体的区别1. 结构体(Struct)2. 联合体(Union)3. 联合体与结构体的

PostgreSQL如何查询表结构和索引信息

《PostgreSQL如何查询表结构和索引信息》文章介绍了在PostgreSQL中查询表结构和索引信息的几种方法,包括使用`d`元命令、系统数据字典查询以及使用可视化工具DBeaver... 目录前言使用\d元命令查看表字段信息和索引信息通过系统数据字典查询表结构通过系统数据字典查询索引信息查询所有的表名可

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物

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

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

每天认识几个maven依赖(ActiveMQ+activemq-jaxb+activesoap+activespace+adarwin)

八、ActiveMQ 1、是什么? ActiveMQ 是一个开源的消息中间件(Message Broker),由 Apache 软件基金会开发和维护。它实现了 Java 消息服务(Java Message Service, JMS)规范,并支持多种消息传递协议,包括 AMQP、MQTT 和 OpenWire 等。 2、有什么用? 可靠性:ActiveMQ 提供了消息持久性和事务支持,确保消

跨国公司撤出在华研发中心的启示:中国IT产业的挑战与机遇

近日,IBM中国宣布撤出在华的两大研发中心,这一决定在IT行业引发了广泛的讨论和关注。跨国公司在华研发中心的撤出,不仅对众多IT从业者的职业发展带来了直接的冲击,也引发了人们对全球化背景下中国IT产业竞争力和未来发展方向的深思。面对这一突如其来的变化,我们应如何看待跨国公司的决策?中国IT人才又该如何应对?中国IT产业将何去何从?本文将围绕这些问题展开探讨。 跨国公司撤出的背景与

康拓展开(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]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。