C++中无向图数据结构

在 C 中，可以使用邻接矩阵或邻接表来表示无向图的数据结构。

1. 邻接矩阵：可以使用二维数组来表示无向图的邻接矩阵。定义一个 N x N 的数组，其中 N 是图中顶点的数量。如果顶点 i 和顶点 j 之间存在边，则将矩阵中索引为 (i, j) 和 (j, i) 的元素设置为 1，否则设置为 0。这种表示方法适用于稠密图，但对于稀疏图可能会浪费很多空间。

示例代码：

#define MAX_VERTICES 100

int adjMatrix[MAX_VERTICES][MAX_VERTICES];

void addEdge(int u, int v) {
    adjMatrix[u][v] = 1;
    adjMatrix[v][u] = 1;
}

void removeEdge(int u, int v) {
    adjMatrix[u][v] = 0;
    adjMatrix[v][u] = 0;}

2. 邻接表：可以使用链表或数组的数组来表示无向图的邻接表。定义一个大小为 N 的数组，每个数组元素是一个链表或动态数组，存储与该顶点相邻的顶点。每个链表或动态数组中的节点表示一条边。

示例代码：

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

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

Node* adjacencyList[MAX_VERTICES];

void addEdge(int u, int v) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = adjacencyList[u];
    adjacencyList[u] = newNode;

    newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = u;
    newNode->next = adjacencyList[v];
    adjacencyList[v] = newNode;
}

void removeEdge(int u, int v) {
    Node* prev;
    Node* curr;

    curr = adjacencyList[u];
    prev = NULL;

    while (curr != NULL && curr->vertex != v) {
        prev = curr;
        curr = curr->next;
    }
    if (curr != NULL) {
        if (prev == NULL) {
            adjacencyList[u] = curr->next;
        } else {
            prev->next = curr->next;
        }
        free(curr);
    }

    curr = adjacencyList[v];
    prev = NULL;

    while (curr != NULL && curr->vertex != u) {
        prev = curr;
        curr = curr->next;
    }
    if (curr != NULL) {
        if (prev == NULL) {
            adjacencyList[v] = curr->next;
        } else {
            prev->next = curr->next;
        }
        free(curr);
    }
}

void printGraph(int numVertices) {
    for (int i = 0; i < numVertices; i++) {
        Node* currNode = adjacencyList[i];
        printf("Adjacency list of vertex %d: ", i);
        while (currNode != NULL) {
            printf("%d -> ", currNode->vertex);
            currNode = currNode->next;
        }
        printf("NULL\n");
    }
}

int main() {
    int numVertices = 4;
  
    for (int i = 0; i < numVertices; i++) {
        adjacencyList[i] = NULL;
    }

    addEdge(0, 1);
    addEdge(0, 2);
    addEdge(1, 3);
    addEdge(2, 3);

    printGraph(numVertices);

    removeEdge(1, 3);

    printGraph(numVertices);

    return 0;
}

以上是在 C 中表示无向图的两种常见数据结构。根据具体需求和图的规模，可以选择适合的数据结构来表示无向图。