c语言编写假设带权有向图采用邻接表存储,顶点i,j已存在,设计一个算法删除一条给定的边<i,j>。
时间: 2023-01-28 15:45:10 浏览: 263
邻接表存储的有向图的基本操作(C语言实现)
在邻接表存储的带权有向图中,我们可以使用如下算法来删除给定的边<i,j>:
1. 定义一个指针p,初始化为顶点i的出边链表的头结点。
2. 使用循环遍历顶点i的出边链表,如果p指向的边的终点是j,则执行删除操作。
3. 在删除边<i,j>时,可以将p指向的边从顶点i的出边链表中删除,并释放该边占用的内存。
4. 如果在遍历过程中没有找到边<i,j>,则可以输出提示信息,表示该边不存在。
算法的时间复杂度为O(n),其中n为顶点数。
示例代码:
```
void deleteEdge(Vertex *vertices, int i, int j)
{
Edge *p = vertices[i].firstEdge;
Edge *q = NULL;
while (p != NULL && p->adjvex != j) // 遍历顶点i的出边链表
{
q = p;
p = p->next;
}
if (p == NULL) // 边<i,j>不存在
{
printf("The edge <%d,%d> does not exist.\n", i, j);
return;
}
if (q == NULL) // 删除的边为顶点i的出边链表的第一条边
{
vertices[i].firstEdge = p->next;
}
else
{
q->next = p->next;
}
free(p); // 释放边<i,j>占用的内存
}
```
阅读全文