|
|
Posted on 2006-04-01 11:23 Tommy Liang 閱讀(852) 評論(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好像不太對吧，我們只是刪一條邊，你的刪了很多呀
|