邻接表存储结构(简单理解图的存储结构)

发布日期:2022-04-15 22:19:01 来源:郑州计算机学校

邻接表是图的一种最主要存储结构,用来描述图上的每一个点。对图的每个顶点建立一个容器(n个顶点建立n个容器),第i个容器中的结点包含顶点Vi的所有邻接顶点。

例如,有向图如图1所示,其邻接表如图2所示。

邻接表存储结构(简单理解图的存储结构)_http://www.jidianku.com_计算机基础知识_第1张

1 数据结构

邻接表用到两个数据结构:

(1) 头结点表,用一维数组存储。包括顶点和指向第一个邻接点的指针。

(2) 每个顶点vi的所有邻接点构成一个线性表,用单链表存储。无向图称为顶点vi的边表,有向图称为顶点vi作为弧尾的出边表,存储的是顶点的序号,和指向下一个边的指针。

头结点:

struct Hnode{ //定义顶点类型 Node *first; //指向第一个邻接点 };

首先创建邻接表表头,初始化每个结点的第一个邻接点为NULL,如图3所示。

邻接表存储结构(简单理解图的存储结构)_http://www.jidianku.com_计算机基础知识_第2张

表结点:

struct Node{ //定义表结点 int v; //以v为弧头的顶点编号 int w; //边的权值 Node *next; //指向下一个邻接结点 };

表结点如图4所示↑。

2 创建邻接表

刚开始的时候把顶点表初始化,指针指向null。然后邻接点的表结点插入进来,插入到first指向的结点之前。

(1) 输入第一条边的结点和权值w、v、w分别为1、3、10。

创建一条边,如图5所示。

邻接表存储结构(简单理解图的存储结构)_http://www.jidianku.com_计算机基础知识_第3张

对应的表结点,如图6所示↑。

将表结点链接到头结点表中,如图7所示。

邻接表存储结构(简单理解图的存储结构)_http://www.jidianku.com_计算机基础知识_第4张

(2) 输入第二条边的结点和权值w、v、w分别为1、2、12。

创建一条边,如图8所示↑。

对应的表结点,如图9所示↑。

将表结点链接到头结点表中,实际上是插入到1号顶点的邻接单链表的表头,即first指向的邻接点之前,如图10所示↑。

注意:由于后输入的插入到了单链表的前面,因此输入顺序不同,建立的单链表也不同。

3 输出邻接表

邻接表存储结构(简单理解图的存储结构)_http://www.jidianku.com_计算机基础知识_第5张

4 代码

邻接表存储结构(简单理解图的存储结构)_http://www.jidianku.com_计算机基础知识_第6张

运行输入:

请输入顶点数n和边数m: 6 9 请依次输入每条边的两个顶点u,v和边的权值w: 1 3 10 1 2 12 2 4 8 3 5 13 3 2 2 4 6 18 4 3 5 5 6 4 5 4 6

运行输出:

----------邻接表如下:---------- v1: [2 12] [3 10] v2: [4 8] v3: [2 2] [5 13] v4: [3 5] [6 18] v5: [4 6] [6 4] v6:

附原代码:

//adjlist #include <iostream> using namespace std; const int N=10000; struct Node { //定义表结点 int v; //以v为弧头的顶点编号 int w; //边的权值 Node *next; //指向下一个邻接结点 }; struct Hnode{ //定义顶点类型 Node *first; //指向第一个邻接点 }; Hnode g[N]; int n,m,i,u,v,w; void insertedge(Hnode &p,int x,int y) //插入一条边 { Node *q; q=new(Node); q->v=x; q->w=y; q->next=p.first; p.first=q; } void printg(int n) //输出邻接表 { cout<<"----------邻接表如下:----------"<<endl; for(int i=1;i<=n;i++) { Node *t=g[i].first; cout<<"v"<<i<<": "; while(t!=NULL) { cout<<"["<<t->v<<" "<<t->w<<"] "; t=t->next; } cout<<endl; } } int main() { cout<<"请输入顶点数n和边数m:"<<endl; cin >>n>>m; for(i=1; i<=n; i++) g[i].first=NULL; cout<<"请依次输入每条边的两个顶点u,v和边的权值w:"<<endl; for(i=0;i<m;i++) { cin>>u>>v>>w; insertedge(g[u],v,w); //无向图时还要插入一条反向边 } printg(n); //输出邻接表 system("pause"); return 0; } -End-


温馨提示:内容来源于网络,仅用于学习交流,无任何商业用途,如有不妥或侵权,请告知,立删!

热门专业推荐

计算机软件应用技术

本专业主要面向机关、企业、事业、公司等应用计算机技术的相关领域,培养具有扎实的计算机专业知识、计算机网络基本应用能力,能够从事计算机办公自动化、计算机综合应用和计算机网络搭建管理,熟练掌握计算机网络构建及管理能力、计算机硬件安装与维护能力、绘图制图能力、网页设计能力,并在建筑信息设计技术方面达到一定水平的高素质技术技能型人才。

电子商务专业

本专业培养学生熟悉信息科技与技术的基本知识和方法,掌握电子商务系统工程的开发、应用与管理的技术和技能,具有创新精神、较强的管理能力和独立分析问题的能力。

计算机平面(3D)设计

本专业培养学生具有动漫设计、制作、绘画、广告设计、网页设计等技能,具备熟练计算机操作能力的技术应用型人才。

音视频剪辑(影视后期制作)

本专业培养以这个专业的培养目标是培养学生具备扎实的文学功底和通晓视听语言的能力,同时熟练掌握包括数字化技术在内的各种剪辑技术。