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

Categories: Code

Yu

Ideals are like the stars: we never reach them, but like the mariners of the sea, we chart our course by them.

7 Comments

海蓝 · August 8, 2013 at 14:53

Google Chrome 27.0.1453.110 Google Chrome 27.0.1453.110 Windows 7 x64 Edition Windows 7 x64 Edition

我就记得 上离散数学的时候 老师讲过图 当年我们班离散考试 就我们三个女生过了 其余全挂了

    yu · August 8, 2013 at 16:04

    Google Chrome 28.0.1500.71 Google Chrome 28.0.1500.71 GNU/Linux x64 GNU/Linux x64

    有向图,无向图,dijkstra,bfs,dfs,prim神马的,其实还是很好玩的

      Leniy · August 9, 2013 at 20:57

      Google Chrome 30.0.1573.2 Google Chrome 30.0.1573.2 Windows 7 Windows 7

      bfs还有点眼熟,别的完全不知道了

Leniy · August 3, 2013 at 14:46

Google Chrome 28.0.1500.95 Google Chrome 28.0.1500.95 Windows 7 Windows 7

XD

    Leniy · August 3, 2013 at 14:47

    Google Chrome 28.0.1500.95 Google Chrome 28.0.1500.95 Windows 7 Windows 7

    我怎么记得chrome已经升级成30版本了呀

      yu · August 3, 2013 at 14:51

      Google Chrome 28.0.1500.71 Google Chrome 28.0.1500.71 GNU/Linux x64 GNU/Linux x64

      大约没有重启吧?
      我看了下我的
      [yu@localhost ~]$ google-chrome –version
      Google Chrome 28.0.1500.71
      表示还没有升级

        Leniy · August 3, 2013 at 14:58

        Google Chrome 28.0.1500.95 Google Chrome 28.0.1500.95 Windows 7 Windows 7

        哦,应该记错了,我另一电脑是测试版,这个是稳定版

Leave a Reply to Leniy Cancel reply

Your email address will not be published. Required fields are marked *