数据结构无向图求邻接表

无向图的邻接表可以用一个数组来表示，数组中每个元素对应一个顶点，每个元素的值是一个链表，链表中存储该顶点所连接的所有边的信息。具体实现可以参考以下代码：

typedef struct EdgeNode{ // 边表结点
    int adjvex; // 邻接点在顶点表中的下标
    int weight; // 权值
    struct EdgeNode* next; // 指向下一个邻接点的指针
}EdgeNode;

typedef struct VertexNode{ // 顶点表结点
    char data; // 顶点信息
    EdgeNode* firstedge; // 指向第一个邻接点的指针
}VertexNode, AdjList[MaxVertexNum];

typedef struct{ // 图
    AdjList adjList; // 邻接表
    int numVertexes, numEdges; // 顶点数和边数
}GraphAdjList;

其中，`MaxVertexNum`为顶点的最大数量。在建立邻接表时，需要遍历所有的边，将每条边的信息存储到对应的链表中。求某个顶点的邻接点时，只需要遍历该顶点对应的链表即可。

相关问题

数据结构邻接表创建无向图

邻接表是一种常见的图的表示方法，它通过链表的方式存储每个节点的邻居节点。在创建无向图的邻接表时，我们需要遍历每个节点，对于每个节点，我们需要创建一个链表来存储它的邻居节点。具体步骤如下：

1. 创建一个大小为n的链表数组，其中n为节点的数量。
2. 遍历每个节点，对于每个节点i，创建一个链表，用于存储它的邻居节点。
3. 对于每个节点i，遍历它的所有邻居节点j，将j加入到i的链表中。
4. 重复步骤3，直到遍历完所有节点。

下面是一个示例代码，用于创建一个无向图的邻接表：

// 定义节点结构体
struct Node {
    int val;
    Node* next;
    Node(int v) : val(v), next(nullptr) {}
};

// 创建邻接表
vector<Node*> createGraph(vector<vector<int>>& edges, int n) {
    vector<Node*> graph(n, nullptr);
    for (auto& edge : edges) {
        int u = edge[0], v = edge[1];
        // 添加u的邻居节点v
        Node* node = new Node(v);
        node->next = graph[u];
        graph[u] = node;
        // 添加v的邻居节点u
        node = new Node(u);
        node->next = graph[v];
        graph[v] = node;
    }
    return graph;
}

C数据结构图的邻接表求度

为了求出图的邻接表中每个顶点的度，我们需要遍历整个邻接表，对于每个顶点，统计其对应链表中的元素个数即可。具体实现方法如下：

// 定义邻接表中的链表结构体
typedef struct AdjListNode {
    int dest;
    struct AdjListNode* next;
} AdjListNode;

// 定义邻接表结构体
typedef struct Graph {
    int V; // 顶点数量
    AdjListNode** array; // 邻接表数组
} Graph;

// 创建一个新的邻接表节点
AdjListNode* newAdjListNode(int dest) {
    AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

// 创建一个邻接表
Graph* createGraph(int V) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->V = V;
    graph->array = (AdjListNode**)malloc(V * sizeof(AdjListNode*));
    for (int i = 0; i < V; ++i) {
        graph->array[i] = NULL;
    }
    return graph;
}

// 添加一条边到无向图中
void addEdge(Graph* graph, int src, int dest) {
    // 添加一条从源节点到目标节点的边
    AdjListNode* newNode = newAdjListNode(dest);
    newNode->next = graph->array[src];
    graph->array[src] = newNode;

    // 添加一条从目标节点到源节点的边
    newNode = newAdjListNode(src);
    newNode->next = graph->array[dest];
    graph->array[dest] = newNode;
}

// 求图中每个顶点的度
void printDegrees(Graph* graph) {
    for (int i = 0; i < graph->V; ++i) {
        int degree = 0;
        AdjListNode* node = graph->array[i];
        while (node) {
            degree++;
            node = node->next;
        }
        printf("Vertex %d has degree %d\n", i, degree);
    }
}