做个图结构

STL库提供了很多很好用的容器,但是没有图.但实际上,我们是常常要用到图的. 前几天居然做梦用写了个图,为了响应心的呼唤,所以写了个带有一些基本功能的图,以后有需求再扩充. 图使用vector作为容器,存放采用邻接表的格式.而图的内容采用模板,这样可以自定义一些奇怪的类型放到里面. 这样,可以给图的每个节点定义一个Node,Node包括位置(这儿写死了是一个二维的int类型的坐标)和一个存放数据的使用模板的data.

然后数据结构的定义大概就是这样子的:

class Position {
public:
int posX;
int posY;
bool operator==(const Position &t) const {
return ((posX == t.posX) && (posY == t.posY));
}
};

template
class Node {
public:
Node(Position p) { pos = p; }
Position pos;
T val;
bool operator==(const Node &t) const { return (pos == t.pos); }
};

因为是使用了模板,所以为了避免麻烦,只能把所有东西都放在一个头文件. 一个图应该有基本功能是增删改查(扶额..),所以graph的主class定义就是这样了:

template
class Graph {
public:
Graph();
virtual ~Graph();
void clear();

bool set(Position pos, T val);
bool set(int posX, int posY, T val);
bool add(Position pos, T val);
bool add(int posX, int posY, T val);
bool contains(Position pos);
bool contains(int posX, int posY);
bool remove(Position pos);
bool remove(int posX, int posY);
bool get(Position pos, T &val);
bool get(int posX, int posY, T &val);

private:
vector<Node > g;
};

然后测试代码是这样子的

#include

#include "graph.h"

using namespace graphns;
using namespace std;

int main() {
Graph g;
g.set(1, 1, 2);
g.set(1, 3, 4);

bool st;
int val = 9;
st = g.get(1, 1, val);
cout << "1,1 : " << (st ? val : -1) << endl;
cout << "1,1 : " << (g.contains(1, 1) ? "contains " : " not contain") << endl;
st = g.get(1, 3, val);
cout << "1,3 : " << (st ? val : -1) << endl;
g.remove(1, 3);
st = g.get(1, 3, val);
cout << "1,3 : " << (st ? val : -1) << endl;
st = g.get(2, 4, val);
cout << "2,4 : " << (st ? val : -1) << endl;
return 0;
}

编译运行得到结果如下:

1,1 : 2
1,1 : contains
1,3 : 4
1,3 : -1
2,4 : -1

最后,我尝试了下节点很多的图,感觉这东西效率没有我想象中的高…回头再改进下. 此外,我很喜欢的BFS,DFS什么的,因为时间限制,还没有加上,只能回头再搞了