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