数据结构之邻接多重表

2024-08-27 01:20
文章标签 数据结构 多重 邻接

本文主要是介绍数据结构之邻接多重表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、特点

存储效率高:对于无向图,邻接多重表能够避免邻接表中同一条边需要存储两次的问题,因为每条边在邻接多重表中只被表示一次。
灵活性高:由于每条边同时链接在两个链表中(分别对应其两个顶点),因此在进行边的增删查改等操作时更加方便。
可读性强:邻接多重表的结构清晰,能够直观地表示无向图中顶点与边之间的关系。

二、结构

邻接多重表由顶点表和边表组成:

顶点表:存储图中的顶点信息,每个顶点元素包含两个域:data域用于存放与顶点相关的信息;firstedge域(或类似指针)指向依附于该顶点的第一条边在边表中的节点。
边表:存储图中边的信息,每个边表节点包含多个域,以下是常见的几个域:
mark:标志域,用于标记该边是否被访问过或进行过其他特定操作。
ivex和jvex:分别存放该边两个顶点在顶点表中的位置(即下标)。
info:信息域,对于带权图,可以存放边的权值;对于无向图,此域可省略。
ilink和jlink:分别指向下一条依附于顶点ivex和jvex的边在边表中的节点。

三、构建方法

构建邻接多重表通常遵循以下步骤:

1、初始化:
创建一个空的邻接多重表,包括顶点表和边表。

2、填充顶点表
根据无向图的顶点数,在顶点表中创建相应数量的顶点元素,并初始化firstedge域为NULL。

3、添加边:
遍历无向图中的每一条边,为每条边创建一个边表节点,并设置其ivex、jvex(以及可能的info)域。然后,将该节点分别插入到顶点ivex和jvex的边链表中,即更新相应顶点的firstedge域以及边表节点的ilink和jlink域。

四、应用场景

邻接多重表特别适用于需要频繁操作边的无向图问题,如边的删除、查找、标记等。在这些场景中,邻接多重表能够提供比邻接表更高效的操作性能,因为它避免了同一条边在邻接表中需要存储两次的问题。

此外,邻接多重表还广泛应用于图论及其相关领域的算法中,如图的遍历、最短路径计算、拓扑排序等。这些算法在利用邻接多重表作为图的存储结构时,能够更加方便地实现算法逻辑,提高算法的执行效率。

这篇关于数据结构之邻接多重表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1110234

相关文章

hdu1171(母函数或多重背包)

题意:把物品分成两份,使得价值最接近 可以用背包,或者是母函数来解,母函数(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v) 其中指数为价值,每一项的数目为(该物品数+1)个 代码如下: #include<iostream>#include<algorithm>

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

多重背包转换成0-1背包

http://acm.hdu.edu.cn/showproblem.php?pid=2191 多重背包特点: 一种物品有C个(既不是固定的1个,也不是无数个) 优化的方法: 运用神奇的二进制,进行物品拆分,转化成01背包 物品拆分,把13个相同的物品分成4组(1,2,4,6) 用这4组可以组成任意一个1~13之间的数! 原理:一个数总可以用2^

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

【408数据结构】散列 (哈希)知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独,于是我记下了些许笔记相伴,希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法,它通过散列函数将关键字映射到数组的一个位置,从而实现快速查找。这种方法的时间复杂度平均为(

浙大数据结构:树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre

Python 内置的一些数据结构

文章目录 1. 列表 (List)2. 元组 (Tuple)3. 字典 (Dictionary)4. 集合 (Set)5. 字符串 (String) Python 提供了几种内置的数据结构来存储和操作数据,每种都有其独特的特点和用途。下面是一些常用的数据结构及其简要说明: 1. 列表 (List) 列表是一种可变的有序集合,可以存放任意类型的数据。列表中的元素可以通过索

浙大数据结构:04-树7 二叉搜索树的操作集

这道题答案都在PPT上,所以先学会再写的话并不难。 1、BinTree Insert( BinTree BST, ElementType X ) 递归实现,小就进左子树,大就进右子树。 为空就新建结点插入。 BinTree Insert( BinTree BST, ElementType X ){if(!BST){BST=(BinTree)malloc(sizeof(struct TNo

【数据结构入门】排序算法之交换排序与归并排序

前言         在前一篇博客,我们学习了排序算法中的插入排序和选择排序,接下来我们将继续探索交换排序与归并排序,这两个排序都是重头戏,让我们接着往下看。  一、交换排序 1.1 冒泡排序 冒泡排序是一种简单的排序算法。 1.1.1 基本思想 它的基本思想是通过相邻元素的比较和交换,让较大的元素逐渐向右移动,从而将最大的元素移动到最右边。 动画演示: 1.1.2 具体步