Encontrar uma fonte de um gráfico acíclico direcionado em tempo linear

Dado um gráfico acíclico direcionado , um vértice é uma fonte se seu indegree for zero, significando que ele possui apenas arcos de saída.$D = (V,A)$$v \in V$

Existe um algoritmo de tempo linear para encontrar uma fonte em um determinado gráfico acíclico direcionado?

Pergunta de acompanhamento: Alguém em tempo linear pode encontrar todas as fontes?

Como Yuval menciona, a estrutura de dados é importante aqui. Vou tentar dar uma solução para alguns dos tipos de listas de adjacência:

1. Lista de arestas de entrada : para cada nó, há uma lista de vértices a partir dos quais há uma aresta de entrada nesse nó. Você pode simplesmente varrer todos os vértices e verificar se o tamanho da lista de adjacências é$0$ ou não. Um tamanho$0$lista significa que não há arestas recebidas; portanto, o nó é uma fonte ou está desconectado. Assumindo um gráfico conectado, essa varredura de cada vértice fornecerá uma lista de todas as fontes (ou você pode parar depois de encontrar uma) em$O(|V|)$tempo - linear no número de vértices .
2. Lista de arestas de saída : para cada nó, existe uma lista de vértices para os quais existe uma aresta direcionada a partir desse nó. Mantenha uma cadeia de bits com cada bit representando um vértice, inicializado como 0. A partir do primeiro nó, comece a varrer sua lista em busca de vértices nos quais existe uma borda de saída. Como esse nó (vizinho) não pode ser uma fonte, continue definindo o bit correspondente na cadeia de bits. No final, todos os vértices cujos bits correspondentes ainda não estão definidos, são os vértices de origem. Você pode fazer isso no tempo linear no tamanho do gráfico -$O(|V| + |E|)$.
3. Ambas as listas juntas : Para cada vértice, há uma lista mista de vértices que têm uma aresta para ou a partir desse vértice, com algum outro atributo indicando qual dos dois é realmente o caso. A abordagem é semelhante à 2 acima, com a adição de que qualquer borda de entrada exclui imediatamente o vértice atual (e você pode marcar seu conjunto de bits). Diferente do ponto 2, onde você precisa passar por todos os vértices, aqui, você pode encontrar alguma fonte mais cedo. Se você não parar, você terá todas as fontes. Nos dois casos, o tempo é novamente linear no tamanho do gráfico -$O(|V| + |E|)$.
4. Ambas as listas separadamente : basta escolher a lista de arestas recebidas e seguir 1.

Como observação lateral, se a escolha da estrutura de dados estiver em suas mãos, convém analisar o que todas as operações você pretende executar e com que frequência e escolher uma estrutura de dados apropriada.

Edit: Para o caso 1, se você tem um dag em que o número de fontes é muito pequeno em comparação com$|V|$(por exemplo, em uma árvore com uma fonte) e onde a distância média de qualquer vértice a uma fonte é pequena em comparação com$|V|$ e você deseja apenas uma fonte, pode usar um algoritmo mais rápido, em média (embora a pior complexidade assintótica seja a mesma). Selecione qualquer vértice aleatoriamente e vá para qualquer um de seus pais (na lista de arestas recebidas) e depois para seu pai, etc., até chegar a um nó que não tem pai - uma fonte. Esse pequeno ganho de eficiência é para tipos muito limitados de gráficos com um algoritmo um pouco mais complexo.

Vamos considerar uma pergunta mais simples. Suponha que você saiba que seu gráfico é uma árvore. Então você pode encontrar o nó de origem em tempo linear. Basta selecionar um nó aleatório, se é a raiz, então você tem a sua resposta; caso contrário, deve ser filho ou pai e, em seguida, retroceder até chegar à raiz. Isso pode ser feito em$O(|V|-1)$.

Supondo que você tenha um gráfico G = (V, E) fornecido no formato de lista de adjacências. (para ficar claro aqui, a lista contém todas as arestas de saída da fonte). Você pode construir o inverso do gráfico G em tempo linear. Em seguida, você pode percorrer o gráfico inverso e coletar todos os vértices que possuem a lista de adjacências vazia. Esses vértices não têm arestas de saída no gráfico inverso, o que significa que não têm arestas de entrada no gráfico original; portanto, esses são os vértices de origem.

O tempo de execução é linear. Construir o inverso do gráfico leva no máximo O (| V | + | E |). A iteração sobre o inverso do gráfico leva tempo O (| V |).