c语言邻接表中删除顶点
时间: 2023-12-12 21:03:11 浏览: 170
要删除邻接表中的一个顶点,需要进行以下步骤:
1. 遍历整个邻接表,将所有与该顶点相邻的边都删除。
2. 删除该顶点所在的链表,即将该链表的头指针置为NULL。
3. 将该顶点从顶点数组中删除,即将该顶点对应的节点从数组中移除。
4. 如果需要保持顶点编号的连续性,则需要对顶点数组进行调整,将所有编号大于该顶点的顶点编号都减1。
下面是一个示例代码:
```c
// 删除邻接表中的一个顶点
void delete_vertex(GraphAdjList* G, int v) {
// 删除该顶点相邻的边
ArcNode* p = G->adjList[v].firstArc;
while (p != NULL) {
int w = p->adjVex;
// 删除该边
delete_edge(G, v, w);
p = p->nextArc;
}
// 删除该顶点所在的链表
G->adjList[v].firstArc = NULL;
// 将该顶点从顶点数组中删除
for (int i = v; i < G->numVertexes - 1; i++) {
G->adjList[i] = G->adjList[i+1];
}
G->numVertexes--;
// 调整顶点数组编号
for (int i = 0; i < G->numVertexes; i++) {
p = G->adjList[i].firstArc;
while (p != NULL) {
if (p->adjVex > v) {
p->adjVex--;
}
p = p->nextArc;
}
}
}
```
其中,delete_edge() 函数是删除邻接表中的一条边的函数,可以参考这个函数的实现。
阅读全文