(数据结构)图的邻接表存储结构_本关任务:用邻接表存储有向图,在顶点表中增加入度域,使用队列存储入度为零的顶点-程序员宅基地

技术标签: 邻接表存储  链表  数据结构与C  数据结构    

图的邻接表存储结构

一般来说,图更多的是采用链表存储,具体的存储方法有 3 种,分别是邻接表、邻接多重表和十字链表


本篇文章将优先介绍邻接表!!!

邻接点:在图中,如果两个点相互连通,且通过其中一个顶点,可直接找到另一个顶点,则称它们互为邻接点

邻接:指图中顶点之间有边或者弧的存在

邻接表存储图的实现方式:给图中的各个顶点独自建立一个链表,用节点存储该顶点,用另一个链表中的节点存储其邻接点

特殊之处是,为了便于管理这些链表,通常会将链表的头节点存储到数组中,也正因为各个链表的头节点存储的是各个顶点,因此各链表在存储邻接点数据时,仅需存储该邻接点位于数组中的位置下标

图 1 邻接表存储有向图

        如上图 1 中,给图的各个顶点创建了一个链表(用于存储数据域和头指针域),然后创建一个数组用来保存各个顶点;之后给邻接点又创建一个链表(用于存储邻接点在数组中的位置下标和指向下一个邻接点的指针)

        对顶点 V1,与其相关的邻接点分别为 V2 和 V3,因此存储 V1 邻接点的链表中存储的是 V2 和 V3 在数组中的位置下标 1 和 2

        图 1 中的链接表结构用结构体声明如下:

#define  MAX_NUM 20  // 最大顶点个数

typedef enum{
	DG, DN, UDG, UDN  // 依次代表的值为 0,1,2,3
} GraphKind;  // 枚举图的 4 种类型

typedef struct ArcNode{
    int adjvex;  // 邻接点在数组中的位置下标
    struct ArcNode *nextarc;  // 指向下一个邻接点的指针
    int *info;  // 信息域
} ArcNode;

typedef struct VNode{
    int data;  // 顶点的数据域
    ArcNode *firstarc;  // 指向邻接点的指针
} VNode, AdjList[MAX_NUM];  // 存储各链表头结点的数组

typedef struct{
    AdjList vertices;  // 图中顶点的数组
    int vexnum, arcnum;  // 记录图中顶点数和边或弧数
    GraphKind kind;  // 记录图的种类
} ALGraph;

邻接表计算顶点的出度和入度

无向图:使用邻接表计算无向图中顶点的入度和出度只需从数组中找到该顶点然后统计此链表中节点的数量即可


有向图:使用邻接表存储有向图时,通常各个顶点的链表中存储的都是以该顶点为弧尾的邻接点,因此通过统计各顶点链表中的节点数量,只能计算出该顶点的出度

对于(有向图)利用邻接表求某顶点的入度,有两种方式:

  1. 遍历整个邻接表中的节点,统计数据域与该顶点所在数组位置下标相同的节点数量,即为该顶点的入度
  2. 建立一个逆邻接表,该表中的各顶点链表专门用于存储以此顶点为弧头的所有顶点在数组中的位置下标

图 4 逆邻接表示意图

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_51927215/article/details/123933547

智能推荐

用两个栈实现一个队列,完成push和pop函数_实验四栈和队列将push和pop函数补充完整-程序员宅基地

文章浏览阅读1.9k次。思路:(1)栈为后入先出,队列为先入先出;(2)进入队列的操作用栈1来完成,然后用栈2来完成出栈操作,把栈1的数据弹出后放入栈2,那么栈1中最后入栈的现在进入栈2的栈底最后出栈,正好实现队列的后入后出,最开始入栈1的数在栈2 的栈顶,最先出队列,相当于在队列的尾部class Solution{public: void push(int node) { stack1.pu..._实验四栈和队列将push和pop函数补充完整

Linux之编译make常识_make -j12-程序员宅基地

文章浏览阅读2.3k次,点赞2次,收藏5次。1,make -j:通过在make后加-j可以加快编译速度。在使用make进行编译时,若只执行make指令则效率较低,若用make -j后面跟一个数值,比如make -j8,make -j12等则可以提高编译效率。make -j命令后面跟着线程数,12表示这个命令使用12线路去执行编译。假设我们的系统是cpu是12核,在不影响其他工作的情况下,我们可以用make -j12(注意make -j线程数不能超过电脑cpu的线程数)。cpu_num=`cat /proc/stat | grep cpu[_make -j12

单独谈谈 Android Cursor 的使用细节-程序员宅基地

文章浏览阅读1.1k次。使用过 SQLite 数据库对 Cursor 应该不陌生,这里单独拿出来谈一下,加深对Android SQLite中使用 Cursor 的理解。在你理解和使用 Android Cursor 的时候你必须先知道关于Cursor的几件事情:Cursor 是每行的集合。使用 moveToFirst() 定位第一行。你必须知道每一列的名称。你必须知道每一列的数据类型。Cur..._cursor.movetoposition(i);为啥每次访问都是第一个数据

如何用CodeBlocks分多个文件编写一个C++程序_cold blocks中建立empty和file的区别-程序员宅基地

文章浏览阅读3.4w次,点赞41次,收藏142次。网上有许多教程,说的是如何用codeblocks编写一个简单的C\C++程序,但没有说如果分多个文件编写程序效果会怎样?下面向大家介绍该如何做:1.首先打开codeblocks:2.单击“File"-"new"-“Projects",或者单击“Create a new project",如下:打开如下对话框:然后单击图中圈出的两项目中的任意一个。再单击“go":_cold blocks中建立empty和file的区别

YAML语言的介绍和语法规则_yaml语言中,字符串 浮点数-程序员宅基地

文章浏览阅读250次。内容转载自我的博客文章目录1. YAML语言概述2. YAML语言的对象3. YAML语言的数组4. YAML语言的复合结构5. YAML语言的纯量6. YAML语言的字符串7. YAML语言的引用1. YAML语言概述YAML 语言的基本语法规则如下大小写敏感使用缩进表示层级关系缩进时不允许使用Tab键,只允许使用空格。缩进的空格数目不重要,只要相同层级的元素左侧对齐即可# 表示注释,从这个字符一直到行尾,都会被解析器忽略YAML 支持的数据结构有三种对象:键值对的集合,又称._yaml语言中,字符串 浮点数

Gralloc 总结-程序员宅基地

文章浏览阅读3.8k次。从字面就可以看出来Gralloc接口是为了显示内存分配与释放 – Graphics Allocation。它的主要目的有三个:Ø 为应用分配显示用内存;Ø 可以把显示内存在不同进程间进行映射;Ø 同步通过加载gralloc抽象层(gralloc.xxx.so),可以打开fb设备(/dev/fb0)和gpu设备(/dev/graphic/),fb设备用于操作fram_gralloc

随便推点

【web课程设计网页规划与设计】基于HTML+CSS+JavaScript制作大学网站(11页)_基于+javascript&mysgl&html的学校官网-程序员宅基地

文章浏览阅读447次。 校园网页设计 、学校班级网页制作、学校官网、小说书籍、等网站的设计与制作。️HTML静态网页设计作业使用dreamweaver制作,采用DIV+CSS布局,共有多个页面,首页使用CSS排版比较丰富,色彩鲜明有活力。顶部导航及底部区域背景色为100%宽度,主体内容区域宽度 一套优质的网页设计应该包含 (具体可根据个人要求而定)网站布局方面:计划采用目前主流的、能兼容各大主流浏览器、显示效果稳定的浮动网页布局结构。网站程序方面:计划采用最新的网页编程语言HTML5+CSS3+JS程序语......_基于+javascript&mysgl&html的学校官网

JavaScript 之for循环打印金字塔图形_请用javascript编写一个程序,可以接收一个整数n层数,打印出金字塔一半。(使用for-程序员宅基地

文章浏览阅读9.4k次,点赞6次,收藏21次。需求:1、用for循环打印半个金字塔图形n=5:<html><head><title>打印半个金字塔</title><script type="text/javascript">var n = window.prompt("请输入金字塔的高度(行数)"); for(var i=0;i<=n;i_请用javascript编写一个程序,可以接收一个整数n层数,打印出金字塔一半。(使用for

Linux 2.6.18内核编译_编译linux2.6.18-程序员宅基地

文章浏览阅读1k次。2、下载2.6内核源码下载地址:http://www.kernel.org/pub/linux/kernel/v2.6/linux-2.6.18.tar.bz23、下载内核升级工具(1)下载module-init-tools-3.2.tar.bz2http://www.kernel.org/pub/linux/utils/kernel/module-init-tools/modul_编译linux2.6.18

auto-extending data file /ibdata1 is of a different size 17152 pages (rounded down to MB)_you need to use --log-bin to make --log-replica-up-程序员宅基地

文章浏览阅读1.6k次。问题描述:由于某一个mysql库经常性导致库崩溃,现在需要把该库迁移到另外一个库中,通过xtrabackup备份恢复,当恢复后无法正常启动mysql,查看日志提示如下内容:2018-09-05 10:01:29 20972 [Warning] You need to use --log-bin to make --binlog-format work.2018-09-05 10:01:29 ..._you need to use --log-bin to make --log-replica-updates work.

服务熔断之Google SRE弹性熔断算法_google sre 熔断器-程序员宅基地

文章浏览阅读1.5k次。一、熔断介绍在分布式系统中,一次完整的请求可能需要经过多个服务模块的调用,请求在多个服务中传递,服务对服务的调用会产生新的请求,这些请求共同组成了这次请求的调用链。当调用链中的某个环节,特别是下游服务不可用时,将会导致上游服务调用方不可用,最终将这种不可用的影响扩大到整个系统,导致整个分布式的不可用,引起服务雪崩现象。为了避免这种情况,在下游服务不可用时,保护上游服务的可用性显得极其重要。对此我们可以通过熔断的方式,通过及时熔断服务调用方和服务提供方的调用链,保护服务调用方资源,防止服务雪崩现象的出_google sre 熔断器

Ntrip协议相关(客户端软件或代码)_ntripdemo-程序员宅基地

文章浏览阅读8.9k次,点赞2次,收藏10次。NTRIPNetworked Transport of RTCM via Internet Protocolhttp://hi.baidu.com/study_then/blog/item/a510514ae796d12409f7ef09.htmlNtrip software which is part of an Ntrip Example Implementation is_ntripdemo

推荐文章

热门文章

相关标签