Имея ориентированный граф без циклов, какие алгоритмы я могу использовать, чтобы проверить, посещается ли каждая вершина, начиная с начальной точки. Например, есть 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;
}
}
}