Алгоритм проверки, посещена ли каждая вершина, начиная с начала координат в ориентированном графе acycli c - PullRequest
0 голосов
/ 15 апреля 2020

Имея ориентированный граф без циклов, какие алгоритмы я могу использовать, чтобы проверить, посещается ли каждая вершина, начиная с начальной точки. Например, есть 5 деревьев (от дерева 1 до дерева 5), вы начинаете с дерева 1. Можете ли вы посетить все деревья в ориентированном графе, причем деревья являются вершинами?

Примером теста является дерево номер: 0 содержит:
[1, 2]
номер дерева: 1 содержит:
[2, 3]
номер дерева: 2 содержит:
[3, 4]
Номер дерева: 3 содержит:
[5]
Номер дерева: 4 содержит:
[6]
Номер дерева: 5 содержит:
[6]
Номер дерева: 6 содержит :
[]

void bfs(struct Graph* graph, int startVertex) {

    struct queue* q = createQueue();

    graph->visited[startVertex] = 1;
    enqueue(q, startVertex);

    while(!isEmpty(q)){
        printQueue(q);
        int currentVertex = dequeue(q);
        printf("Visited %d\n", currentVertex);

       struct node* temp = graph->adjLists[currentVertex];

       while(temp) {
            int adjVertex = temp->vertex;

            if(graph->visited[adjVertex] == 0){
                graph->visited[adjVertex] = 1;
                enqueue(q, adjVertex);
            }
            temp = temp->next;
       }
    }
}
...