Блог

У меня есть график, реализованный с использованием представления списка смежности. Я хочу подсчитать количество ребер, которые указывают на каждую вершину (степень вершины).

Вот график:

 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: %dn", j, incoming[j]); 
    }
    ...
}
 

countIncomingLinks содержит один цикл i , который перебирает индексы для вершин в графе.

Каждая вершина содержит список вершин, к которым она имеет исходящие ребра. Вам нужен другой цикл, который для каждой вершины, пройденной первым циклом, перебирает исходящие ребра этой вершины и для каждого исходящего ребра, которое указывает на целевую вершину, добавляет 1 к количеству.