Considere un gráfico dirigido dado a continuación, DFS del gráfico a continuación es 1 2 4 6 3 5 7 8. En el diagrama a continuación, si se aplica DFS en este gráfico, se obtiene un árbol que se conecta mediante bordes verdes.
Tree Edge : Es un borde que está presente en el árbol obtenido después de aplicar DFS en el gráfico. Todos los bordes verdes son bordes de árboles.
Borde delantero : es un borde (u, v) tal que v es descendiente pero no forma parte del árbol DFS. El borde del 1 al 8 es un borde delantero.
Borde posterior : es un borde (u, v) tal que v es el ancestro del Node u pero no forma parte del árbol DFS. El borde de 6 a 2 es un borde posterior. La presencia del borde posterior indica un ciclo en el gráfico dirigido .
Cross Edge : es un borde que conecta dos Nodes de tal manera que no tienen ningún antepasado y una relación descendiente entre ellos. El borde del Node 5 al 4 es un borde cruzado.
Complejidad del tiempo (DFS)
Dado que se visitan todos los Nodes y vértices, la complejidad de tiempo promedio para DFS en un gráfico es O(V + E), donde V es el número de vértices y E es el número de aristas. En el caso de DFS en un árbol, la complejidad temporal es O(V), donde V es el número de Nodes.
Algoritmo (DFS)
Elija cualquier Node. Si no está visitado, márquelo como visitado y recurra a todos sus Nodes adyacentes.
Repita hasta que se visiten todos los Nodes o se encuentre el Node que desea buscar.
Ejemplo:
Implemente DFS usando una lista de adyacencia, tome un gráfico dirigido de tamaño n = 10 y seleccione aleatoriamente un número de bordes en el gráfico que varía de 9 a 45. Identifique cada borde como borde delantero, borde de árbol, borde trasero y borde cruzado.
Python3
# code
import random
class Graph:
# instance variables
def __init__(self, v):
# v is the number of nodes/vertices
self.time = 0
self.traversal_array = []
self.v = v
# e is the number of edge (randomly chosen between 9 to 45)
self.e = random.randint(9, 45)
# adj. list for graph
self.graph_list = [[] for _ in range(v)]
# adj. matrix for graph
self.graph_matrix = [[0 for _ in range(v)] for _ in range(v)]
# function to create random graph
def create_random_graph(self):
# add edges upto e
for i in range(self.e):
# choose src and dest of each edge randomly
src = random.randrange(0, self.v)
dest = random.randrange(0, self.v)
# re-choose if src and dest are same or src and dest already has an edge
while src == dest and self.graph_matrix[src][dest] == 1:
src = random.randrange(0, self.v)
dest = random.randrange(0, self.v)
# add the edge to graph
self.graph_list[src].append(dest)
self.graph_matrix[src][dest] = 1
# function to print adj list
def print_graph_list(self):
print("Adjacency List Representation:")
for i in range(self.v):
print(i, "-->", *self.graph_list[i])
print()
# function to print adj matrix
def print_graph_matrix(self):
print("Adjacency Matrix Representation:")
for i in self.graph_matrix:
print(i)
print()
# function the get number of edges
def number_of_edges(self):
return self.e
# function for dfs
def dfs(self):
self.visited = [False]*self.v
self.start_time = [0]*self.v
self.end_time = [0]*self.v
for node in range(self.v):
if not self.visited[node]:
self.traverse_dfs(node)
print()
print("DFS Traversal: ", self.traversal_array)
print()
def traverse_dfs(self, node):
# mark the node visited
self.visited[node] = True
# add the node to traversal
self.traversal_array.append(node)
# get the starting time
self.start_time[node] = self.time
# increment the time by 1
self.time += 1
# traverse through the neighbours
for neighbour in self.graph_list[node]:
# if a node is not visited
if not self.visited[neighbour]:
# marks the edge as tree edge
print('Tree Edge:', str(node)+'-->'+str(neighbour))
# dfs from that node
self.traverse_dfs(neighbour)
else:
# when the parent node is traversed after the neighbour node
if self.start_time[node] > self.start_time[neighbour] and self.end_time[node] < self.end_time[neighbour]:
print('Back Edge:', str(node)+'-->'+str(neighbour))
# when the neighbour node is a descendant but not a part of tree
elif self.start_time[node] < self.start_time[neighbour] and self.end_time[node] > self.end_time[neighbour]:
print('Forward Edge:', str(node)+'-->'+str(neighbour))
# when parent and neighbour node do not have any ancestor and a descendant relationship between them
elif self.start_time[node] > self.start_time[neighbour] and self.end_time[node] > self.end_time[neighbour]:
print('Cross Edge:', str(node)+'-->'+str(neighbour))
self.end_time[node] = self.time
self.time += 1
if __name__ == "__main__":
n = 10
g = Graph(n)
g.create_random_graph()
g.print_graph_list()
g.print_graph_matrix()
g.dfs()
PRODUCCIÓN:
