【十字链表,邻接多重表(无向图的另一种链式存储结构),图的遍历】

文章目录

  • 十字链表
  • 邻接多重表(无向图的另一种链式存储结构)
  • 图的遍历

在这里插入图片描述

十字链表

方便找到入度和出度边。
在这里插入图片描述
顶点结点:
data:顶点存放的数据域。
firstin:第一个入度边。
firstout:第一个出度边。
弧度结点:
tailvex:尾结点。
headvex:头结点。
在这里插入图片描述
建立十字链表的步骤:
①先找结点的出度,例如a的出度有b,c。所以a的最后一个firstout指针域指向出度结点,因为结点是从下标为0到1,2所以表示为如图。
②找到结点的出度:例如a结点的入度就是d,c。所以就是从下标为2到0,3到0.表示如图。
③按照以上两个步骤进行查看剩下的顶点结点。最后形成的图就是十字链表。

邻接多重表(无向图的另一种链式存储结构)

在这里插入图片描述
在这里插入图片描述

图的遍历

从已知连通图中的某一顶点出发,沿着一些边访遍图中的所有顶点,使每一个顶点仅被访问一次,叫做图的遍历,它是图的基本运算。
遍历实质:找每一顶点的邻接点的过程。
图的特点:
图中可能存在回路,且图的任一顶点都可能与其它顶点想通,在访问完某个顶点之后可能会沿着某些边又回到曾经访问过的顶点。
怎样避免重复访问?
解决思路:
设置辅助数组visited[n],用来标记被访问过的顶点。

  • 初始状态visited[i]为0;
  • 顶点i被访问,改visited[i]为1,防止被多次访问。

图常用的遍历:

  • 深度优先搜索(Depth_First Search----DFS)
  • 广度优先搜索(Width_First Search----WFS)
    在这里插入图片描述

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

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

相关文章

Django 入门学习总结6 - 测试

1、介绍自动化测试 测试的主要工作是检查代码的运行情况。测试有全覆盖和部分覆盖。 自动测试表示测试工作由系统自动完成。 在大型系统中,有许多组件有很复杂的交互。一个小的变化可能会带来意想不到的后果 测试能发现问题,并以此解决问题。 测试驱…

ANSYS网格无关性检查

网格精度对应力结果存在很大的影响,有时候可以发现,随着网格精度逐渐提高,所求得的最大应力值逐渐趋于收敛。 默认网格: 从默认网格下计算出的应力云图可以发现,出现了的三处应力奇异点,此时算出的应力值是…

手把手从零开始训练YOLOv8改进项目(官方ultralytics版本)教程

手把手从零开始训练 YOLOv8 改进项目 (Ultralytics版本) 教程,改进 YOLOv8 算法 本文以Windows服务器为例:从零开始使用Windows训练 YOLOv8 算法项目 《芒果 YOLOv8 目标检测算法 改进》 适用于芒果专栏改进 YOLOv8 算法 文章目录 官方 YOLOv8 算法介绍改进网络代码汇总第…

【C++上层应用】2. 预处理器

文章目录 【 1. #define 预处理 】【 2. #ifdef、#if 条件编译 】2.1 #ifdef2.2 #if2.3 实例 【 3. # 和 ## 预处理 】3.1 # 替换预处理3.2 ## 连接预处理 【 4. 预定义宏 】 预处理器是一些指令,指示编译器在实际编译之前所需完成的预处理。 所有的预处理器指令都是…

【Java 进阶篇】Ajax 实现——JQuery 实现方式 `ajax()`

嗨,亲爱的读者们!欢迎来到这篇关于使用 jQuery 中的 ajax() 方法进行 Ajax 请求的博客。在前端开发中,jQuery 提供了简便而强大的工具,其中 ajax() 方法为我们处理异步请求提供了便捷的解决方案。无需手动创建 XMLHttpRequest 对象…

接口测试知识点问答

一.什么是接口? 接口测试主要用于外部系统与系统之间以及内部各个子系统之间的交互点,定义特定的交互点,然后通过这些交互点来,通过一些特殊的规则也就是协议,来进行数据之间的交互。 二.接口都有哪些类型&#xff1f…

四旋翼无人机的飞行原理--【其利天下分享】

近年来,无人机在多领域的便捷应用促使其迅猛的发展,如近年来的多场战争,无人机的战场运用发挥得淋漓尽致。 下面我们针对生活中常见的四旋翼无人机的飞行原理做个基础的介绍,以飨各位对无人机有兴趣的朋友。 一:四旋翼…

场景交互与场景漫游-对象选取(8-2)

对象选取示例的代码如程序清单8-11所示: /******************************************* 对象选取示例 *************************************/ // 对象选取事件处理器 class PickHandler :public osgGA::GUIEventHandler { public:PickHandler() :_mx(0.0f), _my…

flink源码分析之功能组件(一)-metrics

简介 本系列是flink源码分析的第二个系列,上一个《flink源码分析之集群与资源》分析集群与资源,本系列分析功能组件,kubeclient,rpc,心跳,高可用,slotpool,rest,metric,future。其中kubeclient上一个系列介绍过,本系列不在介绍。 本文介绍flink metrics组件,metric…

【赠书第6期】MATLAB科学计算从入门到精通

文章目录 前言 1 安装与配置 2 变量定义 3 数据处理 4 绘图 5 算法设计 6 程序调试 7 推荐图书 8 粉丝福利 前言 MATLAB 是一种高级的科学计算和数据可视化平台。它由 MathWorks 公司开发,是科学研究、数据分析和工程实践中非常常用的一种软件工具。本文将…

UDP网络套接字编程

先来说说数据在网络上的传输过程吧,我们知道系统其实终究是根据冯诺依曼来构成的,而网络数据是怎么发的呢? 其实很简单,网络有五层。如下: 如上图,我们知道的是,每层对应的操作系统中的那些地方…

Spring Cloud Stream实践

概述 不同中间件,有各自的使用方法,代码也不一样。 可以使用Spring Cloud Stream解耦,切换中间件时,不需要修改代码。实现方式为使用绑定层,绑定层对生产者和消费者提供统一的编码方式,需要连接不同的中间…

拼图游游戏代码

一.创建新项目 二.插入图片 三.游戏的主界面 1.代码 package com.itheima.ui;import java.awt.event.ActionEvent; import java.awt.event.ActionListener; import java.awt.event.KeyEvent; import java.awt.event.KeyListener; import java.util.Random;import javax.swing…

贪吃蛇代码

一.准备 1.新建项目 2.放进照片 3.创建两个包放置图片类和入口类 二,游戏界面 package com.snake.view;import java.awt.Color; import java.awt.EventQueue; import java.awt.Font; import java.awt.Frame; import java.awt.Graphics; import java.awt.Image; i…

【Java程序员面试专栏 算法训练篇】二叉树高频面试算法题

一轮的算法训练完成后,对相关的题目有了一个初步理解了,接下来进行专题训练,以下这些题目就是二叉树相关汇总的高频题目 遍历二叉树 遍历二叉树,分为递归和迭代两种方式,递归类似于DFS,迭代类似于BFS,【算法训练-二叉树 一】【遍历二叉树】前序遍历、中序遍历、后续遍…

【高级程序设计】Week2-4Week3-1 JavaScript

一、Javascript 1. What is JS 定义A scripting language used for client-side web development.作用 an implementation of the ECMAScript standard defines the syntax/characteristics of the language and a basic set of commonly used objects such as Number, Date …

【Java 进阶篇】Ajax 实现——原生JS方式

大家好,欢迎来到这篇关于原生 JavaScript 中使用 Ajax 实现的博客!在前端开发中,我们经常需要与服务器进行数据交互,而 Ajax(Asynchronous JavaScript and XML)是一种用于创建异步请求的技术,它…

多态语法详解

多态语法详解 一:概念1:多态实现条件 二:重写:三:向上转型和向下转型1:向上转型:1:直接赋值:2:方法传参3:返回值 2:向下转型 一:概念 1:同一个引…

Java值传递和引用传递

在Java中,有值传递(Pass-by-Value)和引用传递(Pass-by-Reference)两种参数传递方式。 值传递(Pass-by-Value):当使用值传递方式时,方法将参数的副本传递给调用方法。这意…