【图论】图论基础

图论不同地方讲的不太一样,本文仅限作者的理解

定义

图一般由点集 V V V 和边集 E E E 组成。
对于 v ∈ V v\in V vV,称 v v v 为该图的一个节点。
对于 e ∈ E e\in E eE,一般用二元组 ( u , v ) (u,v) (u,v) 表示 e e e,其中 u , v ∈ V u,v\in V u,vV。在无向图中,该二元组无序,即边为双向;在有向图中,该二元组有序,即边为单向。
一个带有边权(边的长度)的图称为带权图,此时边一般记为 ( u , v , w ) (u,v,w) (u,v,w)
下面分别是一个无向图和一个有向图的例子:
一个无向图
一个有向图

连通性

从一个图中选出一些节点和边,构成一个合法的新图,称做原图的子图。
扩展至最大的符合某一要求的子图被称为分量。
通过图中的边可以使节点之间联通(单向联通也算)的图称做连通图。
节点之间两两可以互相到达的有向图被称做强联通图。
如果一个图中某一个点及其边被删去后,图将不再联通,则称该点为原图的一个割点。
没有割点的图被称为点双连通图。
如果一个图中某一条边被删去后,图将不再联通,则称该边为原图的一个割边。
没有割边的图被称为边双连通图。
读者可以自行理解联通子图、联通分量、强连通子图、强连通分量、点双联通子图、点双联通分量、边双联通子图、边双联通分量等概念。

树与环

一个没有环的图称为无环图。
一个没有环的有向图称为有向无环图(DAG)。
一个没有环且联通的无向图称为树。
一个有恰一个环且联通的无向图称为基环树。
一个是树且包含所有节点的子图称为原图的生成树。

存储

一般有两种存储方式,邻接矩阵和邻接表。

邻接矩阵

使用一个矩阵来存储图,对于矩阵中的一个元素 G u , v G_{u,v} Gu,v
在无权图中, u , v u,v u,v 之间有边为 1 1 1,无边为 0 0 0
在带权图中, u , v u,v u,v 之间有边为 w w w,无边为 inf ⁡ \inf inf

邻接表

使用多个数组来存储图,对于每一个数组 G u G_u Gu
在无权图中, u , v u,v u,v 间有边则加入 v v v
在带权图中, u , v u,v u,v 间有边则加入有序二元组 ( v , w ) (v,w) (v,w)

代码

分为定义,输入和遍历三部分

  • 邻接矩阵
int G[N][N];
memset(G,0,sizeof(G));//无权
memset(G,INF,sizeof(G));//带权
for (int i=1;i<=m;i++){//无权int u,v;cin>>u>>v;G[u][v]=1;G[v][u]=1;//仅限无向图//带权int u,v,w;cin>>u>>v>>w;G[u][v]=w;G[v][u]=w;//仅限无向图
}
for (int u=1;u<=n;u++) for (int v=1;v<=n;v++)if (G[u][v])//无权if (G{u][v]!=INF)//带权
  • 邻接表
vector<int> G[N];//无权
//带权
struct edge{int v,w;};
vector<edge> G[N];
for (int i=1;i<=m;i++){//无权int u,v;cin>>u>>v;G[u].push_back(v);G[v].push_back(u);//仅限无向图//带权int u,v,w;cin>>u>>v>>w;G[u].push_back({v,w});G[v].push_back({u,w});//仅限无向图
}
for (int u=1;u<=n;u++)for (int v:G[u])//无权for (edge e:G[u])//带权

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

VS2022 .Net6.0 无法打开窗体设计器

拿Vs2022 建了个Demo&#xff0c;运行环境是net6.0-windows&#xff0c;无论双击或是右键都打不开窗体设计器 打开项目目录下的*.csproj.user <?xml version"1.0" encoding"utf-8"?> <Project ToolsVersion"Current" xmlns"htt…

2024年第二十一届 五一杯 (B题)大学生数学建模挑战赛 | 最大流问题,深度学习分析 | 数学建模完整代码解析

DeepVisionary 每日深度学习前沿科技推送&顶会论文&数学建模与科技信息前沿资讯分享&#xff0c;与你一起了解前沿科技知识&#xff01; 本次DeepVisionary带来的是五一杯的详细解读&#xff1a; 完整内容可以在文章末尾全文免费领取&阅读&#xff01; 第一个问题…

[高质量]2024五一数学建模A题保奖思路+代码(后续会更新)

你的点赞收藏是我继续更新的最大动力&#xff0c;可点击文末卡片获取更多资料 你是否在寻找数学建模比赛的突破点&#xff1f; 作为经验丰富的数学建模团队&#xff0c;我们将为你带来2024 年华东杯&#xff08;A题&#xff09;的全面解析包。这个解决方案包不仅包括完整的代…

实习面试算法准备之图论

这里写目录标题 1 基础内容1.1 图的表示1.2图的遍历 2 例题2.1 所有可能的路径2.2 课程表&#xff08;环检测算法&#xff09;2.2.1 环检测算法 DFS版2.2.2 环检测算法 BFS版 2.3 课程表 II &#xff08;拓扑排序算法&#xff09;2.3.1 拓扑排序 DFS版 1 基础内容 图没啥高深的…

百度安全多篇议题入选Blackhat Asia以硬技术发现“芯”问题

Blackhat Asia 2024于4月中旬在新加坡隆重举行。此次大会聚集了业界最杰出的信息安全专业人士和研究者&#xff0c;为参会人员提供了安全领域最新的研究成果和发展趋势。在本次大会上&#xff0c;百度安全共有三篇技术议题被大会收录&#xff0c;主要围绕自动驾驶控制器安全、跨…

IDEA实现Springboot项目自动热部署

每当我们在修改代码时&#xff0c;往往需要重新启动项目&#xff0c;这样不仅浪费时间而且很麻烦&#xff0c;我们可以通过IDEA的热部署来提高效率 1、首先点file >> settings >> Build Excution >> Compire&#xff0c;选择Build project auto matically 2.…

有关CSS中排版常见问题(清除默认样式问题 + 元素居中问题 + 元素之间的空白问题 + 行内块的幽灵空白问题)

前言&#xff1a;在练习CSS排版的时候&#xff0c;我们经常会遇到一些排版上的问题&#xff0c;那么我们如何去解决这些问题呢&#xff1f;本篇文章给出了一些新手在练习排版时候可能会遇到的问题的解决方案。 ✨✨✨这里是秋刀鱼不做梦的BLOG ✨✨✨想要了解更多内容可以访问我…

【竞技宝jjb.lol】LOL:MSI首日赛事前瞻

北京时间2024年5月1日,英雄联盟2024MSI季中赛将在今天正式开打,今天将进行两场入围赛的比赛,分别为FLY对阵PSG以及T1对阵EST。入围赛的战队实力差距较大,但如今各大赛区的实力越来越小,即使是外卡赛区的队伍也有爆冷的可能,下面小编就为大家带来MSI首日赛事前瞻。 FLY VS PSG …

做外贸如何主动开发外贸客户

在外贸业务中&#xff0c;主动开发客户是至关重要的一步&#xff0c;它能够帮助你扩大市场覆盖范围&#xff0c;建立稳定的客户基础。以下是一些有效的策略和方法&#xff0c;可以帮助你更有效地主动开发外贸客户&#xff1a; 明确目标市场&#xff1a;首先&#xff0c;你需要确…

一键PDF水印添加工具

一键PDF水印添加工具 引言优点1. 精准定位与灵活布局2. 自由旋转与透明度调控3. 精细化页码选择4. 全方位自定义水印内容5. 无缝整合工作流程 功能详解结语工具示意图【工具链接】 引言 PDF作为最常用的文档格式之一&#xff0c;其安全性和版权保护显得尤为重要。今天&#xff…

启明云端2.4寸屏+ESP32-S3+小型智能调速电动家用除草机案例 触控三档调速,能显示电压故障码

今天给大家分享个启明云端2.4寸屏ESP32-S3小型智能调速电动家用除草机案例&#xff0c;国外有草坪文化&#xff0c;这个机器能智能触控三档调速&#xff0c;带屏能显示电压故障码&#xff0c;数显档位&#xff08;3档最大&#xff09;&#xff0c;触控屏&#xff0c;长按3秒就能…

K-近邻算法的 sklearn 实现

实验目的与要求 掌握基于 K-近邻分类算法的编程方法通过编程理解 K-近邻分类算法和该算法的基本步骤 实验器材 硬件&#xff1a;PC 机&#xff08;参与实验的学生每人一台&#xff09;软件环境&#xff1a;Python3.7 Pycharm 实验内容 使用 sklearn 库中的 neighbors 模块实…

基于python的舞蹈经验分享交流网站django+vue

1.运行环境&#xff1a;python3.7/python3.8。 2.IDE环境&#xff1a;pycharmmysql5.7/8.0; 3.数据库工具&#xff1a;Navicat11 4.硬件环境&#xff1a;windows11/10 8G内存以上 5.数据库&#xff1a;MySql 5.7/8.0版本&#xff1b; 运行成功后&#xff0c;在浏览器中输入&am…

计算机网络——应用层协议(1)

在这篇文章初识网络中&#xff0c;我介绍了关于计算机网络的相关知识&#xff0c;以及在这两篇文章中Socket编程和Socket编程——tcp&#xff0c;介绍了使用套接字在两种协议下的网络间通信方式。本篇文章中我将会进一步介绍网络中网络协议的部分&#xff0c;而这将会从应用层开…

Vue 组件单元测试深度探索:细致解析与实战范例大全

Vue.js作为一款广受欢迎的前端框架&#xff0c;以其声明式的数据绑定、组件化开发和灵活的生态系统赢得了广大开发者的心。然而&#xff0c;随着项目规模的增长&#xff0c;确保组件的稳定性和可靠性变得愈发关键。单元测试作为软件质量的守护神&#xff0c;为Vue组件的开发过程…

FPGA高端项目:FPGA帧差算法多目标图像识别+目标跟踪,提供11套工程源码和技术支持

目录 1、前言免责声明 2、相关方案推荐FPGA帧差算法单个目标图像识别目标跟踪 3、详细设计方案设计原理框图运动目标检测原理OV5640摄像头配置与采集OV7725摄像头配置与采集RGB视频流转AXI4-StreamVDMA图像缓存多目标帧差算法图像识别目标跟踪模块视频输出Xilinx系列FPGA工程源…

PDF高效编辑器,支持修改PDF文档并转换格式从PDF文件转换成图片文件,轻松管理你的文档世界!

PDF文件已成为我们工作、学习和生活中不可或缺的一部分。然而&#xff0c;传统的PDF阅读器往往只能满足简单的查看需求&#xff0c;对于需要频繁编辑、修改或转换格式的用户来说&#xff0c;就显得力不从心。现在&#xff0c;我们为您带来一款全新的PDF高效编辑器&#xff0c;让…

绿色便携方式安装apache+mysql+tomcat+php集成环境并提供控制面板

绿色便携方式安装带控制面板的ApacheMariaDBTomcatPHP集成环境 目录 绿色便携方式安装带控制面板的ApacheMariaDBTomcatPHP集成环境[TOC](目录) 前言一、XAMPP二、安装和使用1.安装2.使用 三、可能的错误1、检查端口占用2、修改端口3、JDK原因导致 前言 安装集成环境往往配置复…

paddlehub的简单应用

1、下载安装 pip install paddlehub -i https://pypi.tuna.tsinghua.edu.cn/simple 报错&#xff1a; Collecting onnx<1.9.0 (from paddle2onnx>0.5.1->paddlehub)Using cached https://pypi.tuna.tsinghua.edu.cn/packages/73/e9/5b953497c0e36df589fc60cc6c6b35…

[1688]jsp工资投放管理系统Myeclipse开发mysql数据库web结构java编程计算机网页项目

一、源码特点 JSP 工资投放管理系统是一套完善的java web信息管理系统&#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。开发环境为 TOMCAT7.0,Myeclipse8.5开发&#xff0c;数据库为Mysql5.0…