主题:[讨论]无向图算法请教
雨523
[专家分:200] 发布于 2006-12-10 18:47:00
已知某无向图采用邻接表作为存储结构,写一函数,删除图中的某一顶点Vi.
回复列表 (共4个回复)
沙发
雨523 [专家分:200] 发布于 2006-12-10 19:38:00
我也是认为.在这些中,我更喜欢矩阵和邻接表.但是不知道为什么它们挺喜欢邻接多重表
书上说了,我刚才查了一下,邻接多重表在计算某类问题的时候有它的好处
邻接多重表和十字链表长得很象,我不知道它们各适用于什么样的计算问题.
板凳
xieyong456 [专家分:2620] 发布于 2006-12-11 17:13:00
邻接表的核心代码是这里
s->adjvex = j;
s->next = G->vertices[i].firstarc;
G->vertices[i].firstarc = s;
如果是无向图,再多加三行代码就可以,我们就不必拘泥与这些,自己懂了就可以
要删除某一顶点Vi,这个顶点的下标肯定是我们自己手工输入的i
所以我们可以找到这个顶点
p = G->vertices[i].firstarc;
然后对起进行删除,我们会联想到单链表里操作,既然是顶点操作就不会变的很麻烦
q = p;
p = p->next;
free(q);
你认为如何?(有疑问请马上指出一起讨论)
第二个问题,我觉得是,这个不是喜欢不喜欢的问题,应该是对我们要处理的对象而定,书上本有指出,各有利弊,看对象选择合适的东西。。
具体处理是问题,看平时经验而定了
3 楼
雨523 [专家分:200] 发布于 2006-12-11 19:32:00
[quote]邻接表的核心代码是这里
s->adjvex = j;
s->next = G->vertices[i].firstarc;
G->vertices[i].firstarc = s;
如果是无向图,再多加三行代码就可以,我们就不必拘泥与这些,自己懂了就可以
要删除某一顶点Vi,这个顶点的下标肯定是我们自己手工输入的i
所以我们可以找到这个顶点
p = G->vertices[i].firstarc;
然后对起进行删除,我们会联想到单链表里操作,既然是顶点操作就不会变的很麻烦
q = p;
p = p->next;
free(q);
你认为如何?(有疑问请马上指出一起讨论)
第二个问题,我觉得是,这个不是喜欢不喜欢的问题,应该是对我们要处理的对象而定,书上本有指出,各有利弊,看对象选择合适的东西。。
具体处理是问题,看平时经验而定了
[/quote]
[em16]
4 楼
雨523 [专家分:200] 发布于 2006-12-17 14:35:00
顶一下,该算法较好
我来回复