图的存储--邻接表

article/2025/8/27 19:44:42

邻接表既适用于存储无向图,也适用于存储有向图。邻接表常用于稀疏图的存储。

邻接表存储图主要在于将图的各顶点建立一个链表,链表记录该顶点的邻接点的在数组的位置。

 

#define MAX_VERTEX_NUM 10	// 最大顶点数
#define INF 32767			// 不邻接
typedef char verType;		// 顶点类型
typedef string infoType;	// 弧上信息类型
typedef enum { UDG, DG, UDN, DN }Graph;	// 无向图、有向图、无向网、有向网
// 弧
struct ArcNode {ArcNode() :adjIndex(INF), Next(NULL), info(NULL) {}int adjIndex;	// 邻接节点下标ArcNode* Next;	// 下一邻接节点	infoType* info;
};
// 顶点
typedef struct VerNode {VerNode() :first(NULL) {}VerNode(verType ver) :vertex(ver), first(NULL) {}verType vertex;		// 数据域ArcNode* first;		// 指向第一个邻接节点
}AdjList[MAX_VERTEX_NUM];
// 邻接表
struct ALGraph {AdjList adj;	// 邻接表int ver_num;	// 顶点数int arc_num;	// 边数Graph Kind;		// 图类型
};

获取顶点在数组位置:

// 获取顶点位置
int LocateVertex(ALGraph &graph, verType ver) {for (int i = 0; i < graph.ver_num; ++i) {if (ver == graph.adj[i].vertex) return i;}return -1;
}

创建图:

// 创建无向图
void CreatUDG(ALGraph &graph) {graph.Kind = UDG;cout << "输入顶点数、边数>>" << endl;cin >> graph.ver_num >> graph.arc_num;cout << "输入顶点信息>>" << endl;for (int i = 0; i < graph.ver_num; ++i) {cin >> graph.adj[i].vertex;graph.adj[i].first = NULL;}verType v1, v2;int index1, index2;for (int i = 0; i < graph.arc_num; ++i) {cout << "输入邻接的顶点>>" << endl;cin >> v1 >> v2;index1 = LocateVertex(graph, v1);index2 = LocateVertex(graph, v2);if (index1 < 0 || index2 < 0) {cout << "邻接顶点有误" << endl;--i;continue;}// 头插法插入邻接表ArcNode* arc1 = new ArcNode();ArcNode* arc2 = new ArcNode();arc1->adjIndex = index2;arc1->Next = graph.adj[index1].first;graph.adj[index1].first = arc1;	// 头插arc2->adjIndex = index1;arc2->Next = graph.adj[index2].first;graph.adj[index2].first = arc2;	// 头插cout << "弧上是否存储信息" << endl;cout << " 1.是   0、否" << endl;int Is_info;cin >> Is_info;if (Is_info) {cout << "输入弧上信息" << endl;infoType INFO;cin >> INFO;graph.adj[index1].first->info = new infoType(INFO);graph.adj[index2].first->info = new infoType(INFO);}}
}
// 创建有向图
void CreatDG(ALGraph &graph) {graph.Kind = DG;cout << "输入顶点数、边数>>" << endl;cin >> graph.ver_num >> graph.arc_num;cout << "输入顶点信息>>" << endl;for (int i = 0; i < graph.ver_num; ++i) {cin >> graph.adj[i].vertex;graph.adj[i].first = NULL;}verType v1, v2;int index1, index2;for (int i = 0; i < graph.arc_num; ++i) {cout << "输入邻接的顶点>>" << endl;cin >> v1 >> v2;index1 = LocateVertex(graph, v1);index2 = LocateVertex(graph, v2);if (index1 < 0 || index2 < 0) {cout << "邻接顶点有误" << endl;--i;continue;}cout << "弧上是否存储信息" << endl;cout << " 1.是   0、否" << endl;int Is_info;cin >> Is_info;ArcNode* arc = new ArcNode();arc->adjIndex = index2;arc->Next = graph.adj[index1].first;graph.adj[index1].first = arc;	// 头插if (Is_info) {cout << "输入弧上信息" << endl;infoType INFO;cin >> INFO;graph.adj[index1].first->info = new infoType(INFO);}}
}

输出图的邻接表:
 

// 遍历
void Traverse(ALGraph &graph) {for (int i = 0; i < graph.ver_num; ++i) {ArcNode* T = graph.adj[i].first;int index;while (T) {index = T->adjIndex;cout << "顶点 " << graph.adj[i].vertex << " <----> "<< "顶点 " << graph.adj[index].vertex;if (T->info) {cout << " 弧上信息:" << *(T->info);}cout << endl;T = T->Next;}}
}


http://chatgpt.dhexx.cn/article/Q3NYnJXY.shtml

相关文章

有向图的邻接矩阵、邻接表和逆邻接表

1、如何根据有向图画出邻接矩阵&#xff1f; 如图&#xff1a; v1指向v2和v3&#xff0c;在矩阵中v1指向v2、v3的表示标1。 注意&#xff1a; v1指向v2在矩阵中是用竖列的v1对应横行的v2 2、如何根据有向图画出邻接表呢&#xff1f; 注意&#xff1a; 画有向图的邻接表时…

【数据结构】 图的邻接表

邻接表是图的另一种存储结构&#xff08;使用链表的思想&#xff09;。 该方式的基本思路&#xff1a;顶点表后指向邻接表&#xff0c;邻接表中依次为当前顶点的邻接点 准备工作 与邻接矩阵类似&#xff0c;在构造邻接表之前&#xff0c;需要存储各个顶点的信息&#xff0c;…

《数据结构》-图的邻接表表示法(四)

邻接表表示法(链式) 存储定义&#xff1a; 顶点&#xff1a;按编号顺序将顶点数据存储在一维数组中关联同一顶点的边(以顶点为尾的弧)&#xff1a;用线性链表存储 无向图的邻接表 例如&#xff0c;如下无向图 则它的邻接表为 无向图邻接表的特点&#xff1a; 邻接表不唯一…

【图】邻接表

目录 无向图的邻接表 链表&#xff08;存相邻顶点下标&#xff09;的类 数组里放的顶点 邻接表&#xff08;操作&#xff09; 构造和析构&#xff08;创建销毁邻接表&#xff09; 插入顶点 插入边 获取下标 插v1、v2之间的边 删除顶点 删除边 输出&#xff1a; 其他…

图的邻接表表示法(C语言)

邻接表 邻接表数据结构类型如下&#xff1a; #define MaxVertices 100 typedef struct node{ //边表 int adjvex;node* next; }EdgeNode; typedef struct{ //顶点表 int vertex; EdgeNode* edgenext; }VertexNode; typedef VertexNode AdjList[MaxVertices];//…

邻接表的创建

邻接表 特点&#xff1a; 1、想要知道某个顶点的度&#xff0c;就去查找这个顶点的边表中结点的个数 2、若想判断顶点 Vi 到 Vj是否存在边&#xff0c;只需测试顶点 Vi 的边表中adjvex是否存在 Vj 的下标。 3、若求顶点的所有邻接点&#xff0c;其实就是对此顶点的边表进行遍历…

邻接表创建

邻接矩阵是个不错的图储存结构&#xff0c;但我们发现&#xff0c;对于边数相对顶点较少的图&#xff0c;这种结构是存在对储存空间的极大浪费的&#xff08;关于邻接矩阵的相关知识在这里&#xff1a;邻接矩阵的创建&#xff09;&#xff0c;因此我们要考虑另外一种存储结构方…

邻接表和邻接矩阵

进入图论的大门&#xff08;深渊&#xff09;之前&#xff0c;我们一定要掌握的两种必备手段——邻接表和邻接矩阵&#xff0c;此刻将成为我们的巨大帮手&#xff08;其实做不来题还是做不来&#xff09;&#xff0c;下面让我们来学习一下&#xff0c;这两种存图方式在计算机中…

图的邻接矩阵和邻接表的比较

欢迎关注“软件开发理论”公众号获取干货 图的存储结构主要分两种&#xff0c;一种是邻接矩阵&#xff0c;一种是邻接表。 1.邻接矩阵 图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息&#xff0c;一个二维数组&#xff08;邻接矩阵&#xff09;存储图…

无向图邻接表实现

无向图邻接表实现 顶点&#xff1a;按照编号顺序将顶点数据存储在一维数组当中 关联同一个顶点的边&#xff08;以顶点为尾的弧&#xff09;&#xff1a;用线性链表存储 头结点&#xff1a;datafirstarc 表结点&#xff1a;adjvex&#xff08;邻接点的序号&#xff0c;存放…

邻接矩阵和邻接表

图的存储结构主要分两种&#xff0c;一种是邻接矩阵&#xff0c;一种是邻接表。 1.邻接矩阵 邻接矩阵的存储方式是用两个数组来表示图。一个一维数组储存图中顶点信息&#xff0c;一个二维数组储存图中的边或弧的信息。 无向图 这里右图是把顶点作为矩阵内行和列的标头罗列出…

图--邻接表

邻接表是图结构中的一种存储结构&#xff0c;适用于存储无向图和有向图。 邻接表存储图的实现方式是&#xff0c;给图中的各个顶点独自建立一个链表&#xff0c;用节点存储该顶点&#xff0c;用链表中其他节点存储各自的临界点。 与此同时&#xff0c;为了便于管理这些链表&a…

邻接表的实现(有向邻接表)、(无向邻接表),基于C++

邻接表 邻接矩阵的实现请看这里 是不错的一种图存储结构&#xff0c;但是&#xff0c;对于边数相对顶点较少的图&#xff0c;这种结构存在对存储空间的极大浪费。因此&#xff0c;找到一种数组与链表相结合的存储方法称为邻接表。 邻接表的处理方法是这样的&#xff1a; &a…

邻接表图文详解

在与链表相关的诸多结构中&#xff0c;邻接表是相当重要的一个。它是树与图结构的一般化存储方式&#xff0c; 邻接表可以看成“带有索引数组的多个数据链表”构成的结构集合。在这样的结构中存储的数据被分成若干类&#xff0c;每一类的数据构成一个链表。每一类还有一个代表元…

数据结构 图的邻接表

呃&#xff0c;下面该写邻接表了....... 邻接表的出现是因为图若是稀疏图&#xff0c;用邻接矩阵会造成空间的浪费&#xff0c;毕竟你要开辟一个一维数组和一个二维数组嘛&#xff0c;而且还是大开小用的那种。 邻接表为了避免内存的浪费引入了链式存储&#xff0c;它的处理办…

怎么画邻接表?不用邻接矩阵也能画?

目录 一、有向图的邻接表 二、无向图的邻接表 一、有向图的邻接表 最简单粗暴的方式就是把某个顶点发出的箭头指向的顶点全作为单个结点连接到此顶点的后面。结点数等于边数。 按正常思路的话&#xff0c;是一种递归遍历。 1.选一个点作为出发点。比如选一个v0。 2.从第一出…

数据结构之图(三)——邻接表

邻接表表示法(链式) 顶点&#xff1a; 按编号顺序将顶点数据存储在一维数组中。关联同一顶点的边&#xff1a; 用线性链表存储。如果有边\弧的信息&#xff0c;还可以在表结点中增加一项&#xff0c; 无向图的邻接表 例子&#xff1a; 特点&#xff1a; 邻接表不唯一若无向…

邻接表

邻接表&#xff1a;所谓邻接表&#xff08;adjacency list&#xff09;&#xff0c;就是把从同一个顶点发出的边链接在同一个称为边链表的单链表中。边链表的每个结点代表一条边&#xff0c;称为边结点。每个边结点有2 个域&#xff1a;该边终点的序号&#xff0c;以及指向下一…

图的邻接表

邻接表 图的邻接表存储方法跟树的孩子链表示法相类似&#xff0c;是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点&#xff0c;则把相邻顶点依次存放于表头结点所指向的单向链表中。如词条概念图所示&#xff0c;表结点存放的是邻接顶点在…

【数据结构】图的存储结构—邻接表

目录 什么是邻接表&#xff1f; 邻接表&#xff1a;定义 邻接表&#xff1a;相关类 邻接表&#xff1a;基本操作 1&#xff09;创建无向网 2&#xff09;创建有向网 3&#xff09;顶点定位 4&#xff09;插入边 5&#xff09;第一个邻接点 6&#xff09;查询下一个邻…