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

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

邻接表

邻接表结构
邻接表数据结构类型如下:

#define  MaxVertices 100
typedef struct node{   //边表 int adjvex;node* next;  
}EdgeNode;  typedef struct{     //顶点表  int vertex;  EdgeNode* edgenext;  
}VertexNode;  typedef VertexNode AdjList[MaxVertices];//顶点表数组  typedef struct{   AdjList adjlist;  int n,e;  
}AdjMatrix; 

注:边表为链表结构,插入元素有头插法和尾插法两种,这里以头插法为例。

对应的,我们得到如下的结构:
邻接表数据结构
我们以无向图为例:
无向图
写出相应的邻接矩阵:
邻接表实际


邻接表生成函数:

void CreateGraph(AdjMatrix* G)  
{  int i,j,k,w,v;  EdgeNode *s;  printf("输入顶点数和边数(中间以空格分开):");  scanf("%d%d",&G->n,&G->e);  printf("建立顶点表\n"); for (i=0;i<G->n;i++)  {  //fflush(stdin);  //如果 stream 指向输入流(如 stdin),那么 fflush 函数的行为是不确定的。//故而使用 fflush(stdin) 是不正确的。getchar(); printf("请输入第%d个顶点的信息:",i+1);G->adjlist[i].vertex=getchar();G->adjlist[i].edgenext=NULL;  }  //前插法 printf("建立边表\n");  for (k=0;k<G->e;k++)  {  printf("输入有连接的顶点序号:");  scanf("%d%d",&i,&j); i-=1;j-=1; //①//对于直接相连的进行编入(即对输入“0 1”时,在0对应的边表中编入1) s=(EdgeNode*)malloc(sizeof(EdgeNode));  s->adjvex=j;//边表赋值 s->next=G->adjlist[i].edgenext;  G->adjlist[i].edgenext=s;  //对于间接相连的进行编入(即对输入“0 1”时,在1对应的边表中编入0)s=(EdgeNode*)malloc(sizeof(EdgeNode));  s->adjvex=i;  s->next=G->adjlist[j].edgenext;  G->adjlist[j].edgenext=s;  }  
}   

邻接表打印函数:

void DispGraph(AdjMatrix *G)
{int i;for (i=0;i<G->n;i++)  {  printf("%d->",i+1);  while(1)  {             if(G->adjlist[i].edgenext==NULL){printf("^");break;	}printf("%d->",G->adjlist[i].edgenext->adjvex+1);//②G->adjlist[i].edgenext=G->adjlist[i].edgenext->next;  }  printf("\n");  }  
} 

注:①②处是由于边表的顺序是对应的是顶点表数组的顺序,所以起始数组为G->adjlist[0],但是按照人们的输入习惯,我们从1开始,所以对于每个输入的i,j进行减1处理存储,再对于输出的G->adjlist[i].edgenext->adjvex进行加1处理,保证输入输出的统一性


具体代码实现:

#include <stdio.h>  
#include <stdlib.h>  
#define  MaxVertices 100
typedef struct node{   //边表 int adjvex;node* next;  
}EdgeNode;  typedef struct{     //顶点表  int vertex;  EdgeNode* edgenext;  
}VertexNode;  typedef VertexNode AdjList[MaxVertices];  typedef struct{   AdjList adjlist;  int n,e;  
}AdjMatrix;  void CreateGraph(AdjMatrix* G)  
{  int i,j,k,w,v;  EdgeNode *s;  printf("输入顶点数和边数(中间以空格分开):");  scanf("%d%d",&G->n,&G->e);  printf("建立顶点表\n"); for (i=0;i<G->n;i++)  {  //fflush(stdin);  //如果 stream 指向输入流(如 stdin),那么 fflush 函数的行为是不确定的。//故而使用 fflush(stdin) 是不正确的。getchar(); printf("请输入第%d个顶点的信息:",i+1);G->adjlist[i].vertex=getchar();G->adjlist[i].edgenext=NULL;  }  //前插法 printf("建立边表\n");  for (k=0;k<G->e;k++)  {  printf("输入有连接的顶点序号:");  scanf("%d%d",&i,&j);  i-=1;j-=1;//①//对于直接相连的进行编入(即对输入“0 1”时,在0对应的边表中编入1) s=(EdgeNode*)malloc(sizeof(EdgeNode));  s->adjvex=j;//边表赋值 s->next=G->adjlist[i].edgenext;  G->adjlist[i].edgenext=s;  //对于间接相连的进行编入(即对输入“0 1”时,在1对应的边表中编入0)s=(EdgeNode*)malloc(sizeof(EdgeNode));  s->adjvex=i;  s->next=G->adjlist[j].edgenext;  G->adjlist[j].edgenext=s;  }  
}   
void DispGraph(AdjMatrix *G)
{int i;for (i=0;i<G->n;i++)  {  printf("%d->",i+1);  while(1)  {             if(G->adjlist[i].edgenext==NULL){printf("^");break;	}printf("%d->",G->adjlist[i].edgenext->adjvex+1); //② G->adjlist[i].edgenext=G->adjlist[i].edgenext->next;  }  printf("\n");  }  
} 
int main()  
{  AdjMatrix* G= (AdjMatrix*)malloc(sizeof(AdjMatrix));  CreateGraph(G);  DispGraph(G); 
}

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

相关文章

邻接表的创建

邻接表 特点&#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;查询下一个邻…

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

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

图的存储结构——邻接表

图的存储结构之邻接表 一、邻接表表示法无向图的邻接表有向图的邻接表有向图的逆邻接表 二、图的邻接表存储表示三、采用邻接表表示法创建无向网 一、邻接表表示法 回忆在线性表时&#xff0c;顺序存储结构就存在预先分配内存可能造成存储空间浪费的问题&#xff0c;于是引出了…

vivado实现FFT和IFFT信号处理

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

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.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…