数据结构--图的基本操作

server/2025/3/17 1:20:11/

知识总览:

一、图的基本操作

  1.Adjacent(G,x,y),判断图G是否有边---对于有向图和无向图来说,邻间接矩阵的时复杂度更低。

   邻接矩阵时间复杂度  O(1)     邻接表时间复杂度  O(1)~~O(v)

  2.Neighbors(G,x):判断图G与结点x邻接的边.---邻间接矩阵的时复杂度更低。

无向图:邻接矩阵时间复杂度  O(v)     邻接表时间复杂度  O(1)~~O(v)

有向图:邻接矩阵时间复杂度  O(v)     邻接表时间复杂度出边:  O(1)~~ O(v)   入边:O(E)

  3. InsertVertex(G,x):  在图G中插入顶点x。

  邻接矩阵时间复杂度  O(1)     邻接表时间复杂度  O(1)

   在初始化邻接矩阵时,就应当将每个没有相连的顶点设置为0,因此时间复杂度为1.

   在邻接表中也是类似的

4.DeleteVertex(G,x):从图G中删除顶点x。

  对于无向图:

   在邻接矩阵中,删除一个顶点时,将其相连的所有顶点的值设置为0,再设置一个bool类型变量,用于表示该表点是否为空。  时间复杂度为O(v).

  在邻接表中,删除一个顶点,需要删除自己的所有链表外,还需遍历所有顶点的链表,将含有这个顶点的链表中删除。时间复杂度为O(1)~~~O(E)--所有顶点都与该顶点相连。

  对于有向图:

  在邻接矩阵中,与无向图一样。

  在邻接表中,只删除出边,将顶点整个边删除即可,时间复杂度为O(1)~~~O(V)

  删除入边,需要遍历整个边链表,时间复杂度为O(E)

  5.AddEdge(G,x,y):若无向边(x,y)或有向边(x,y)不存在,则在图G中添加该边。

  无向图:邻接矩阵时间复杂度为O(1).

              邻接表时间复杂度为O(1)--采用头插法

  对于有向图也是类似的

  6.FirstNeighbor(G,x):求图G中顶点x的第一个临界点,若有则返回顶点号,若x没有邻接点或图中不存在x,则返回-1.

  无向图:邻接矩阵:从左到右进行扫描 发现第一个1返回即可。时间复杂度为O(1)~~O(V)

                 邻接表:只需要找链表的第一个元素即可 时间复杂度为O(1).

 有向图:对于邻接矩阵 出边则扫描行  入边则扫面列。时间复杂度为O(1)~~O(v)

               对于邻接表,出边为O(1),  入边时间复杂度为O(1)~~O(E)

  7.NextNeighbor(G,x,y):假设图G中顶点y是顶点x的一个邻接点,返回除y之外顶点x的下一个邻接点的顶点号,若y是x的最后一个邻接点,则返回-1。

  无向图:邻接矩阵直接继续向后扫描即可,时间复杂度为:O(1)~~O(V)

                邻接表只需要再向后找一位即可,时间复杂度为:O(1)

  8.Get edge_value(G,x,y):获取图G中边(x,y)或<x,y>对应的权值。

     Set_edge_value(G,x,y,v):设置图G中边(x,y)或<x,y>对应的权值为v。

   与判断图G是否存在边类似,邻接矩阵时间复杂度  O(1)     邻接表时间复杂度  O(1)~~O(v)

  总结:


http://www.ppmy.cn/server/175571.html

相关文章

Gerrit报错:Permission denied publickey的解决办法

如何解决问题在最后 一、核心定位 Gerrit 是一款开源的代码审查与项目管理工具&#xff0c;深度集成 Git 版本控制系统&#xff0c;专为团队协作设计。最初由 Google 开发&#xff08;源于 Android 项目&#xff09;&#xff0c;现广泛应用于开源项目&#xff08;如 Linux 内核…

基于卡尔曼滤波的雷达光电多目标航迹融合算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.本算法原理 4.1卡尔曼滤波步骤 4.2 雷达光电多目标航迹融合算法原理 5.完整程序 1.程序功能描述 基于卡尔曼滤波的雷达光电多目标航迹融合算法matlab仿真。实现2个雷达&#xff0c;一个光电下的双目标…

重新认识OpenCV:C++视角下的历史演进、功能特性以及OpenCV 4.11新特性

&#xff08;基于2025年最新技术动态&#xff0c;面向工业级C开发者&#xff09; 一、OpenCV的历史迭代与技术定位 自1999年英特尔实验室诞生以来&#xff08;记住这个人-加里 布拉德斯基&#xff0c;是他怀揣着美好愿景启动了这个项目&#xff09;&#xff0c;OpenCV已成长…

UBuntu24.04-JDK7-TOMCAT7安装

jdk7 apt-get 找不到。 tomcat7 也没找到。 以下是安装成功的&#xff0c;供大家参考。 1.JAVA openjdk-7-jdk /usr/lib/jvm/java-7-openjdk-amd641.安装指定版本apt search jdk //查找版本sudo apt install default-jdk //此为默认版本sudo apt install ope…

目前人工智能的发展,判断10年、20年后的人工智能发展的主要方向,或者带动的主要产业

根据2025年的最新行业研究和技术演进趋势&#xff0c;结合历史发展轨迹&#xff0c;未来10-20年人工智能发展的主要方向及带动的产业将呈现以下六大核心趋势&#xff1a; 一、算力革命与底层架构优化 核心地位&#xff1a;算力将成为类似“新能源电池”的基础设施&#xff0c;…

Spring Boot框架总结(超级详细)

前言 本篇文章包含Springboot配置文件解释、热部署、自动装配原理源码级剖析、内嵌tomcat源码级剖析、缓存深入、多环境部署等等&#xff0c;如果能耐心看完&#xff0c;想必会有不少收获。 一、Spring Boot基础应用 Spring Boot特征 概念&#xff1a; 约定优于配置&#…

IvorySQL 4.4 发布

IvorySQL 4.4 已于 2025 年 3 月 10 日正式发布。新版本全面支持 PostgreSQL 17.4&#xff0c;新增多项新功能&#xff0c;并修复了已知问题。 增强功能 PostgreSQL 17.3 增强功能 加强 PQescapeString 及相关函数对无效编码输入字符串的防护。恢复在连接请求中出现的数据库…

【2025】Electron Git Desktop 实战一(上)(架构及首页设计开发)

源代码仓库&#xff1a; Github仓库【electron_git】 Commit &#xff1a; bb40040 Github Desktop 页面分析 本节目标&#xff1a; 1、实现类似Github Desktop的「空仓库」提示页 2、添加本地仓库逻辑编写从 Github Desktop 我们看到 他的 主要页面分为三个区域 Head头部区域…