|
|
Posted on 2006-04-01 11:23 Tommy Liang 阅读(829) 评论(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好像不太对吧，我们只是删一条边，你的删了很多呀
|