图论之邻接表

这篇具有很好参考价值的文章主要介绍了图论之邻接表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

 路径规划系列文章目录

  1. 路径规划算法综述
  2. 图论基础介绍
  3. 图论之邻接矩阵

目录

 路径规划系列文章目录

一、邻接表

二、邻接表实现

2.1 链式前向星实现

2.2 链表实现

三、总结


一、邻接表

        由于对于稀疏图来说,使用邻接矩阵进行存储显然会使得空间利用率较低,因此利用邻接表来存储图,可以克服这一缺点。

        前面我们提到过,图其实就是由顶点和边构成的,因此我们可以将图分两部分来组织,即顶点与其连接的边。对于顶点而言,我们只需要存储顶点的信息以及边的地址,存储顶点信息代表着顶点的编号,有了边的地址就能够访问与其相连的边的信息,此外一般我们将顶点按照1,2,3...n来进行编号,这样可以将顶点表示为一个数组,只需要通过顶点编号对应位下标即可访问各个顶点。对于边来说,只需要存储边的权重,所连接的顶点编号以及下一条边的地址即可,因此边适合用链表来存储。

        综上所述的分析,我们可以知道顶点表的要点主要有:

  1. 顶点表是一个数组,每个结点通过结点编号所对应的下标访问
  2. 结点中包含存储的顶点数据,这里是顶点编号
  3. 每个顶点表的结点中还包含其所对应边结点的地址,由于边是用链表来表示的,因此只需要知道与其相连的任意一条边结点的地址即可。

        因此顶点表的结点如下图所示。

邻接表,路径规划,图论,算法,c++,数据结构

        同样地,边链表的要点有:

  1.  边链表是链表构建成的
  2. 边链表中包含该边的权重
  3. 边链表中还包含另一个顶点信息,(由于边链表一定是根据某个顶点访问到的,因此在访问边链表前已经知道了一个顶点的信息,所以只需要在记录下另一个顶点的信息即可)
  4. 边链表中包含连接在该顶点上的下一条边的地址(以便访问下一条边)

        因此边链表的结点如下图所示。

邻接表,路径规划,图论,算法,c++,数据结构

 下面是一张图与其对应邻接表的示例:
 

邻接表,路径规划,图论,算法,c++,数据结构

邻接表,路径规划,图论,算法,c++,数据结构

二、邻接表实现

        这里提供两种邻接表的实现方法,一种是链式前向星的方法,另一种是使用链表实现。下面分别介绍。

2.1 链式前向星实现

        使用链式前向星其实就是利用两个数组来模拟链表实现邻接表,并且我们不但对顶点进行编号,我们还对边进行编号,因为每一条边都包含信息,相对于其他边都是独立的,因此我们可以将边也用数组来表示,并且使用其下标访问。

        我们重点来介绍如何添加边的信息。我们使用head[]数组来表示头结点,如head[n] = a;表示头结点n的首个边的编号为a。用e[]结构体数组表示边结点。边界点存储了该边的权重、下一个结点的编号,以及下一条边的编号。其定义如下

const int M=500;//边的最大数量 
struct Edge //边结结点构体 
{
	int to,w;//分别表示下一个顶点编号以及该条边的权重	
	int next;//下一条边的编号 
}e[M]; 

        我们从1开始对边结点进行编号,每添加一条边,编号就+1,添加时采用头插法添加,比如说当向第i个顶点上添加边的时候,只需要将新的边的next=head[i],然后将head[i]=新的边的编号即可。这里使用一个整型变量idx为其分配编号。

邻接表,路径规划,图论,算法,c++,数据结构

邻接表,路径规划,图论,算法,c++,数据结构

         插入结束后,则链表状态如下所示

邻接表,路径规划,图论,算法,c++,数据结构

        代码如下所示

#include<iostream>
#include<cstring>
using namespace std;

const int N=500;//顶点最大数量 
const int M=500;//边的最大数量 
const int INF = 1e9;//最大权重 

int n;
int head[N];//顶点结点数组 
int idx;//边结点的编号 


struct Edge //边结结点构体 
{
	int to,w;//分别表示下一个顶点编号以及该条边的权重	
	int next;//下一条边的编号 
}e[M]; 

void init()
{
	memset(head,-1,sizeof(head));//将头结点指向第一个编号设置为-1 
	idx = 1;//边编号从1开始 
}

void add(int a,int b,int w)//添加边 
{
	e[idx].to = b;//与边相连的另一个顶点编号 
	e[idx].w = w;//设置权重 
	e[idx].next = head[a];//边指向顶点a的下一条边的编号 
	head[a] = idx;//更新顶点a指向的边 
	idx++;//编号自增1 
}

void testEdge()
{
	int m;
	cin>>n>>m;//输入顶点数量和边的数量 
	init();
	int a,b,w;
	while(m--)
	{
		cin>>a>>b>>w;
		add(a,b,w);	
	}
	
	/*按照结点打印图*/ 
	for(int i=1;i<=n;i++)
	{
		cout<<i<<"->";
		for(int j=head[i];j!=-1;j=e[j].next)
		{
			cout<<e[j].to<<"("<<e[j].w<<")"<<"->"; 
		}
		cout<<endl;
	}
	
}

int main()
{
	testEdge();
}

2.2 链表实现

#include<iostream>
#include<queue>
#include<stack>

using namespace std;

#define INF 65333
#define MaxVerNum 1000 //定义最大顶点个数
typedef char elementType; //定义定点数据类型
typedef int einfoType;  //定义权值数据类型 
 
//边链表结点结构 
typedef struct eNode
{
	int adjVer; //边链表编号
	einfoType einfo;//边链表边信息
	struct eNode* next; //边链表下一个结点 
}EdgeNode;//链表结点类型 

typedef struct vNode
{
	elementType data;//存放图中顶点数据值 
	EdgeNode* firstEdge;
}VerNode;//顶点表结点类型 


class Graph
{
private:
	VerNode* VerList;//结点 
	int VerNum;//顶点个数 
	int ArcNum;//边数 

public:

	void CreateGraph();
	void printGraph();
};

void Graph::CreateGraph()
{
	int vNum,aNum;
	cin>>vNum>>aNum;//输入顶点数量和边数量 
	ArcNum = aNum;
	VerNum = vNum; 
	VerList = new VerNode[VerNum+1];//给顶点表开辟空间 
	
	while(vNum)//初始化顶点表 
	{
		VerList[vNum].data = 0;
		VerList[vNum].firstEdge = NULL;
		vNum--;
	}
	
	aNum = ArcNum;
	
	while(aNum--)//输入图信息 
	{
		int a,e,w;
		cin>>a>>e>>w;
		EdgeNode *en = new EdgeNode; 
		en->einfo = w;//给边付权重 
		en->adjVer = e;//设置另一个顶点编号 
		VerList[a].data = a;//设置该顶点编号 
		en->next = VerList[a].firstEdge;//该边结点下一个指向第一个边结点 
		VerList[a].firstEdge = en;//第一个边结点指向该边 
	}

}

void Graph::printGraph() 
{
	int vNum;
	vNum = VerNum;
	while(vNum)
	{
		EdgeNode* pe;
		cout<<vNum<<"->";
		for(pe = VerList[vNum].firstEdge;pe!=NULL;pe=pe->next)
		{
			cout<<pe->adjVer<<"("<<pe->einfo<<")->";
		}
		vNum--;
		cout<<endl;
	}
}

int main()
{
	Graph g;
	g.CreateGraph();
	g.printGraph();
}

三、总结

        本文介绍了图的邻接表存储方法,使用邻接表存储图要稍微复杂一些,但能够提高空间利用率。本文给出了两种实现方法,一种是链式前向星,另一种是链表实现,链式前向星是利用数组来模拟链表,并且在最后给出了邻接表的一种打印方法。文章来源地址https://www.toymoban.com/news/detail-763664.html

到了这里,关于图论之邻接表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】算法题:邻接表构造相应的逆邻接表

    编写算法:根据含有n个顶点的有向图邻接表,构造相应的逆邻接表。 1.算法的思想: 邻接表和逆链接表的 顶点信息是相同的 ,直接复制即可。把 出边信息转换成入边信息 ,则需要逐一访问邻接表的各结点的出边表,把边结点通过头插法插入相应的入边表中。 2.算法的实现

    2024年02月11日
    浏览(47)
  • 数据结构与算法基础-学习-23-图之邻接矩阵与邻接表

    目录 一、定义和术语 二、存储结构 1、邻接矩阵 1.1、邻接矩阵优点 1.2、邻接矩阵缺点 2、邻接表 3、邻接矩阵和邻接表的区别和用途 3.1、区别 3.2、用途 三、宏定义 四、结构体定义 1、邻接矩阵 2、邻接表 3、网数据类型(造测试数据) 五、函数定义 1、使用邻接矩阵创建无

    2024年02月14日
    浏览(33)
  • 【数据结构与算法】图的基本概念 | 邻接矩阵和邻接表 | 广度优先遍历和深度优先遍历

    🌠 作者:@ 阿亮joy. 🎆 专栏:《数据结构与算法要啸着学》 🎇 座右铭:每个优秀的人都有一段沉默的时光,那段时光是付出了很多努力却得不到结果的日子,我们把它叫做扎根 图是由顶点集合及顶点间的关系组成的一种数据结构:G = (V, E) ,其中: 顶点集合V = {x|x属于某

    2024年02月04日
    浏览(69)
  • 【数据结构与算法】图论及其相关算法

    线性表局限于一个直接前驱和一个直接后继的关系,树也只能有一个直接前驱也就是父节点,当我们需要表示多对多的关系时, 这里我们就用到了图。 图是一种数据结构,其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边。 结点也可以称为顶点。如图:

    2024年02月09日
    浏览(38)
  • 【图论】Dijkstra 算法求最短路 - 构建邻接矩阵(带权无向图)

    题目链接:1976. 到达目的地的方案数

    2024年03月22日
    浏览(44)
  • Dijkstra算法——邻接矩阵实现+路径记录

    本文是在下面这篇文章的基础上做了一些补充,增加了路径记录的功能。具体Dijkstra的实现过程可以参考下面的这篇文章。 [jarvan:Dijkstra算法详解 通俗易懂](Dijkstra算法详解 通俗易懂 - jarvan的文章 - 知乎 https://zhuanlan.zhihu.com/p/338414118) 创建 GraphAdjMat 类 GraphAdjMat 类用来实现图的

    2024年01月18日
    浏览(37)
  • 图论之寻找桥边

    目录 ①基准法 ②并查集 ③逆向思维之标记环边 ④并查集压缩路径 主函数读取文件调函数方法处理 在图论中,一条边被称为“桥”代表这条边一旦被删除,这张图的连通块数量会增加。等价地说,一条边是一座桥当且仅当这条边不在任何环上。一张图可以有零或多座桥。

    2024年02月16日
    浏览(36)
  • 图论之毕克定理证明

    毕克定理是小学四年级奥赛内容,无意间从一本教材上看到,觉得定理蛮有意思,也和自己从事的工作有一些关联,就在网上找了一些证明资料,结合自己的思考,稍微挖掘了以下,聊以记录。 毕克定理是指一个计算点阵中顶点在格点上的多边形面积公式,该公式可以表示为

    2024年02月15日
    浏览(49)
  • C++图论之强连通图

    什么是连通性? 连通,字面而言,类似于自来水管道中的水流,如果水能从某一个地点畅通流到另一个地点,说明两点之间是连通的。也说明水管具有连通性,图中即如此。 无向图和有向图的连通概念稍有差异。 无向图连通性 如果任意两点间存在路径,称此图具有连通性

    2024年02月03日
    浏览(36)
  • 数据结构的应用场景:如社交网络、路由算法、图论、网络协议等

    作者:禅与计算机程序设计艺术 数据结构(Data Structure)是计算机科学中存储、组织、管理数据的方式,主要用于解决信息检索、处理和运算时的效率及空间占用问题。它是指数据元素(elements)之间的关系、顺序和逻辑结构,以及相互作用的算法。数据结构通常采用抽象数据类

    2024年02月14日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包