图的邻接表存储结构细况
发布时间：2022-07-10 05:18:23 所属栏目：语言 来源：互联网
导读：通常，图更多的是采用链表存储，具体的存储方法有 3 种，分别是邻接表、邻接多重表和十字链表。 在具体讲解邻接表存储图的实现方法之前，先普及一个邻接点的概念。在图中，如果两个点相互连通，即通过其中一个顶点，可直接找到另一个顶点，则称它们互为邻
|
通常，图更多的是采用链表存储，具体的存储方法有 3 种，分别是邻接表、邻接多重表和十字链表。 在具体讲解邻接表存储图的实现方法之前，先普及一个"邻接点"的概念。在图中，如果两个点相互连通，即通过其中一个顶点，可直接找到另一个顶点，则称它们互为邻接点。 邻接指的是图中顶点之间有边或者弧的存在。 邻接表存储图的实现方式是，给图中的各个顶点独自建立一个链表，用节点存储该顶点，用链表中其他节点存储各自的临界点。 与此同时，为了便于管理这些链表，通常会将所有链表的头节点存储到数组中（也可以用链表存储）。也正因为各个链表的头节点存储的是各个顶点，因此各链表在存储临界点数据时，仅需存储该邻接顶点位于数组中的位置下标即可。 拿顶点 V1 来说，与其相关的邻接点分别为 V2 和 V3，因此存储 V1 的链表中存储的是 V2 和 V3 在数组中的位置下标 1 和 2。 链接表结构转化为对应 C 语言代码如下： #define MAX_VERTEX_NUM 20//最大顶点个数 #define VertexType int//顶点数据的类型 #define InfoType int//图中弧或者边包含的信息的类型 typedef struct ArcNode{ int adjvex;//邻接点在数组中的位置下标 struct ArcNode * nextarc;//指向下一个邻接点的指针 InfoType * info;//信息域 }ArcNode; typedef struct VNode{ VertexType data;//顶点的数据域 ArcNode * firstarc;//指向邻接点的指针 }VNode,AdjList[MAX_VERTEX_NUM];//存储各链表头结点的数组 typedef struct { AdjList vertices;//图中顶点的数组 int vexnum,arcnum;//记录图中顶点数和边或弧数 int kind;//记录图的种类 }ALGraph; 邻接表计算顶点的出度和入度 使用邻接表计算无向图中顶点的入度和出度会非常简单，只需从数组中找到该顶点然后统计此链表中节点的数量即可。 （编辑：云计算网_宿迁站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
站长推荐