假设带权有向图G采用邻接表存储,假设顶点i,j已存在,设计一个算法删除i到j的边。
时间: 2024-05-20 10:12:32 浏览: 142
有向图的邻接表表示(c/c ++语言)
4星 · 用户满意度95%
删除i到j的边,需要遍历i的邻接表,找到j对应的边,然后将其删除即可。具体的算法步骤如下:
1. 在顶点i的邻接表中查找顶点j对应的边,如果找到,则删除该边;如果没有找到,说明边不存在,直接返回。
2. 删除边的方法是,找到边所在链表中的前一个节点p和当前节点q,然后将p的next指针指向q的next,即可删除q节点。
算法的时间复杂度为O(deg(i)),其中deg(i)表示顶点i的度数,也就是邻接表中与i相连的边的数量。因为需要遍历i的邻接表,找到j对应的边,所以时间复杂度与i的度数有关。
阅读全文