数据结构--图(Graph)

定义

图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成的一种非线性表结构,通常表示为:G(V,E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合。

  • 顶点(vertex):图中的元素。
  • 边(edge):图中的顶点与其他任意顶点建立连接的关系。
  • 度(degree):跟顶点相连接的边的条数。
  • 入度(In-dedree):以该顶点为终点的边的条数。
  • 出度(Out-degree):以该顶点为起点的边的条数。

完全图

无向完全图

在无向图中,如果任意两个顶点之间都存在边,则称该图为无向完全图。

含有n个顶点的无向完全图有n×(n-1)/2条边

有向完全图

在有向图中,如果任意两个顶点之间都存在方向互为相反的两条弧,则称该图为有向完全图。

含有n个顶点的有向完全图有n×(n-1)条边

连通图

如果从顶点v到顶点w之间有路径,则称顶点v和w连通。

连通图一般都是指无向图。

顶点数为n的连通图,至少有n-1条边。

强连通图

在有向图中,若从顶点v到w有路径,则称这两个顶点强连通。若任意一对顶点都是强连通的,称此图为强连通图。

顶点数为n的强连通图,最少有n条边。

图的表示

邻接矩阵

图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边信息。

无向图

有向图

使用邻接矩阵的存储方式比较简单、直接,且可以高效的获取两个顶点的关系;但是由于存在n个顶点的图需要n*n个数组元素进行存储,当图为稀疏图时,使用邻接矩阵存储方法将会出现大量0元素,这会造成极大的空间浪费。这时,可以考虑使用邻接表表示法来存储图中的数据。

邻接表

图的顶点对应一条链表,链表中存储的是与这个顶点相连接的其他顶点。

邻接表存储起来比较节省空间,但是使用起来就比较耗时间。

当链表过长,为了提高查找效率,我们可以将链表换成其他更加高效的数据结构,如平衡二叉树(红黑树)、跳表、散列表等。

图的深度优先遍历

图的深度优先遍历,类似于树的先序遍历,主要思想是首先选择一个未被访问过的顶点作为起始顶点,沿当前顶点的边走到未访问过的顶点。当没有未访问过的顶点时,则回到上一个顶点,继续试探别的顶点,直至所有的顶点都被访问过。

以无向图为例,深度优先搜索的算法步骤。

  1. 选择起始节点 u,并将其标记为已访问。
  2. 遍历当前节点 u 的所有未访问邻接节点。
  3. 对每个未访问的邻接节点 v,从节点 v 出发继续进行深度优先搜索(递归)。
  4. 如果节点 u 没有未访问的相邻节点,回溯到上一个节点,继续搜索其他路径。
  5. 重复 2∼4 步骤,直到遍历完整个图或找到目标节点为止。

//递归实现
void DfsRecursive(int v)
{cout<<v<<" ";//将v标记为已读visited[v] = true;for (int i = 0; i < vertexNum; i++){//选择一个没有被标记过的节点if ((arc[v][i] != 0 && arc[v][i] != inf) && visited[i] == 0){DfsRecursive(i);}}}
//非递归
void DFS(int v) {stack<int> st;st.push(v); // 将起始顶点压入栈中visited[v]=true // 标记起始顶点为已访问while (!st.empty()) {v = stack.top();stack.pop();cout << v << " "; // 访问顶点v// 遍历顶点v的所有邻接点for (int i = 0; i < vertexNum; i++){//选择一个没有被标记过的节点if ((arc[v][i] != 0 && arc[v][i] != inf) && visited[i] == false){st.push(i);}    }}
}

 深度优先搜索的时间复杂度为 O(E),E 表示边的个数;空间复杂度为 O(V),V 表示顶点的个数。

图的广度优先遍历

广度优先遍历从某个顶点 v 出发,首先访问这个结点,并将其标记为已访问,然后顺序访问v的所有未被访问的邻接点 {vi,..,vj} ,并将其标记为已访问,然后将 {vi,...,vj} 中的每一个节点重复节点v的访问方法,直到所有结点都被访问完为止。

步骤:

  1. 将起始节点u 放入队列中,并标记为已访问。
  2. 从队列中取出一个节点,访问它并将其所有的未访问邻接节点 v 放入队列中。
  3. 标记已访问的节点 v,以避免重复访问。
  4. 重复步骤 2∼3,直到队列为空或找到目标节点。
    void BFS(int v)
    {queue<int> q;q.push(v);visited[v] = true;while (!q.empty()){v = q.front();q.pop();cout<<v<<" ";for (int i = 0; i < vertexNum; i++){if ((arc[v][i] !=0&&arc[v][i]!=inf) && visited[i] == false){q.push(i);visited[i] = true;}}}}

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

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

相关文章

阿里云智能大数据演进

本文根据7月24日飞天发布时刻产品发布会、7月5日DataFunCon2024北京站&#xff1a;大数据大模型.双核时代实录整理而成&#xff0c;演讲信息如下&#xff1a; 演讲人&#xff1a;徐晟 阿里云研究员/计算平台产品负责人 主要内容&#xff1a; Overview - 阿里云大数据 AI 产品…

经典算法题总结:数组常用技巧(双指针,二分查找和位运算)篇

双指针 在处理数组和链表相关问题时&#xff0c;双指针技巧是经常用到的&#xff0c;双指针技巧主要分为两类&#xff1a;左右指针和快慢指针。所谓左右指针&#xff0c;就是两个指针相向而行或者相背而行&#xff1b;而所谓快慢指针&#xff0c;就是两个指针同向而行&#xf…

【YOLO5 项目实战】(3)PCB 缺陷检测

欢迎关注『youcans动手学模型』系列 本专栏内容和资源同步到 GitHub/youcans 【YOLO5 项目实战】(1)YOLO5 环境配置与测试 【YOLO5 项目实战】(2)使用自己的数据集训练目标检测模型 【YOLO5 项目实战】(3)PCB 缺陷检测 【YOLO5 项目实战】(3)PCB 缺陷检测 1. PCB 缺陷检…

vue-cli 中 配置 productionSourceMap 为 false 失效?

背景 最近 发现 vuecli 构建的 项目中配置的 productionSourceMap 为 false 后 &#xff0c;生产代码 还是能够看到 sourceMap 文件 。 原因 生效前提条件 得设置 NODE_ENV 为 production 才会生效&#xff01; 解决 直接修改生产环境的配置 NODE_ENV 为 production 直接覆…

融资3亿美元——月之暗面:AI大模型领域的新星

月之暗面&#xff0c;这个名字在AI领域引起了不小的震动。作为国内大模型创业企业的佼佼者&#xff0c;月之暗面以其独特的技术优势和商业模式&#xff0c;迅速在激烈的市场竞争中崭露头角。同时以其出色的长文本处理能力和创新的商业模式吸引了众多投资者的目光。 优牛企讯-企…

基于DETR模型实现交通标志检测

交通标志检测在自动驾驶和交通监控中是一个重要的问题。目标检测技术极大地促进了这一过程的自动化。本文实现基于DETR目标检测模型识别交通标志。 Tiny LISA交通标志检测数据集 本文数据集使用Kaggle上提供的Tiny LISA交通标志检测数据集(https://www.kaggle.com/datasets/mm…

手把手教你CNVD漏洞挖掘 + 资产收集

0x1 前言 挖掘CNVD漏洞有时候其实比一般的edusrc还好挖&#xff0c;但是一般要挖证书的话&#xff0c;还是需要花时间的&#xff0c;其中信息收集&#xff0c;公司资产确定等操作需要花费一定时间的。下面就记录下我之前跟一个师傅学习的一个垂直越权成功的CNVD漏洞通杀&#…

MySql 5.7.1 分区的实践

在性能优化中&#xff0c;Mysql 进行分区&#xff0c;能有效提高查询效率&#xff0c;因此开始百度了起来。但是结果总不是那么一番风顺的。如今使用 uuid 作为主键的情况已是主流&#xff0c;因此在给表增加分区时&#xff0c;出现了如下错误&#xff1a; 错误&#xff1a; A …

AI在医学领域:联邦学习 (FL) 在肿瘤学的应用综述

关键词&#xff1a;联邦学习 (Federated Learning, FL)、机器学习 (Machine Learning, ML)、肿瘤学 (Oncology)、数据隐私 (Data Privacy)、精准医疗 (Precision Medicine)、多模态 (Multi-modal) 肿瘤学正在经历快速的变革&#xff0c;这得益于机器学习&#xff08;ML&#xf…

奥德彪视频素材去哪里找?视频素材网站分享

今天我们来聊一聊一个非常实用的话题——视频素材网站推荐&#xff0c;尤其是奥德彪视频素材。这个名词可能对你来说有些陌生&#xff0c;但别担心&#xff0c;跟着我一起探索&#xff0c;你会发现这是一个充满创意与乐趣的旅程。 蛙学网 首先要介绍的是蛙学网。这是一个视频素…

【传知代码】医疗AI:轻量级图像分割新突破(论文复现)

在医学图像领域&#xff0c;精准的图像分割技术一直是提高诊断效率和准确性的关键&#xff0c;然而传统的图像分割方法常常受到计算资源和处理速度的限制&#xff0c;尤其在资源紧张的医疗环境中更是如此。随着人工智能技术的飞速发展&#xff0c;我们迎来了一个激动人心的新时…

PAT--1101.B是A的多少倍

题目描述 算法分析 把数字转为字符串处理&#xff0c;会简化问题 完整代码 #include<bits/stdc.h> //万能头文件 //#include<iostream> //#include<string> //#include <iomanip> // 包含 std::fixed 和 std::setprecision using namespace std;…

PHP汽车保养维修信息管理系统小程序源码

&#x1f697;爱车守护神器&#xff01;揭秘“汽车保养维修信息管理系统”全攻略&#x1f50d; &#x1f525;【开篇揭秘&#xff1a;为何你需要它&#xff1f;】&#x1f525; 在这个快节奏的时代&#xff0c;爱车不仅是代步工具&#xff0c;更是生活品质的象征。但你是否曾…

JUC-变量的线程安全

成员变量和静态变量是否线程安全&#xff1f; 如果它们没有共享&#xff0c;则线程安全&#xff0c;即没有被外部访问。 如果它们被共享了&#xff0c;根据它们的状态是否能够改变&#xff0c;又分两种情况 如果只有读操作&#xff0c;则线程安全 如果有读写操作&#xff0c;…

精彩回顾 | 风丘科技亮相2024名古屋汽车工程博览会

2024年7月17日-19日&#xff0c;风丘科技联合德国IPETRONIK亮相日本名古屋汽车工程博览会。该展会面向汽车行业不同应用场景&#xff0c;包括新的eAxle、FCEV、ADAS、测试测量系统和ECU测试等相关技术&#xff0c;是一个专为活跃在汽车行业前线的工程师和研究人员举办的汽车技术…

Leetcode JAVA刷刷站(11)盛最多水的容器

一、题目概述 二、思路方向 这个问题是经典的“盛最多水的容器”问题&#xff0c;通常使用双指针法来解决。基本思路是&#xff0c;我们初始化两个指针&#xff0c;一个指向数组的起始位置&#xff0c;另一个指向数组的末尾位置。然后&#xff0c;我们计算当前两个指针所指向…

学习笔记第二十四天

1.exec族函数的区别 int exec l(const char *path, const char *arg, ...); int exec l p(const char *file, const char *arg, ...); int exec l e(const char *path, const char *arg,..., char * const envp[]); int exec v(const char *path, char *const argv[]); …

硬件面试经典 100 题(31~40 题)

31、多级放大电路的级间耦合方式有哪几种&#xff1f;哪种耦合方式的电路零点偏移最严重&#xff1f;哪种耦合方式可以实现阻抗变换&#xff1f; 有三种耦合方式&#xff1a;直接耦合、阻容耦合、变压器耦合。直接耦合的电路零点漂移最严重&#xff0c;变压器耦合的电路可以实现…

广告资料库是什么?如何正确使用Facebook广告资料库?一文解决你的烦恼!

什么是广告资料库 广告营销领域&#xff0c;创意和策略的更新速度极快。为了跟上这种节奏&#xff0c;广告资料库应运而生&#xff0c;成为广告人和营销专家的重要工具。广告资料库是一个集中存储和管理广告素材、创意案例、市场数据和用户反馈的平台。它不仅帮助用户获得灵感…

掌握高可用核心:Keepalived 铸就坚不可摧的集群防线

目录 一.初识keepalived 二.VRRP工作模式 1.三种状态 2.选举机制 三.Keepalived 架构 四. Keepalived环境准备 五.KeepAlived 配置说明 1.配置文件组成部分 2.配置语法说明&#xff1a;全局配置 3.配置虚拟路由器 4.启用keepalived日志功能 5.实现独立子配置文件 六…