用c语言写一个删除图的顶点及其相关的边

在 C 语言中，要删除图中的顶点及其相关的边，我们通常会使用邻接表数据结构来表示图，因为这个数据结构便于添加、删除节点以及查找邻居。下面是一个简单的示例，展示如何删除给定顶点及其相关边：

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

typedef struct List {
    Node* head;
} Graph;

// 创建新节点
Node* newNode(int value) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = value;
    node->next = NULL;
    return node;
}

// 添加边到邻接列表
void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = newNode(dest);
    if (graph->head == NULL) {
        graph->head = newNode;
    } else {
        Node* temp = graph->head;
        while (temp->next != NULL && temp->data != src) {
            temp = temp->next;
        }
        if (temp->data == src) {
            temp->next = newNode;
        } else {
            printf("Edge from %d to %d not found.\n", src, dest);
        }
    }
}

// 删除顶点及其相关边
void deleteVertex(Graph* graph, int vertex) {
    Node* temp = graph->head;
    Node* prev = NULL;

    // 遍历找到该顶点
    while (temp != NULL) {
        if (temp->data == vertex) {
            // 如果头节点就是要删除的节点
            if (prev == NULL) {
                graph->head = temp->next;
            } else {
                prev->next = temp->next;
            }

            // 释放当前节点内存
            free(temp);
            break;
        } else {
            prev = temp;
            temp = temp->next;
        }
    }

    // 移除该顶点的出边
    for (temp = graph->head; temp != NULL; temp = temp->next) {
        if (temp->data == vertex || temp->next->data == vertex) {
            // 简化示例，这里仅删除单向边；如果需要双向链表，则需遍历两次
            Node* delNode = temp->next;
            if (delNode != NULL) {
                temp->next = delNode->next;
                free(delNode);
            }
        }
    }
}

// 打印图的邻接列表
void printGraph(Graph* graph) {
    Node* temp = graph->head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

int main() {
    Graph graph;
    graph.head = NULL;

    // 添加边到图中
    addEdge(&graph, 0, 1);
    addEdge(&graph, 0, 2);
    addEdge(&graph, 1, 2);

    // 删除顶点2及其相关边
    deleteVertex(&graph, 2);

    // 打印更新后的图
    printGraph(&graph);

    return 0;
}