图论:如何构建静态临接表。
(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)
{
}
遍历某个点出发的边:
int id = v[i];
while(id != -1)
{
}
另外,如果insert函数这样写:
void insert(int from, int to, int
va)//多了一个from元素,可要可不要,根据题目需要
{
}
这样的话,找一条边的反向边就十分容易了:
e中相邻的两条边:第一条是偶数,第二条是奇数,互为反向。
则任取一条边i号,则i ^ 1就是它的反向边位置,很巧妙。