邻接表的实现（有向邻接表）、（无向邻接表），基于C++

article/2025/8/27 22:28:52

邻接表 

邻接矩阵的实现请看这里

是不错的一种图存储结构，但是，对于边数相对顶点较少的图，这种结构存在对存储空间的极大浪费。因此，找到一种数组与链表相结合的存储方法称为邻接表。
邻接表的处理方法是这样的：

  • （1）图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过，数组可以较容易的读取顶点的信息，更加方便。
  • （2）图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以，用单链表存储，无向图称为顶点vi的边表，有向图则称为顶点vi作为弧尾的出边表。
    例如，下图就是一个无向图的邻接表的结构。

从图中可以看出，顶点表的各个结点由data和firstedge两个域表示，data是数据域，存储顶点的信息，firstedge是指针域，指向边表的第一个结点，即此顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex是邻接点域，存储某顶点的邻接点在顶点表中的下标，next则存储指向边表中下一个结点的指针。
对于带权值的网图，可以在边表结点定义中再增加一个weight的数据域，存储权值信息即可。如下图所示。 

代码实现邻接表（有向邻接表图） 基于C++

/*** C++: 邻接表图** @author lph* */#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;#define MAX 100
// 邻接表
class ListDG {
private: // 内部类// 邻接表中表对应的链表顶点class ENode {public:int ivex;			// 该边所指向的顶点的位置ENode* nextEdge;	// 指向下一条弧的指针};// 邻接表中表的顶点class VNode {public:char data;			//顶点信息ENode* firstEdge;	//指向第一条依赖该顶点的弧};private: // 私有成员int mVexNum;			//图的顶点的数目int mEdgNum;			//图的边的数目VNode mVexs[MAX];		//用一维数组来存储邻接表的顶点public:// 创建邻接表对应的图（自己输入）ListDG();// 创建邻接表对应的图（用已经提供的数据）ListDG(char vexs[], int vlen, char edges[][2], int elen);~ListDG();// 打印邻接表图void print();private:// 读取一个输入字符char readChar();// 返回ch的位置int getPosition(char ch);// 将node节点链接到List的最后void linkLast(ENode* list, ENode* node);
};/*
* 创建邻接表对应的图（自己输入）
*/
ListDG::ListDG() {char c1, c2;int v, e;int i, p1, p2;ENode* node1, * node2;// 输入顶点数和边数cout << "input vertex number: ";cin >> mVexNum;cout << "input edge number: ";cin >> mEdgNum;if (mVexNum < 1 || mEdgNum < 1 || (mEdgNum > (mVexNum * (mVexNum - 1)))) {cout << "input error: invalid parameters! " << endl;return;}// 初始化邻接表的顶点for (i = 0; i < mVexNum; ++i) {cout << "vertex(" << i << "):";mVexs[i].data = readChar();mVexs[i].firstEdge = nullptr;}// 初始化邻接表的边for (i = 0; i < mEdgNum; ++i) {// 读取边的起始点和结束顶点cout << "edge(" << i << "):";c1 = readChar();c2 = readChar();p1 = getPosition(c1);p2 = getPosition(c2);// 初始化node1node1 = new ENode();node1->ivex = p2;// 将node1链接到p1所在链表的末尾if (mVexs[p1].firstEdge == nullptr)mVexs[p1].firstEdge = node1;elselinkLast(mVexs[p1].firstEdge, node1);}
}/*创建邻接表对应的图（用已经提供的数据）
*/
ListDG::ListDG(char vexs[], int vlen, char edges[][2], int elen) {char c1, c2;int i, p1, p2;ENode* node1, * node2;// 初始化顶点数和边数mVexNum = vlen;mEdgNum = elen;// 初始化"邻接表"的顶点for (i = 0; i < mVexNum; i++){mVexs[i].data = vexs[i];mVexs[i].firstEdge = NULL;}// 初始化邻接表的边for (i = 0; i < mEdgNum; ++i) {// 读取边的起始顶点和结束顶点c1 = edges[i][0];c2 = edges[i][1];p1 = getPosition(c1);p2 = getPosition(c2);// 初始化node1node1 = new ENode();node1->ivex = p2;// 将node1链接到p1所在链表的末尾if (mVexs[p1].firstEdge == nullptr)mVexs[p1].firstEdge = node1;elselinkLast(mVexs[p1].firstEdge, node1);}
}/*析构函数
*/
ListDG::~ListDG() {}
/*将node节点连接到List最后
*/ 
void ListDG::linkLast(ENode* list, ENode* node) {ENode* p = list;while (p->nextEdge)p = p->nextEdge;p->nextEdge = node;
}/*返回ch的位置
*/
int ListDG::getPosition(char ch) {int i;for (i = 0; i < mVexNum; ++i) if (mVexs[i].data == ch)return i;return -1; // 失败返回-1}/*读取一个输入字符
*/
char ListDG::readChar() {char ch;do {cin >> ch;} while (!((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')));return ch;
}/*打印邻接表图
*/
void ListDG::print() {int i, j;ENode* node;cout << "List Graph: " << endl;for (i = 0; i < mVexNum; ++i) {cout << i << "(" << mVexs[i].data << "):";node = mVexs[i].firstEdge;while (node != nullptr) {cout << node->ivex << "(" << mVexs[node->ivex].data << ") ";node = node->nextEdge;}cout << endl;}
}
int main() {char vexs[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };char edges[][2] = {{'A', 'B'},{'B', 'C'},{'B', 'E'},{'B', 'F'},{'C', 'E'},{'D', 'C'},{'E', 'B'},{'E', 'D'},{'F', 'G'} };int vlen = sizeof(vexs) / sizeof(vexs[0]);int elen = sizeof(edges) / sizeof(edges[0]);ListDG* pG;// 自定义图（输入矩阵队列）// pG = new ListDG();// 采用已经有的图pG = new ListDG(vexs, vlen, edges, elen);pG->print();return 0;}

用已经有的数据运行代码后的结果（有向邻接表图）为：

用自己手动输入数据的结果（有向邻接表图）：

邻接表的实现（无向邻接表图） ：

/*C++: 邻接表表示的"无向图(List Undirected Graph)"@author lph*/
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;constexpr auto MAX = 100;
// 邻接表;
class ListUDG {
private:// 内部类// 邻接表中表对应的链表的顶点class ENode {public:int ivex;		// 该边所指向的顶点的位置ENode* nextEdge;// 指向下一条弧的指针};// 邻接表中表对应的顶点class VNode {public:char data;		// 顶点信息ENode* firstEdge;// 指向第一条依赖该顶点的弧};
private:int mVexNum;		// 图的顶点个数int mEdgNum;		// 图的边的数目VNode mVexs[MAX];  // 一维数组存储图的顶点，也就是邻接表第一列的顶点
public:// 创建邻接表对应的图（自己输入）ListUDG();// 创建邻接表对应的图（用已经提供的数据）ListUDG(char vexs[], int vlen, char edges[][2], int elen);// 析构函数~ListUDG();// 打印邻接表图void print();
private:// 读取一个输入字符char readChar();// 返回ch的位置int getPosition(char ch);// 将node节点链接到list的最后void linkLast(ENode* list, ENode* node);
};
/*创建邻接表对应的图（自己输入）
*/
ListUDG::ListUDG() {char c1, c2;// int v, e;int i, p1, p2;ENode* node1, * node2;// 输入顶点数和边数cout << "input vertex number: ";cin >> mVexNum;cout << "input edge number: ";cin >> mEdgNum;if (mVexNum < 1 || mEdgNum < 1 || (mEdgNum > (mVexNum * (mVexNum - 1)))) {cout << "input error: invalid parameters!" << endl;return;
}// 初始化邻接表的顶点for (i = 0; i < mVexNum; ++i) {cout << "vertex(" << i << "):";mVexs[i].data = readChar(); // 如果mVexs在之前用的是VNode* mVexs[MAX],那么这里需要用指针mVexs[i]->datamVexs[i].firstEdge = nullptr;}// 初始化邻接表的边for (i = 0; i < mEdgNum; ++i) {// 读取边的起点和结束顶点cout << "edge(" << i << "):";c1 = readChar();c2 = readChar();p1 = getPosition(c1);p2 = getPosition(c2);// 初始化node1node1 = new ENode();node1->ivex = p2;// 将node1链接到p1所在链表的末尾if (mVexs[p1].firstEdge == nullptr)mVexs[p1].firstEdge = node1;elselinkLast(mVexs[p1].firstEdge, node1);// 初始化node2node2 = new ENode();node2->ivex = p1;// 将node2链接到p2所在链表的末尾if (mVexs[p2].firstEdge == nullptr)mVexs[p2].firstEdge = node2;elselinkLast(mVexs[p2].firstEdge, node2);}
}
/*创建邻接表对应的图(用已提供的数据)
*/
ListUDG::ListUDG(char vexs[], int vlen, char edges[][2], int elen) {char c1, c2;int i, p1, p2;ENode* node1, * node2;// 初始化顶点数和边数mVexNum = vlen;mEdgNum = elen;// 初始化邻接表的顶点for (i = 0; i < mVexNum; ++i) {mVexs[i].data = vexs[i];mVexs[i].firstEdge = nullptr;}// 初始化邻接表的边for (i = 0; i < mEdgNum; ++i) {// 读取边的起始顶点和结束顶点c1 = edges[i][0];c2 = edges[i][1];p1 = getPosition(c1);p2 = getPosition(c2);// 初始化node1node1 = new ENode();node1->ivex = p2;// 将node1链接到p1所在的末尾if (mVexs[p1].firstEdge == nullptr)mVexs[p1].firstEdge = node1;elselinkLast(mVexs[p1].firstEdge, node1);// 初始化node2node2 = new ENode();node2->ivex = p1;// 将node2链接到p2所在链表的末尾if (mVexs[p2].firstEdge == nullptr)mVexs[p2].firstEdge = node2;elselinkLast(mVexs[p2].firstEdge, node2);}
}
/*析构函数
*/
ListUDG::~ListUDG() {}
/*将node节点连接到list最后
*/
void ListUDG::linkLast(ENode* list, ENode* node) {ENode* p = list;while (p->nextEdge)p = p->nextEdge;p->nextEdge = node;
}
/*返回ch的位置
*/
int ListUDG::getPosition(char ch) {int i;for (i = 0; i < mVexNum; ++i) if (mVexs[i].data == ch)return i;return -1;
}
/*读取一个输入字符
*/
char ListUDG::readChar() {char ch;do {cin >> ch;} while  (!((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')));return ch;
}/*打印邻接表图
*/
void ListUDG::print() {int i, j;ENode* node;cout << "List Graph:" << endl;for (i = 0; i < mVexNum; ++i) {cout << i << "(" << mVexs[i].data << ")";node = mVexs[i].firstEdge;while (node != nullptr) {cout << node->ivex << "(" << mVexs[node->ivex].data << ")";node = node->nextEdge;}cout << endl;}
}
int main(){char vexs[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };char edges[][2] = {{'A', 'C'},{'A', 'D'},{'A', 'F'},{'B', 'C'},{'C', 'D'},{'E', 'G'},{'F', 'G'} };int vlen = sizeof(vexs) / sizeof(vexs[0]);int elen = sizeof(edges) / sizeof(edges[0]);ListUDG* pG;// 自定义"图"(输入矩阵队列)//pG = new ListUDG();// 采用已有的"图"pG = new ListUDG(vexs, vlen, edges, elen);pG->print();   // 打印图return 0;
}

打印已提供邻接表（无向邻接表图）数据的结果： 

 打印自己输入的邻接表（无向邻接表图）的数据：

 

邻接矩阵的实现请看这里


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

相关文章

邻接表图文详解

邻接表图文详解

在与链表相关的诸多结构中&#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;查询下一个邻…
阅读更多...
图的存储结构---邻接表

图的存储结构---邻接表

1. 邻接表&#xff08;无向图&#xff09; 对于边数相对顶点较少的图&#xff0c;可采取邻接表。把数组与链表结合在一起来存储&#xff0c;这种方式在图结构也适用&#xff0c;称为邻接表&#xff08;AdjacencyList&#xff09;。 2. 邻接表&#xff08;有向图&#xff09…
阅读更多...
图的存储结构——邻接表

图的存储结构——邻接表

图的存储结构之邻接表 一、邻接表表示法无向图的邻接表有向图的邻接表有向图的逆邻接表 二、图的邻接表存储表示三、采用邻接表表示法创建无向网 一、邻接表表示法 回忆在线性表时&#xff0c;顺序存储结构就存在预先分配内存可能造成存储空间浪费的问题&#xff0c;于是引出了…
阅读更多...
vivado实现FFT和IFFT信号处理

vivado实现FFT和IFFT信号处理

一&#xff0c;FFT的物理意义 FFT是离散傅立叶变换的快速算法&#xff0c;可以将一个信号变换到频域。有些信号在时域上是很难看出什么特征的&#xff0c;但是如果变换到频域之后&#xff0c;就很容易看出特征了。这就是很多信号分析采用FFT变换的原因。另外在频谱分析方面&a…
阅读更多...
ifft java_OpenCV DFT_INVERSE与Matlab的ifft不同

ifft java_OpenCV DFT_INVERSE与Matlab的ifft不同

我尝试使用opencv的dft函数过滤信号 . 我试图这样做的方式是在时域中获取信号&#xff1a; x [0.0201920000000000 -0.0514940000000000 0.0222140000000000 0.0142460000000000 -0.00313500000000000 0.00270600000000000 0.0111770000000000 0.0233470000000000 -0.00162700…
阅读更多...
4.8 IFFT/FFT

4.8 IFFT/FFT

4.8.1 IFFT/FFT原理 1. IFFT、FFT在OFDM系统中的应用 2、IFFT/FFT原理 3、DIT的基2FFT算法 4、DIF的基2FFT运算 5、基于的频率抽选FFT算法 4.8.2 基于 DIF FFT的硬件 结构 1、各级的蝶形运算硬件实现 2、transfer12、 transfer34、transfer56硬件实现 3、transfer23、 transfe…
阅读更多...
Python实现FFT及IFFT

Python实现FFT及IFFT

运行环境及编译工具 WindowsVS Code 编程语言及库版本 库版本Python3.7.0copy无numpy1.19.2opencv3.4.2PIL8.1.0matplotlib3.4.3 可执行文件 HW_2.pyHW_2.ipynb在HW_2.ipynb中执行&#xff0c;详细程序信息在HW_2.py中 问题 1 通过计算一维傅里叶变换实现图像二维快速傅里…
阅读更多...
matlab FFT 和IFFT

matlab FFT 和IFFT

代码&#xff1a; fs100;N128; n0:N-1;tn/fs; xsin(2*pi*40*t)sin(2*pi*15*t); subplot(221);plot(n,x,b); xlabel(时间/s);ylabel(x);title(原始信号); grid on;yfft(x,N); magabs(y); fn*fs/N; subplot(222);plot(f(1:N/2),mag(1:N/2)*2/N,b); xlabel(频率/Hz);ylabel(振幅)…
阅读更多...
基于vivado实现FFT/IFFT

基于vivado实现FFT/IFFT

文章目录 前言一、基本过程二、vivado配置1.新建工程2.调用DDS的IP核2.调用FFT的IP核 三、编写Verilog程序1.顶层文件fft.v2.仿真文件fft_tb.v 四、运行仿真1. 运行仿真设置2. 仿真波形设置3. 结果分析 前言 使用vivado2018.3实现FFT&#xff0f;IFFT&#xff0c;过程比较详细…
阅读更多...
python fft ifft

python fft ifft

文章目录 条件代码实例 条件 任何一个满足狄利克雷条件的函数都可以通过傅里叶基数展开。 numpy和scipy中都有fft变换&#xff0c;且效果都是一样的。 代码 import numpy as np from scipy.fftpack import fft,ifft import matplotlib.pyplot as plt from matplotlib.pylab …
阅读更多...
FFT专题:IFFT后信号如何重建

FFT专题:IFFT后信号如何重建

ifft(outFFTData, g_fft_temp, inFFTData, g_twiddle_ifft, twiddle_stride, F_WLEN);//思考ifft输出的复数结果怎么给到硬件输出 之前一直关注FFT后信号奔赴到频域处理,那么频域处理完后,怎么重建信号呢? 给出一段FFT和IFFT函数源码 int nFrameRunCount 0;#pragma section…
阅读更多...
数字信号处理基础(二):FFT和IFFT的使用以及详细分析代码书写思路

数字信号处理基础(二):FFT和IFFT的使用以及详细分析代码书写思路

目录 1. fft和ifft的原理1.1 fft1.2 ifft 2. 书写代码思路3. 完整代码4. 结果图 1. fft和ifft的原理 1.1 fft fft是快速傅里叶变换&#xff0c;是MATLAB中计算信号频谱的函数&#xff0c;使用方法是fft(x)&#xff0c;直接对信号x进行fft计算。 由于fft函数计算信号的频谱是0…
阅读更多...
信号处理中的反傅里叶变换（IFFT）原理

信号处理中的反傅里叶变换（IFFT）原理

信号处理中&#xff0c;经常需要将信号转换到频域进行分析&#xff0c;有时候还会从频域转回时域&#xff0c;用到FFT和IFFT函数。 FFT变换是将信号从时域转换到频域&#xff0c;在时域看起来复杂的信号转换到频域看起来就方便容易了很多。但有时候也需要将频域信号转换到时域…
阅读更多...
adb下载、安装、环境配置

adb下载、安装、环境配置

一&#xff1a;adb安装 adb下载链接&#xff1a;https://pan.baidu.com/s/1Vd6KyZ6vT2Qtmhazwre4OQ 提取码&#xff1a;3dx1 安装&#xff1a; 1.双击adb.exe文件&#xff0c;并运行。 2.添加环境变量&#xff1a; 右击计算机–属性—高级系统设置—高级—环境变量—新建&…
阅读更多...
推荐文章

Copyright @ 2022~2023