时间戳

首页 > 解决方案 > 在C中计算邻接表图中每个顶点的入度

c - 在C中计算邻接表图中每个顶点的入度

问题描述

我有一个使用邻接表表示实现的图。我想计算指向每个顶点的边数（顶点的入度）。

这是一个图表：

Vertex 0: 3 -> 2 -> 1 -> 
Vertex 1: 4 -> 
Vertex 2: 6 -> 1 -> 5 -> 4 -> 
Vertex 3: 4 -> 5 -> 6 -> 0 -> 
Vertex 4: 6 -> 2 -> 1 -> 
Vertex 5: 0 -> 3 -> 2 -> 6 -> 4 -> 1 -> 
Vertex 6: 0 -> 3 -> 5 -> 2 -> 4 -> 1 ->

我创建的代码没有正确计算链接数并输出以下内容：

Vertex 0: 2
Vertex 1: 0
Vertex 2: 0
Vertex 3: 1
Vertex 4: 2
Vertex 5: 0
Vertex 6: 2

而此示例的链接数应如下所示：

Vertex 0: 3
Vertex 1: 5
Vertex 2: 4
Vertex 3: 3
Vertex 4: 5
Vertex 5: 3
Vertex 6: 4

我想我可能错过了代码中到下一个节点的切换？我怎样才能解决这个问题？

图结构：

typedef struct graph {
    int numberV;
    int numberE;
    struct vertex **adjList;
} GraphT; 

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

计数代码：

int countIncomingLinks(GraphT *graph, int vertex) {
    int count = 0;
    GraphT *current = graph;

    for (int i = 0; i < graph->numberV; i++) {
        if (current->adjList[i]->vertex == vertex) {
            count++; 
        }
        // current = current->adjList[i]->next; 
    }
    return count;
}

int main() {
    ...
    int incoming[vertices]; 

    for (int j = 0; j < vertices; j++) {
        incoming[j] = countIncomingLinks(graph, j); 
    }

    for (int j = 0; j < vertices; j++) {
        printf("Vertex %d: %d\n", j, incoming[j]); 
    }
    ...
}

标签： c

解决方案

countIncomingLinks包含一个循环遍历i图中顶点的索引。

每个顶点包含一个顶点列表，它具有出边。您需要另一个循环，对于第一个循环迭代的每个顶点，迭代该顶点的出边，并且对于指向目标顶点的每个出边，将计数加 1。

推荐阅读