首页 > 学院 > 开发设计 > 正文

图的两种表示和接口

2019-11-14 09:41:12
字体:
来源:转载
供稿:网友

常读常新

这里多分析了三个点: 1. 两种表示方式在另一个维度的比较; 2. 一种复杂应用场景下的取舍办法; 3. 经典表示方法之外的黑科技。

众所周知,在经典的图论里,图的两种表示方式为: 1. 邻接矩阵; 2. 邻接表。

先回顾一下,图是由结点,以及结点之间的边构成的。结点一般编号为0,1,2,……,然后一条边由<u, v[,w]>来定义,其中的u和v都是某个结点的编号(如果有w的话,表示这条边的权重)。

图还分为有向图和无向图,其实本质上并没区别,可以说一切图都是有向图,而无向图只不过是每条有向边都存在一条反方向的边而已(两个结点可以直接互通,谓之无向,在这里,“方向”表示通行的限制)。

记号声明

E,表示整张图的边(edge)的数量;V,表示整张图的顶点(vertex)的数量;e,表示某个顶点相邻的边的数量。

优缺点分析

先po一张统一的图以便后续分析:

结点为:0, 1, 2边为:<0, 1, 10>, <1, 2, 66>, <2, 0, 55>

这张图很明显是一个三角形。

邻接矩阵

顾名思义,这种方式是用一个N*N的矩阵来表示图,如果存在边

0 10 00 0 6655 0 0优点:可以在常数时间内得到一条边的权重;缺点:占用内存多,特别是对于稀疏图来说;缺点:没法保证在O(e)时间内遍历某个结点的所有边。

稍微解释一下,对于1,因为矩阵可以随机存取元素,所以可以在常数时间内知道两个结点之间是否存在一条边。 对于2,很明显矩阵占用的内存是顶点的数量的平方,对于稀疏图来说,很浪费内存。 对于3,比如想遍历结点1的所有边(在这里只有1条),但没法只访问1次,而是必须得访问V(=3)次,才能得出所有与1相邻的边。

邻接表

用矩阵对于稀疏图来说,太过浪费内存,所以不妨只记录每个结点相邻的结点,比如vector<vector<pair<int, int> > > >就是一个链表的数组。

用链表来表示上面的图便是:

0 -> [<1, 10>]1 -> [<2, 66>]2 -> [<0, 55>]优点:相对省内存,如果E < N*N的话;优点:可以在O(e)时间内遍历某个结点的所有边;缺点:没法在常数时间内获取一条边的权重。

对于1,邻接链表存储的元素数量等于边的数量,对于稀疏图来说,很明显是节省内存的。 对于2,由于某个结点对应的链表就是与它相邻的所有边,自然可以在O(e)时间内遍历完。 对于3,由于是用链表存储的,没法随机访问,所以必须遍历链表来得到具体的某条边的权重。

取舍

普通情况下,只需要按照上面提到的优缺点便可以轻松取舍,比如稠密图就用邻接矩阵啦,稀疏图并且不需要在常数时间内获取一条边的权重的就用邻接表啦……

但是,在这样一种较复杂的情况下,该用什么——

既需要在常数时间内获取一条边的权重,又需要在O(E)时间内遍历某个结点的所有边。

注意,这里不需要省内存了。

回答这个问题之前,可能一个正常人会先问:真的有这样的场景吗

有的,这种需求在图论算法的实现中比比皆是,比如最近重新写Dijkstra算法,首先需要在常数时间内获取某条边的权重(因为需要用来计算最短路径);其次,每次一个结点出队时,我需要遍历它的所有相邻的边,来“疏松”路径。

那该怎么办呢?看上去水火不相容啊?

其实我的解决办法很简单,两种表示法都用,然后各取其长处即可!这样自然没法省内存了,不过时空博弈从来如此。

最后面有具体的实例。

一点点黑科技

其实很容易想到其它的数据结构来表示图,比如用map<pair<int, int>, int>,map的键是结点对<u, v>,map的值是该边的权重。

这样的数据结构可以在log(E)(注意是大写的E)的时间内获取某条边的权重,但是……没法获取某个顶点相邻的边,只能用其它的数据结构来保存,比如vector<vector<int> >保存的是所有边的信息,这里和邻接表唯一不同的地方就是,没有保存权重,因为权重是用上述的map来保存。

把这两者结合起来的好处是,当log(E)普遍远远小于e时,这样做的总体效率会比邻接表好一些~

有没有必要搞这样一个“四不像”出来呢?应该是有的,就是,图比较稠密,且顶点的数量太大以至于没法开一个矩阵来存放时!

或许会有更好的solution也说不定。

取舍的做法举例

举个例子,我为了调用简单,把这两种表示方法都写成了类,先看看是如何调用的:

int main() { int n, e, u, v, w; cin >> n >> e; AdjacencyMatrix am(n); AdjacencyList al(n); while (e--) { cin >> u >> v >> w; am.insertEdge(u, v, w); al.insertEdge(u, v, w); } int s, t; while (cin >> s >> t) { dijkstra(am, al, s, t); } return 0;}

完整的代码请移步:http://paste.Ubuntu.com/23929990/。

然后AdjacencyMatrix和AdjacencyList具体是这样的:

// DirectedGraph.h#ifndef __Directed_Graph_H__#define __Directed_Graph_H__#include <vector>#include <iostream>using namespace std;typedef int weight_t;const weight_t INFINITE = 1e9;class AdjacencyMatrix{public: AdjacencyMatrix(size_t n); int getWeight(size_t u, size_t v) const; void insertEdge(size_t u, size_t v, weight_t w); size_t getNumberOfNode() const;PRivate: vector<vector<weight_t> > data; size_t numberOfNode;};class AdjacencyList{public: AdjacencyList(size_t n); int getWeight(size_t u, size_t v) const; void insertEdge(size_t u, size_t v, weight_t w); const vector<vector<size_t> >& getEdges() const; size_t getNumberOfNode() const;private: size_t numberOfNode; vector<vector<size_t> > edges; vector<vector<weight_t> > weights;};#endif//DirectedGraph.cpp#include "DirectedGraph.h"AdjacencyMatrix::AdjacencyMatrix(size_t n): data(n, vector<weight_t>(n, INFINITE)), numberOfNode(n) {}int AdjacencyMatrix::getWeight(size_t u, size_t v) const { return data[u][v];}void AdjacencyMatrix::insertEdge(size_t u, size_t v, weight_t w) { data[u][v] = w;}size_t AdjacencyMatrix::getNumberOfNode() const { return numberOfNode;}// =====华丽丽的~分隔线======AdjacencyList::AdjacencyList(size_t n): edges(n), weights(n), numberOfNode(n) {}int AdjacencyList::getWeight(size_t u, size_t v) const { for (int i = 0; i < edges[u].size(); ++i) { if (edges[u][i] == v) return weights[u][i]; } return INFINITE;}void AdjacencyList::insertEdge(size_t u, size_t v, weight_t w) { edges[u].push_back(v); weights[u].push_back(w);}const vector<vector<size_t> >& AdjacencyList::getEdges() const { return edges;}size_t AdjacencyList::getNumberOfNode() const { return numberOfNode;}
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表