专栏文章

图的存储

ddeepshits
个人记录参与者 1已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@min2hin9
此快照首次捕获于
2025/12/01 19:29
3 个月前
此快照最后确认于
2025/12/01 19:29
3 个月前
查看原文
链式前向星
无边权
CPP
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e4+5;
const int MAXM=1e6+5;
struct Edge{
	int to;
	int nxt;
};
Edge ed[MAXM];
int head[MAXN];
int len;
void add_edge(int u,int v){
	len++;
	ed[len].to=v;
	ed[len].nxt=head[u];
	head[u]=len;
} 
int n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
    	int u,v;
    	cin>>u>>v;
    	add_edge(u,v);
    	add_edge(v,u);
	}
	for(int i=1;i<=n;i++){
		cout<<i;
		for(int j=head[i];j!=0;j=ed[j].nxt){
			cout<<"-->"<<ed[j].to<<' ';
		}
		cout<<'\n';
	}
	return 0;
}
有边权
CPP
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e4+5;
const int MAXM=1e6+5;
struct Edge{
	int to;
	int val;
	int nxt;
};
Edge ed[MAXM];
int head[MAXN];
int len;
void add_edge(int u,int v){
	len++;
	ed[len].to=v;
	ed[len].val=w;
	ed[len].nxt=head[u];
	head[u]=len;
} 
int n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
    	int u,v,w;
    	cin>>u>>v>>w;
    	add_edge(u,v,w);
    	add_edge(v,u,w);
	}
	for(int i=1;i<=n;i++){
		cout<<i;
		for(int j=head[i];j!=0;j=ed[j].nxt){
			cout<<"-->"<<ed[j].to<<'('<<ed[j].val<<')'<<' ';
		}
		cout<<'\n';
	}
	return 0;
}
优点：对不会vector的人来说比较友好，时间比邻接矩阵优。
邻接矩阵
有边权
CPP
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e4+5;
const int MAXM=1e6+5;
int g[MAXN][MAXN];
int n,m;
signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
    	int u,v,w;
    	cin>>u>>v>>w;
    	g[u][v]=w;
    	g[v][u]=w;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)
		    cout<<g[i][j]<<' ';
		cout<<'\n';
	}
    return 0; 
}
无边权
CPP
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e4+5;
const int MAXM=1e6+5;
int g[MAXN][MAXN];
int n,m;
signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
    	int u,v;
    	cin>>u>>v;
    	g[u][v]=1;
    	g[v][u]=1;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)
		    cout<<g[i][j]<<' ';
		cout<<'\n';
	}
    return 0; 
}
优点：写的非常快
vector
有边权
CPP
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e4+5;
const int MAXM=1e6+5;
vector<pair<int,int> > g[MAXN];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
    	int u,v,w;
    	cin>>u>>v>>w;
    	g[u].push_back(make_pair(v,w));
    	g[v].push_back(make_pair(u,w));
	}
	for(int i=1;i<=n;i++){
		cout<<i<<':';
		for(auto j:g[i])
		    cout<<j.first<<'('<<j.second<<')'<<' ';
		cout<<'\n';
	}
	return 0;
}
无边权
CPP
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e4+5;
const int MAXM=1e6+5;
vector<int> g[MAXN];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
    	int u,v,w;
    	cin>>u>>v>>w;
    	g[u].push_back(v);
    	g[v].push_back(u);
	}
	for(int i=1;i<=n;i++){
		cout<<i<<':';
		for(auto j:g[i])
		    cout<<j<<' ';
		cout<<'\n';
	}
	return 0;
}
优点：和链式前向星的时间和空间差不多，并且比链式前向星好写。

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...