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 "graph.h"
#include <iostream>

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

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

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

海蓝 · 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还有点眼熟,别的完全不知道了

Leave a Reply

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