图论建图
图论建图无外乎邻接表建图和链式前向星建图,不要问我是怎么知道的,要是你的学校逼你打图论位的话你就知道了。
1.邻接表建图：
直接开一个N*N的矩阵如果i,j相连则将二维矩阵赋值，否则则为INF。
虽然简单直观但是遍历效率过低， “并且不能存储重边”， 准确的说是不能覆盖重边,应该说这是邻接表建图和链式前向星的弊病所在。
遇到点较稀疏的图时空间利用率过低，时间复杂度为O(N*N)
#include<iostream>
#include<algorithm>
#include<vector>
#define maxn 0x3f3f3f3f
using namespace std;
int N,M;
struct node{
int y,w=maxn;//初始化,没有连接的边默认为maxn
node(int y1,int w1){y=y1;w=w1;}//构造函数
};
vector<node>G[105];
int main(){
int i,j,x,y,z;
cin>>N>>M; //构图
while(scanf("%d%d%d",&x,&y,&z)!=EOF){
G[x].push_back((node){y,z});
}
for(int i=1;i<=N;i++)
for(int j=0;j<G[i].size();j++)
printf("%d %d %d\n",i,G[i][j].y,G[i][j].w);
return 0;
}vector + pair ,如果会用pair的话就不用建结构体了,美滋滋..
typedef pair<int,int> pii;
vector<pii>G[maxn];
//vector<pair<int,int> > G[maxn];
//加边:
G[u].push_back(make_pair(v,w));
//遍历从p点出发的边
for(int i=0;i<G[p].size();i++){
int v=G[p][i].first;
int w=G[p][i].second;
}2.链式前向星
1.结构
edge存边，edge[i]表示第i条边
head[i]存以i为起点的第一条边(在edge中的下标)
struct EDGE{
int next=0; //下一条边的存储下标(默认0)
int to; //这条边的终点
int w; //权值
};
EDGE edge[500010];3.增边
若以点i为起点的边新增了一条，在edge中的下标为j.
那么edge[j].next=head[i];然后head[i]=j.
即每次新加的边作为第一条边，最后倒序遍历
void Add(int u, int v, int w) { //起点u, 终点v, 权值w
//cnt为边的计数，从1开始计
edge[++cnt].next = head[u];
edge[cnt].w = w;
edge[cnt].to = v;
head[u] = cnt; //第一条边为当前边
}4. 遍历
遍历以st为起点的边
for(int i=head[st]; i!=0; i=edge[i].next)i开始为第一条边，每次指向下一条(以0为结束标志) （若下标从0开始，next应初始化-1）
#include <iostream>
using namespace std;
#define MAXM 500010
#define MAXN 10010
struct EDGE{
int next; //下一条边的存储下标
nt to; //这条边的终点
int w; //权值
};
EDGE edge[MAXM];
int n, m, cnt;
int head[MAXN]; //head[i]表示以i为起点的第一条边
void Add(int u, int v, int w) { //起点u, 终点v, 权值w
edge[++cnt].next = head[u];
edge[cnt].w = w;
edge[cnt].to = v;
head[u] = cnt; //第一条边为当前边
}
void Print() {
int st;
cout << "Begin with[Please Input]: \n";
cin >> st;
for(int i=head[st]; i!=0; i=edge[i].next) {//i开始为第一条边，每次指向下一条(以0为结束标志)若下标从0开始，next应初始化-1
cout << "Start: " << st << endl;
cout << "End: " << edge[i].to << endl;
cout << "W: " << edge[i].w << endl << endl;
}
}
int main() {
int s, t, w;
cin >> n >> m;
for(int i=1; i<=m; i++) {
cin >> s >> t >> w;
Add(s, t, w);
}
Print();
return 0;
}我知道在座的有很多图论大佬,但我想说,不喜勿喷,谢谢大家的关爱
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2018-12-23，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录