做个图结构

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 <typename T>
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 <typename T>
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<T> > g;
};

然后测试代码是这样子的

#include <iostream>

#include "graph.h"

using namespace graphns;
using namespace std;

int main() {
  Graph<int> 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什么的,因为时间限制,还没有加上,只能回头再搞了