加载中…
个人资料
  • 博客等级:
  • 博客积分:
  • 博客访问:
  • 关注人气:
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
正文 字体大小:

图论:如何构建静态临接表。

(2010-07-21 12:35:55)
标签:

临接表

it

分类: 图论

开一个静态的边表e,存终点,权值和下一个边的ID
struct edge{int to, value, next;} e[size]
开一个点表,一维的int数组v,大小是点数。
v[i]表示从点i出发的第一条边在e表中的位置。
开始时,v都赋值-1,表示没有边。

插入边:cnt是e表中的下一个可用的位置(顺寻增长)
void insert(int from, int to, int va)
{
    e[cnt].to = to; e[cnt].value = va;
    e[cnt].next = v[from];//每次都插入到最前面
    v[from] = cnt++;
}

遍历某个点出发的边:
int id = v[i];
while(id != -1)
{
    //e[id]就是边
    id = e[id].next;
}
另外,如果insert函数这样写:
void insert(int from, int to, int va)//多了一个from元素,可要可不要,根据题目需要
{
    e[cnt].from = from, e[cnt].to = to; e[cnt].val = va;
    e[cnt].next = v[from];v[from] = cnt++;
    e[cnt].from = to, e[cnt].to = from; e[cnt].val = 反向边你需要的值; //同时插入相邻的反向边
    e[cnt].next = v[to];v[to] = cnt++;
}
这样的话,找一条边的反向边就十分容易了:
e中相邻的两条边:第一条是偶数,第二条是奇数,互为反向。
则任取一条边i号,则i ^ 1就是它的反向边位置,很巧妙。

0

阅读 收藏 喜欢 打印举报/Report
  

新浪BLOG意见反馈留言板 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

新浪公司 版权所有