邻接矩阵以及邻接表

邻接矩阵以及邻接表(彻底搞懂到自己会用)

邻接矩阵:

f[i][j]//表示i到j有没有边,以及是否关联,存入权值

关联矩阵:
n行e列

f[i][j]//若有边,存入1,否则存入0

实例:

1564153348800

→ 当边数很稀疏时(m<<n^2)用相邻矩阵存图太浪费空间(有大量都是0)
→ 如何为更高效地存储图结构?把有值的元素放到一侧 其他的不存了

这就是邻接表的诞生!!!!!

→ 每个顶点创建一个链表 链表的每一项表示该顶点的一条出边/入边 (链表长度=该顶点的出度) 最简单的实现是vector
→ 如上存储结构称为邻接表 空间性能:O(n+m)(基本无浪费) 支持重边

好了,接下来进入正题

以前,我遇见要用到邻接表的图论题,我只有被吊打的份。(根本不会)。。那么,邻接表到底是什么?? 我们用一个struct结构体,内含(next , to),我们再用一个数组head[N].

1564157084301

head[1]=5;//1号节点对应最后一条边
struct edge{int nxt,to;} e[N]; e[i].nxt[5]=10;//nxt表示5的下一条边
to[5]=4;//to表示边能到的节点
int cnt;//cnt用来遍历每条边

(原谅我没把结构体没打全)
储存方式:

struct edge{
	int nxt,to;
} e[M];
int head[N],cnt,vis[N],d[N],t,fa[N];
void add(int x,int y){
	e[++cnt]=(edge){head[x],y};//=  ++cnt; e[cnt].next=head[x],e[cnt].to=y;
	head[x]=cnt;
}

读入以及调用方式:

int n,m;
	cin>>n>>m;
	memset(head,0,sizeof head); cnt=0;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}

绝对正宗!!!

其实,也没那么难,对吧??

原文链接: https://www.cnblogs.com/tushukai/p/11253566.html

欢迎关注

微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍

    邻接矩阵以及邻接表

原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/299814

非原创文章文中已经注明原地址,如有侵权,联系删除

关注公众号【高性能架构探索】,第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处!

(0)
上一篇 2023年2月15日 下午8:54
下一篇 2023年2月15日 下午8:55

相关推荐