Iniciar sesiónCrear cuenta

Algoritmia - Algoritmos de grafos

Vista:

Algoritmos de grafos

Publicado por stratford (3 intervenciones) el 25/03/2013 18:56:15
Hola, agradecería mucho si me pudieseis decir una solución a estos 3 problemas de algoritmos de grafos.

BFS/DFS
Let G = (V, E) be a directed graph and s &#8712; V a selected vertex. Develop an O(|V | + |E|) algorithm to check whether there is at most one simple path from s to any other vertex u &#8712; V . A path is simple if each node on the path is visited at most once. Use this algorithm to develop a O(|V ||E|) algorithm to check whether there is at most one simple path between any two vertices u and v.

Ordenación Topológica
Let t be a node with out-degree 0 in a dag G = (V, E). Give a O(|V | + |E|) algorithm to determine the number of paths from each vertex u &#8712; V &#8722; {t} to t.

Let s and t be two vertices in a dag G such that the in-degree of s and the out-degree of t is 0. Use the result of the previous exercise to determine, for each edge (u, v) &#8712; E, the number of paths from s to t that run through (u, v) and this in O(|V | + |E|) time.

Componente fuertemente conexos
Let G = (V, E) be a directed graph, develop a O(|V ||E|) algorithm to check whether for any two vertices u, v &#8712; V there is either a path from u to v in G or a path from v to u in G.

Muchas gracias!! :D
Valora esta pregunta
0
Otras secciones de LWP con contenido de Algoritmia
Cursos y Temas de Algoritmia