二、图的表示和带权图

文章目录

  • 1、图的表示
    • 1.1 邻接矩阵
    • 1.2 邻接表
    • 1.3 关联矩阵
  • 2、带权图
    • 2.1 最短路径问题
    • 2.2 中国邮递员问题
    • 2.3 旅行商问题
  • THE END

1、图的表示

1.1 邻接矩阵

\qquad 将图的所有顶点分别构成一个二维矩阵的行列,将顶点之间的边关系表示在构成的矩阵之中,则称这个二维矩阵为图的邻接矩阵。无向图和有向图的邻接矩阵如下图所示。
在这里插入图片描述
在这里插入图片描述

1.2 邻接表

\qquad 上述使用图的邻接矩阵表示图的时候,当图时一个稀疏图时(图中的边数量较少),在图的存储时会浪费大量的存储空间,所以需要将图进行压缩存储。一种简单的方式就是利用图的邻接表来存储图。邻接表中表的头结点表示图中每一个顶点,邻接表中的每一个节点中有值域和指针域,值域存储图中节点的编号,指针域存储一个指针,指向和当前结点相邻接的其他结点。无向图和有向图的邻接表的形式如下图所示。
在这里插入图片描述
在这里插入图片描述

1.3 关联矩阵

\qquad 将图的所有顶点和所有的边分别构成一个二维矩阵的行列,将顶点之间和边之间的关系表示在构成的矩阵之中,则称这个二维矩阵为图的关联矩阵。无向图和有向图的关联矩阵如下图所示。
在这里插入图片描述
在这里插入图片描述

2、带权图

\qquad 给定一个图 G = ( V , E , f , g ) G=(V,E,f,g) G=(V,E,f,g),其中 f : V → R f:V\rightarrow R f:VR表示每一个顶点到实数的映射, g : E → R g:E\rightarrow R g:ER表示每一条边到实数的映射,则称 G G G为一个带权图。

2.1 最短路径问题

\qquad 最短路径问题是图论研究中的一个经典算法问题,旨在寻找图(由结点和路径组成的)中
两结点之间的最短路径。算法具体的形式包括:

  • 确定起点的最短路径问题。也叫单源最短路问题,即已知起始结点,求最短路径的问题。在边权非负时适合使用Dijkstra算法,若边权为负时则适合使用Bellman-ford算法或者SPFA算法
  • 确定终点的最短路径问题。与确定起点的问题相反,该问题是已知终结结点,求最短路径的问题。在无向图中该问题与确定起点的问题完全等同,在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
  • 确定起点终点的最短路径问题 - 即已知起点和终点,求两结点之间的最短路径。
  • 全局最短路径问题也叫多源最短路问题,求图中所有的最短路径。适合使用Floyd-Warshall算法

2.2 中国邮递员问题

\qquad 在一个连通的无向图中找到一最短的封闭路径,且此路径需通过所有边至少一次。现实意义中,中国邮递员问题就是在一个已知的地区,邮差要设法找到一条最短路径,走过此地区所有的街道,且最后要回到出发点。
\qquad 此问题是图遍历问题的一种。无向图的中国邮递员问题是容易解决的,是P问题;而有向图的中国邮递员问题是NP完全问题。中国邮递员问题由管梅谷教授在1960年提出。

2.3 旅行商问题

\qquad 是组合优化中的一个NP困难问题,在运筹学和理论计算机科学中非常重要。问题内容为“给定一系列城市和每对城市之间的距离,求解访问每座城市一次并回到起始城市的最短回路。
\qquad 可以用无向加权图来对TSP建模,则城市是图的顶点,道路是图的边,道路的距离就是该边的长度。它是起点和终点都在一个特定顶点,访问每个顶点恰好一次的最小化问题。通常,该模型是一个完全图(即每对顶点由一条边连接)。如果两个城市之间不存在路径,则增加一条非常长的边就可以完成图,而不影响计算最优回路。

THE END

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/506920.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

在CentOS 8.5.2111下安装vncserver

# 参考: 如何在 CentOS 8/RHEL 8 上安装配置 VNC 服务器 安装CentOS 8.5.2111 及 vncserver # 标准安装步骤 安装GNOME桌面环境使用屏幕号:1。安装VNC服务器(tigervnc-server tigervnc)设置VNC密码设置VNC服务器配置文件开启vnc服务。开放防…

FX110网:货币交易5个亏损典型,你有中招吗?

人生百年几今日,今日不为真可惜!若言姑待明朝至,明朝又有明朝事。很多投资朋友总是抱怨,为什么总是看见别人赚钱,自己一进场就亏损,那么在这里投资失败无非两点:一是自身原因,自己没…

SAP 销售分销中的免费货物

销售业务中,免费货物在您与客户协商价格时起着重要作用。在零售、化工或消费品这样的行业部门中,通常以免费货物的形式向客户提供折扣。 作为用户,业务用户希望能自动确定免费货物并将它们归入销售凭证中。同时需要向成本控制部门提供免费货物…

密码算法概论

基本概念 什么是密码学? 简单来说,密码学就是研究编制密码和破译密码的技术科学 例题: 密码学的三个阶段 古代到1949年:具有艺术性的科学1949到1975年:IBM制定了加密标准DES1976至今:1976年开创了公钥密…

盘点那些好用的SAP FIORI App(一) Display Customer/Supplier List

做SAP运维的人可能都知道,SAP标准的菜单里面基本没有好用的report可以用来批量显示并导出客户清单,或者供应商清单。T-code MKVZ 可以导出供应商的采购数据,但仅限于部分字段,客户清单的话系统标准的有这个S_ALR_87012179 - Custo…

电脑端手机配置检测工具推荐与使用指南

摘要 本文介绍了如何使用克魔助手工具在电脑上检测手机的配置信息。通过该工具,用户可以全面了解手机的硬件和操作系统信息,包括电池、CPU、内存、基带信息和销售信息等。 引言 在日常工作中,了解手机的配置信息对于开发和测试人员非常重要…

算法刷题笔记(3.25-3.29)

算法刷题笔记 3.25-3.29 1. 相同的树2. 二叉树的最近公共祖先3. 二叉搜索树中第K小的元素通过双端队列duque 中序遍历 4. 二叉树的锯齿形层序遍历new LinkedList<Integer>(levelList)双端队列复制 数组需要左右顺序&#xff0c;考虑双端队列 5. 岛屿数量6. 字典序排数&am…

【应用浅谈】Odoo的库存计价与产品成本(一)

序言:时间是我们最宝贵的财富,珍惜手上的每个时分 Odoo的库存&#xff08;Stock&#xff09;模块拥有众多功能&#xff0c;其中库存计价是一项非常重要的功能&#xff0c;原生的成本方法分三种&#xff1a;【标准成本】&#xff0c;【平均成本】&#xff0c;【先进先出】&#…

个人博客系统|基于Springboot的个人博客系统设计与实现(源码+数据库+文档)

个人博客系统目录 目录 基于Springboot的个人博客系统设计与实现 一、前言 二、系统功能设计 三、系统实现 1、管理员功能实现 &#xff08;1&#xff09;用户管理 &#xff08;2&#xff09;文章分类管理 &#xff08;3&#xff09;公告信息管理 &#xff08;4&#…

微服务之分布式事务概念

微服务之分布式事务概念 CAP定理和Base理论 CAP定理 CAP定理在1998年被加州大学的计算机科学家 Eric Brewer 提出&#xff0c;分布式系统有三个指标&#xff1a; 一致性&#xff08;Consistency&#xff09;可用性&#xff08;Availability&#xff09;分区容错性&#xff…

Taro 关于微信订阅消息的调用

requestSubscribeMessage 是微信提供的方法 封装的调用requestSubscribeMessage的方法 示例图如下 import {getWechatTemplates,postSubscribeNotice } from /magic-sdk/apis/wechat-service; import {WechatTemplateType,SubscribeNoticeObjTypeOptions,WechatTemplateEvent…

详细分析Mysql中的STR_TO_DATE基本知识(全)

目录 前言1. 基本知识2. Demo3. 实战Demo4. Sql彩蛋4.1 LPAD函数4.2 SUBSTRING_INDEX函数 5. Java彩蛋 前言 对于该知识点&#xff0c;主要因为数据库类型为String&#xff08;类似2024-03-26&#xff09;&#xff0c;放置于后端操作后&#xff0c;需要自定义比较&#xff0c;…

做了盲/埋孔,PCB还有必要做盘中孔吗?

在PCB设计中&#xff0c;过孔类型可分为盲孔、埋孔和盘中孔&#xff0c;它们各自有不同应用场景和优势&#xff0c;盲孔和埋孔主要用于实现多层板之间的电气连接&#xff0c;而盘中孔是元器件的固定及焊接。如果PCB板上做了盲孔和埋孔&#xff0c;那么有必要做盘中孔吗&#xf…

java的Class文件分析

文章目录 1. 简介2. Class文件分析 1. 简介 Java有一个著名的口号一次编译&#xff0c;处处运行&#xff0c;这就凸显出来Java程序的一个特点平台无关性。Java的平台无关性是基于各种不同平台的Java虚拟机&#xff0c;以及所有平台都统一支持的程序存储格式—字节码实现的。在…

B端管理系统:UI设计师为什么没有话语权?

一、六大因素&#xff0c;导致了UI设计师话语权缺失。 专业性差异&#xff1a; UI设计师主要负责界面设计和用户体验&#xff0c;而在B端管理系统中&#xff0c;功能性和操作流程往往更为重要&#xff0c;需要产品经理和开发人员更多的参与&#xff0c;他们对于系统的功能和技…

Springboot Thymeleaf 实现数据添加、修改、查询、删除

1、引言 在Spring Boot中使用Thymeleaf模板引擎实现数据的添加、修改、查询和删除功能&#xff0c;通常步骤如下&#xff1a; 在Controller类中&#xff0c;定义处理HTTP请求的方法。创建Thymeleaf模板来处理表单的显示和数据的绑定。 2、用户数据添加 1、 在Controller类中…

尚医通day1

1 创建项目 doc 窗口 pnpm create vite 填写项目名 vue-syt选择框架 vuetypeScript 2整理项目 删除 /src/assets/vue.svg 文件&#xff0c;删除 /src/components 下的 helloWorld.vue删除app.vue内容&#xff0c;快捷键v3ts 生成模板内容去掉 /src/style.css 样式文件&…

格雷希尔G10系列L150A和L200A气动快速连接器,在新能源汽车线束线缆剥线后的气密性测试密封方案

线束线缆在很多用电环境都有使用&#xff0c;比如说新能源汽车&#xff0c;从电池包放电开始&#xff0c;高低压、通讯都开始进行工作&#xff0c;线束在连接的地方需要具有较高的气密性和稳定性&#xff0c;才能保证车辆在不同环境下能够正常的运行。 线束在组装铜鼻子前需要剥…

【Linux】开始掌握进程控制吧!

送给大家一句话&#xff1a; 我并不期待人生可以一直过得很顺利&#xff0c;但我希望碰到人生难关的时候&#xff0c;自己可以是它的对手。—— 加缪 开始学习进程控制 1 前言2 进程创建2.1 fork函数初识2.2 fork函数返回值2.3 写时拷贝2.4 fork常规用法2.5 fork调用失败的原因…

高阶DS---AVL树详解(每步配图)

目录 前言&#xff1a; AVL树的概念: AVL树节点的定义&#xff1a; AVL树的插入&#xff08;重点&#xff09; AVL树的旋转&#xff1a; &#xff08;1&#xff09;新节点插入较高左子树的左侧---右单旋 &#xff08;2&#xff09;新节点插入较高右子树的右侧---左单旋 …