想当年，我只会用邻接矩阵，MLE的感人肺腑啊！
看最短路算法时，很多遍历边的方法我都看不懂。于是专门刷了一下存图……在此做个回顾总结。
部分来源于NOCOW。在此感谢。
邻接矩阵
作为图的一种储存方式，实际上就是一个二维数组。即为记为map[i][j]，map[i][j]为节点i到节点j之间的边的权值，若不存在边，则为-1或其他。
这种储存方式的优势是书写方便，但缺点是非稠密图空间效率不高。相比之下，稍微麻烦点的前向星,邻接表等结构更加快速。
邻接表
邻接表是图的一种链式存储结构，在邻接表中，对图中每个顶点建立一个单链表，n个顶点，就要建n个链表。
第i个单链表中的结点表示依赖于顶点vi的边。单链表中每一个结点称为表结点，应包括三个域邻接点域、链域和数据域。邻接点域，用以存放与vi相邻接的顶点序号；链域用以指向与vi邻接的下一个结点,数据域存储和边或弧有关的的信息。
但是，为什么一定要链表呢？
有vector为什么不用呢？
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
vector<pair<int, int> > MAP[MAX]; //存边 cin >> M; for(int i = 1; i <= M; i++) { int s, e, v; cin >> s >> e >> v; MAP[s].push_back(make_pair(e, v)); } //遍历x的边集,MAP[x][i].first为终点，MAP[x][i].second为边权 for(int i = 0; i < MAP[x].size(); i++){ //do YOLO } |
前向星
前向星构造方法如下：
读入每条边的信息
将边存放在数组中
把数组中的边按照起点顺序排序
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
struct R{ int first,last; }record[MAXN]; struct Edge{ int s,t,w; bool operator <(const Edge &b)const { return this->s<b.s; } }edge[MAXE]; for(i=1;i<=n;++i){ record[i].last=0; // 每个顶点在数组中的起始位置初始化为-1，表示出度为0 record[i].first=-1; } for(i=1;i<=m;++i){ scanf("%d%d%d",&a,&b,&c); edge[i].s=a; edge[i].t=b; edge[i].w=c; record[a].last++;//记录某个节点出发的边有多少条 } sort(edge+1,edge+m+1);//m条边排序 //下面求每个顶点在数组中的起始位置和终止位置 int index=1; while(index<=m){ record[edge[index].s].first=index;//以一个点为出发点的第一条边 record[edge[index].s].last+=record[edge[index].s].first-1; //以一个点为出发点的最后一条边 index=record[ edge[index].s].last+1; } |
链式前向星
嗯，排序，快排，nlogn。
你看看人家存边只要O(n)……（如果你会计数排序的话……也行
那么……链式前向星。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
struct edge{ int e;int v;int next; }; int first[MAXN],head; edge V[MAXN]; cin>>m; while(head++<m){ cin>>b>>e>>l; V[head].e=e;V[head].v=l; if(first[b]!=-1){ V[head].next=first[b]; }else{ V[head].next=head; } first[b]=head; } for(int ed=first[ps];;ed=V[ed].next){ //do YOLO if(ed==V[ed].next)break; } |
还有吗……
十字链表和邻接多重表……在OI中还真没怎么见过
[Dr.Lib]Note:Data Structures – 关于存图 by Liqueur Librazy is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Pingback: [Dr.Lib]Note:Algorithm – SSSP - Dr.Lib - Dr.Librazy