tommy

It's hard to tell the world we live in is either a reality or a dream
posts - 52, comments - 17, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

邻接表 SparseMultiGRAPH

Posted on 2006-04-01 11:23 Tommy Liang 阅读(808) 评论(1)  编辑 收藏 引用 所属分类: 读书笔记《C++图算法》
SparseMultiGRAPH.h
#pragma once
struct Edge        //
{
    
int v,w;
    Edge( 
int v = -1int 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->== 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 windward
remove好像不太对吧,我们只是删一条边,你的删了很多呀

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理