|
Posted on 2006-04-01 11:23 Tommy Liang 阅读(826) 评论(1) 编辑 收藏 引用 所属分类: 读书笔记《C++图算法》
SparseMultiGRAPH.h #pragma once struct Edge //边 { int v,w; Edge( int v = -1, int w = -1) : v(v), w(w) { } };
class SparseMultiGRAPH { private: int Vcnt; //节点数 int Ecnt; //边数 bool digraph; //是否有向图 struct node //节点 { int v; //节点值 node* next; //邻接节点 node(int x,node* t) { v = x; next = t; } }; typedef node* link; vector<link> adj; //邻接表 public: SparseMultiGRAPH(int V, bool digraph = false); ~SparseMultiGRAPH(); int V() const; //取节点数 int E() const; //取边数 bool directed() const; //取是否有向图 void insert(Edge e); //插入边 void remove(Edge e); //移除边 bool edge(int v,int w) const; //判断两点间是否存在边
class adjIterator; //iterator friend class adjIterator; };
class SparseMultiGRAPH::adjIterator { const SparseMultiGRAPH &G; int v; link t; public: adjIterator(const SparseMultiGRAPH &G,int v); int beg(); int nxt(); bool end(); }; SparseMultiGRAPH.cpp #include "SparseMultiGRAPH.h"
SparseMultiGRAPH::SparseMultiGRAPH(int V, bool digraph) : adj(V), Vcnt(V), Ecnt(0), digraph(digraph) { adj.assign(V,0); } SparseMultiGRAPH::~SparseMultiGRAPH() { for(int i=0;i < Vcnt; i++) { delete adj[i]; } } int SparseMultiGRAPH::V() const { return Vcnt; } int SparseMultiGRAPH::E() const { return Ecnt; } bool SparseMultiGRAPH::directed() const { return digraph; } void SparseMultiGRAPH::insert(Edge e) { int v = e.v; int w = e.w; adj[v] = new node(w, adj[v]); if ( !digraph) adj[w] = new node(v,adj[w]); Ecnt ++; } void SparseMultiGRAPH::remove(Edge e) { int v = e.v; int w = e.w; adj.erase(adj.begin() + v, adj.begin() + v + 1); int i = v < w ? w-1 : w; adj.erase(adj.begin() + i, adj.begin() + i + 1); } bool SparseMultiGRAPH::edge(int v,int w) const { node * p = adj[v]; while( p != NULL) { if(p->v == w) return true; p = p->next; } return false; }
SparseMultiGRAPH::adjIterator::adjIterator(const SparseMultiGRAPH &G,int v) : G(G), v(v) { t = 0; } int SparseMultiGRAPH::adjIterator::beg() { t = G.adj[v]; return t ? t->v : -1; } int SparseMultiGRAPH::adjIterator::nxt() { if (t) t = t->next; return t ? t->v : -1; } bool SparseMultiGRAPH::adjIterator::end() { return t == 0; } 用法:
#include <tchar.h> #include <windows.h> #include <iostream>
#include "KTimer.h" #include "SparseMultiGRAPH.h"
int main(int argc, char* argv[]) { KTimer timer;
unsigned cpuspeed10 = timer.GetCPUSpeed();
timer.Start(); SparseMultiGRAPH g(5); Edge e1(0,1); Edge e2(1,2); Edge e3(2,3); Edge e4(0,2); Edge e5(1,3);
Edge e6(1,4); Edge e7(2,4); Edge e8(3,4);
g.insert(e1); g.insert(e2); g.insert(e3); g.insert(e4); g.insert(e5); g.insert(e6); g.insert(e7); g.insert(e8); cout << "0到2存在边?" << g.edge(0,2) << endl; cout << "0到3存在边?" << g.edge(0,3) << endl;
SparseMultiGRAPH::adjIterator gitor(g,1); for(int i=gitor.beg(); !gitor.end(); i = gitor.nxt()) cout << i << endl;
unsigned time = timer.Stop();
TCHAR mess[128]; wsprintf(mess,_T("耗时:%d ns"), time * 10000 / cpuspeed10); cout << mess << endl;
return 0; }
Feedback
# re: 邻接表 SparseMultiGRAPH 回复 更多评论
2011-05-16 12:28 by
remove好像不太对吧,我们只是删一条边,你的删了很多呀
|