TIP
图在数据结构中比较重要,但是了解的却非常的少,所以现在就重新再学习一遍。图的存储结构用的最多的就是邻接矩阵了,因为简单,只需要开一个二维数组就可以了,但是边的数量非常的少时,空间就比较浪费了,所以为了提高效率,就必须做出改变,下面就来一一说说吧。
# 邻接矩阵
邻接矩阵比较简单,也更加的直观,二维数组的下标就是代表一组坐标,例如a[x][y]
(x,y)就是在这个矩阵中的一个坐标,当a[x][y]=1
时代表这两个点之间有连线,当a[x][y]=0
时代表这两个点之间没有连线,代码如下(默认以无向图为例)
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m;//n代表有几个点,m代表有几条边
cin >> n >> m;
int a[n+1][n+1];//不用数组0下标
fill(a[0],a[0]+(n+1)*(n+1),0);//将数组初始化为0
for(int i=0; i<m; i++){
int x,y;
cin >> x >> y;
a[x][y]=1;
a[y][x]=1;
}
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
cout << a[i][j] << ' ';
}
cout << endl;
}
return 0;
}
# 邻接表
邻接表开始我也不是很理解,不知道如何用代码实现,看着那个图好像是那么回事,无法下手。做这个之前,需要先了解一下,构成邻接表需要哪些东西,一个顶点域,顶点的下标就是代表起始点,还有一部分数据域,里面的内容是从顶点到哪个顶点,还有权值,还有指向下一顶点的指针,代码如下(默认以有向图为例)
#include<bits/stdc++.h>
using namespace std;
const int Max=1e4+3;
typedef struct ENode
{
int to;//终止点
int w;//权值
ENode *next;//指向下一终止点
};
typedef struct VNode
{
int from;//开始点,实际上没用到
ENode *first;//指向终止点
};
VNode adjlist[Max];//初始化顶点
int main()
{
int n,m;//n代表有几个顶点,m代表有几条边
cin >> n >> m;
for(int k=0;k<m;k++){
int i,j,w;//i代表起点,j代表终点,w代表权值
cin >> i >> j >> w;
ENode *p=new ENode;
p->to=j;
p->w=w;
p->next=adjlist[i].first;
adjlist[i].first=p;
}
for(int i=1;i<=n;i++){
for(ENode *k=adjlist[i].first;k!=NULL;k=k->next){
printf("%d %d %d\n",i,k->to,k->w);
}
}
return 0;
}
# vector版本邻接表
如果上面的邻接表不好理解的话,这个vector版本绝对是适合大多数人的,比较好实现。实现原理是这样的,定义一个一维结构体容器,一维数组的下标代表起始点,结构体包括终止点和权值,这样对于同一起始点的就可以放在同一行了,实现起来很容易,代码如下(有向图)
#include<bits/stdc++.h>
using namespace std;
const int Max=1e4+3;
typedef struct ENode
{
int to;
int w;
};
vector<ENode> s[Max];
int main()
{
int n,m;//n代表起点,m代表终点
cin >> n >> m;
for(int i=0;i<n;i++){
s[i].clear();
}
for(int k=0;k<m;k++){
int i,j,w;
cin >> i >> j >> w;
ENode e;
e.to=j;
e.w=w;
s[i].push_back(e);
}
for(int i=1;i<=n;i++){
for(auto it=s[i].begin();it!=s[i].end();it++){
ENode k=*it;
printf("%d %d %d\n",i,k.to,k.w);
}
}
return 0;
}