当前位置: 首页 > news >正文

图的存储:邻接矩阵法

1.邻接矩阵的实现

邻接矩阵的定义:在无向图和有向图中,使用二维数组表示各个顶点的相邻情况:1代表相邻,0表示不相邻。
代码实现:

#define MaxVertexNum 100//顶点数目的最大值
typedef struct {char Vex [MaxVertexNum];//顶点表int Edge [MaxVertexNum] [MaxVertexNum] ;//邻接矩阵,边表int vexnum, arcnum;//图的当前顶点数和边数/弧数
}MGraph;;

注意:

  • 顶点中可以存更复杂的信息
  • 边可以用bool型或枚举型变量

2.求顶点的度,入度,出度

1.无向图

  • 第i个结点的度=第i行(或第i列)的非零元素个数。(时间复杂度为O(N))

2.有向图

  • 第i个结点的出度=第i行的非零元素个数。
  • 第i个结点的入度=第i列的非零元素个数。
  • 第i个结点的度=第i行、第i列的非零元素个数之和。

3.邻接矩阵法存储带权图(网)

分为有向网和无向网。
同样使用二维矩阵存储,无穷代表没有路径可达,反之值代表路径的长度。
代码实现:

#define MaxVertexNum 100//顶点数目的最大值
#define INFINITY  1000000//最大的int值  宏定义常量"无穷"
typedef char VertexType; //顶点的数据类型
typedef int EdgeType; // 带权图中边上权值的数据类型
typedef struct {VertexType Vex [MaxVertexNum];//顶点EdgeType Edge[MaxVertexNum][MaxVertexNum]; //边的权int vexnum, arcnum;//图的当前顶点数和弧数
}MGraph;;

4.临接矩阵的性能分析

1.空间复杂度

O(n2):只和顶点数相关,和实际的边数无关。

  • 适合用于存储稠密图
  • 无向图的邻接矩阵是对称矩阵,可以压缩存储(只存储上三角区/下三角区)

5.邻接矩阵法的性质

设图G的邻接矩阵为A(矩阵元素为0/1),
则A"的元素A[i][]等于由顶点i到顶点j的长度为n的路径的数目。

相关文章:

图的存储:邻接矩阵法

1.邻接矩阵的实现 邻接矩阵的定义:在无向图和有向图中,使用二维数组表示各个顶点的相邻情况:1代表相邻,0表示不相邻。 代码实现: #define MaxVertexNum 100//顶点数目的最大值 typedef struct {char Vex [MaxVertexN…...

如何优雅的使用Git?

第一部分:Git的基本概念和初始设置 Git是一个分布式版本控制系统,它允许多人共同工作,同时跟踪和管理项目的版本历史。使用Git,您可以恢复旧版本、创建新分支进行实验,并与其他开发者进行协作,而不会影响主…...

【【STM32分析IO该设置什么模式的问题】】

STM32分析IO该设置什么模式的问题 我们分析而言 我们对于PA0 的设计就从此而来 对于边沿触发的选择我们已经有所了解了 我们下拉,但是当我们摁下开关的时候 从0到1 导通了 所以这个是下拉 上升沿触发 而对于KEY0 我们摁下是使得电路从原来悬空高阻态到地就是0 所以…...

飞天使-k8s基础组件分析-服务与ingress

文章目录 服务的介绍服务代理服务发现连接集群外服务服务发布无头服务 服务,pod和dns的关系端口转发通过expose 暴露应用服务案例INGRESSMetalLB使用参考文档 服务的介绍 服务的作用是啥? 提供外部调用,保证podip的真实性看看服务解决了什么…...

Unity——拖尾特效

拖尾是一种很酷的特效。拖尾的原理来自人类的视觉残留:观察快速移动的明亮物体,会看到物体移动的轨迹。摄像机通过调整快门时间,也可以拍出具有拖尾效果的照片,如在城市的夜景中,汽车的尾灯拖曳出红色的线条。 在较老…...

java开发之fastjson

依赖 <!-- fastjson依赖 --> <!-- https://mvnrepository.com/artifact/com.alibaba/fastjson --> <dependency> <groupId>com.alibaba</groupId> <artifactId>fastjson</artifactId> <version>1.2.76</version> <…...

第一个C语言程序:HelloWorld

第一个C语言程序 注释 注释 对代码的解释和说明 特点 ○ 不会被执行 目的 让人们能够更加轻松地看懂代码 分类 行注释 // 快键键 ctrl/ 块注释 /**/ 快捷键 shiftalta 示例代码&#xff1a; #include <stdio.h>int main() {// 行注释/*块注释*/printf("hello w…...

golang 使用 viper 加载配置文件 自动反序列化到结构

文章博客地址:golang 使用 viper 加载配置 自动反序列化到结构 golang使用 viper 无需设置 mapstructure tag 根据配置文件后缀 自动返序列化到结构解决结构有下划线的字段解析不成功问题 viper 正常加载配置文件 golang viper 其中可以用来 查找、加载和反序列化JSON、TOML…...

C#设计模式六大原则之--接口隔离原则

设计模式六大原则是单一职责原则、里氏替换原则、依赖倒置原则、接口隔离原则、迪米特法则、开闭原则。它们不是要我们刻板的遵守&#xff0c;而是根据实际需要灵活运用。只要对它们的遵守程度在一个合理的范围内&#xff0c;努为做到一个良好的设计。本文主要介绍一下.NET(C#)…...

【面试题】:axios二次封装都进行了哪些配置以及如果项目里面有两个baseURL你怎么解决?

一.axios的概念 Axios 是一个基于 promise 网络请求库&#xff0c;作用于node.js 和浏览器中。 它是 isomorphic 的(即同一套代码可以运行在浏览器和node.js中)。在服务端它使用原生 node.js http 模块, 而在客户端 (浏览端) 则使用 XMLHttpRequests。 二.axios的特点&#xf…...

谈谈对 GMP 的简单认识

犹记得最开始学习 golang 的时候&#xff0c;大佬们分享 GMP 模型的时候&#xff0c;总感觉云里雾里&#xff0c;听了半天&#xff0c;并没有一个很清晰的概念&#xff0c;不知 xmd 是否会有这样的体会 虽然 golang 入门很简单&#xff0c;但是对于理解 golang 的设计思想和原…...

Java正则表达式系列--从字符串中提取字符串或数字

原文网址&#xff1a;Java正则表达式系列--从字符串中提取字符串或数字_IT利刃出鞘的博客-CSDN博客 简介 本文用示例介绍Java如何使用正则表达式从字符串中提取想要的内容&#xff08;字符串或者数字等&#xff09;。 例1&#xff1a;提取一次不同内容 需求 从字符串中找到…...

机器学习实战之模型的解释性:Scikit-Learn的SHAP和LIME库

概要 机器学习模型的“黑箱”困境 机器学习模型的崛起让我们惊叹不已&#xff01;不论是预测房价、识别图片中的猫狗&#xff0c;还是推荐给你喜欢的音乐&#xff0c;这些模型都表现得非常出色。但是&#xff0c;有没有想过&#xff0c;这些模型到底是如何做出这些决策的呢&a…...

Go 语言进阶与依赖管理 | 青训营

Powered by:NEFU AB-IN 文章目录 Go 语言进阶与依赖管理 | 青训营 语言进阶依赖管理测试 Go 语言进阶与依赖管理 | 青训营 GO语言工程实践课后作业&#xff1a;实现思路、代码以及路径记录 语言进阶 Go可以充分发挥多核优势&#xff0c;高效运行 Goroutine是Go语言中的协程…...

hyperf 十三 视图

教程&#xff1a;Hyperf composer地址&#xff1a;hyperf/view - Packagist 本次测试使用twig twig composedr地址&#xff1a;twig/twig - Packagist twig 文档地址&#xff1a;Home - Twig - The flexible, fast, and secure PHP template engine 一、安装 composer re…...

请你说说前端图形图像的框架

前端图形图像方面有许多强大的框架和库&#xff0c;使得开发者能够更容易地创建丰富的视觉效果和复杂的图形应用。下面列举了一些主要的框架和库&#xff1a; 1. Three.js Three.js 是一款运行在浏览器中的 3D 引擎&#xff0c;你可以用它创建各种三维场景&#xff0c;包括了…...

C++数据结构学习——栈

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、栈二、C语言实现1.声明代码2.实现增删查改代码3.测试代码 总结 前言 栈&#xff08;Stack&#xff09;是计算机科学中一种常见的数据结构&#xff0c;它是…...

【C++笔记】C++之类与对象(下)

【C笔记】C之类与对象(下&#xff09; 1、再看构造函数1.1、构造函数的初始化列表1.2、C支持单参数的构造函数的隐式类型转换1.3、匿名对象 2、Static成员2.1、为什么要有静态成员变量&#xff1f;2.2、一个类的静态成员变量属于这个类的所有对象2.3、静态成员函数 3、友元3.1、…...

管理类联考——英语——实战篇——大作文——图表——动态图表——整体效果

动态图表模板 What is clearly presented in the above 图表类型 is that dramatic changes have taken place in 主题词1 from 年份1 to 年份2.During the period, there was a marked jump from 数字1 to 数字2 in 事物1,while that of 事物2 declined significantly from 数…...

threejs纹理加载三(视频加载)

threejs中除了能把图片作为纹理进行几何体贴图以外&#xff0c;还可以把视频作为纹理进行贴图设置。纹理的类型有很多&#xff0c;我们可以用不同的加载器来加载&#xff0c;而对于视频作为纹理&#xff0c;我们需要用到今天的主角&#xff1a;VideoTexture。我们先看效果&…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...