Estructuras de datos son una forma de organizar los datos para que se pueda acceder a ellos de manera más eficiente según la situación. Las estructuras de datos son fundamentales de cualquier lenguaje de programación en torno al cual se construye un programa. Python ayuda a aprender los fundamentos de estas estructuras de datos de una manera más sencilla en comparación con otros lenguajes de programación.

En este artículo, analizaremos las estructuras de datos en el lenguaje de programación Python y cómo se relacionan con algunas estructuras de datos integradas específicas como listas de tuplas, diccionarios, etc., así como algunas estructuras de datos avanzadas como árboles, gráficos, etc.

Liza

Las listas de Python son como las matrices, declaradas en otros lenguajes y que son una colección ordenada de datos. Es muy flexible ya que no es necesario que los elementos de una lista sean del mismo tipo.

La implementación de Python List es similar a Vectors en C++ o ArrayList en JAVA. La operación costosa es insertar o eliminar el elemento desde el principio de la Lista, ya que es necesario desplazar todos los elementos. La inserción y eliminación al final de la lista también puede resultar costosa en el caso de que la memoria preasignada se llene.

Podemos crear una lista en Python como se muestra a continuación.

Ejemplo: creación de una lista de Python

Python3

>

>

[1, 2, 3, 'GFG', 2.3]>

Se puede acceder a los elementos de la lista mediante el índice asignado. En el índice inicial de Python de la lista, la secuencia es 0 y el índice final es (si hay N elementos) N-1.

Ejemplo: operaciones de lista de Python

Python3

>

fecha java a cadena

>

List containing multiple values: ['Geeks', 'For', 'Geeks'] Multi-Dimensional List: [['Geeks', 'For'], ['Geeks']] Accessing element from the list Geeks Geeks Accessing element using negative indexing Geeks Geeks>

Diccionario

diccionario de pitón es como las tablas hash en cualquier otro idioma con la complejidad temporal de O (1). Es una colección desordenada de valores de datos, que se utiliza para almacenar valores de datos como un mapa, que, a diferencia de otros tipos de datos que contienen solo un valor como elemento, el Diccionario contiene el par clave:valor. El valor clave se proporciona en el diccionario para optimizarlo más.

La indexación del Diccionario Python se realiza con la ayuda de claves. Estos son de cualquier tipo hash, es decir, un objeto que nunca puede cambiar, como cadenas, números, tuplas, etc. Podemos crear un diccionario usando llaves ({}) o comprensión del diccionario .

Ejemplo: operaciones del diccionario Python

Python3

>

>

Creating Dictionary: {'Name': 'Geeks', 1: [1, 2, 3, 4]} Accessing a element using key: Geeks Accessing a element using get: [1, 2, 3, 4] {1: 1, 2: 4, 3: 9, 4: 16, 5: 25}>

tupla

Tupla de Python es una colección de objetos de Python muy parecida a una lista, pero las tuplas son de naturaleza inmutable, es decir, los elementos de la tupla no se pueden agregar ni eliminar una vez creados. Al igual que una Lista, una Tupla también puede contener elementos de varios tipos.

En Python, las tuplas se crean colocando una secuencia de valores separados por 'comas' con o sin el uso de paréntesis para agrupar la secuencia de datos.

Nota: También se pueden crear tuplas con un solo elemento, pero es un poco complicado. Tener un elemento entre paréntesis no es suficiente, debe haber una 'coma' al final para convertirlo en una tupla.

Ejemplo: operaciones de tuplas de Python

Python3

>

>

Tuple with the use of String: ('Geeks', 'For') Tuple using List: First element of tuple 1 Last element of tuple 6 Third last element of tuple 4>

Colocar

Conjunto de pitón es una colección desordenada de datos que es mutable y no permite ningún elemento duplicado. Los conjuntos se utilizan básicamente para incluir pruebas de membresía y eliminar entradas duplicadas. La estructura de datos utilizada en esto es Hashing, una técnica popular para realizar inserción, eliminación y recorrido en O(1) en promedio.

Si hay varios valores presentes en la misma posición de índice, entonces el valor se agrega a esa posición de índice para formar una lista vinculada. En CPython Sets se implementan utilizando un diccionario con variables ficticias, donde las claves son los miembros establecidos con mayores optimizaciones para la complejidad del tiempo.

Establecer implementación:

Conjuntos con numerosas operaciones en una sola HashTable:

Ejemplo: operaciones de conjuntos de Python

Python3

>

>

Set with the use of Mixed Values {1, 2, 'Geeks', 4, 6, 'For'} Elements of set: 1 2 Geeks 4 6 For True>

Conjuntos congelados

Los conjuntos congelados en Python son objetos inmutables que solo admiten métodos y operadores que producen un resultado sin afectar el conjunto congelado o conjuntos a los que se aplican. Si bien los elementos de un conjunto se pueden modificar en cualquier momento, los elementos del conjunto congelado permanecen iguales después de la creación.

Si no se pasan parámetros, devuelve un frozenset vacío.

Python3

>

>

Normal Set {'a', 'c', 'b'} Frozen Set frozenset({'g', 'e', 'f'})>

Cadena

Las cadenas de Python son matrices de bytes que representan caracteres Unicode. En términos más simples, una cadena es una matriz inmutable de caracteres. Python no tiene un tipo de datos de carácter, un solo carácter es simplemente una cadena con una longitud de 1.

Nota: Como las cadenas son inmutables, modificar una cadena dará como resultado la creación de una nueva copia.

Ejemplo: operaciones de cadenas de Python

Python3

>

>

Creating String: Welcome to GeeksForGeeks First character of String is: W Last character of String is: s>

matriz de bytes

Python Bytearray proporciona una secuencia mutable de números enteros en el rango 0 <= x < 256.

Ejemplo: operaciones de Python Bytearray

Python3

>

>

Creating Bytearray: bytearray(b'x0cx08x19x02') Accessing Elements: 8 After Modifying: bytearray(b'x0cx03x19x02') After Adding Elements: bytearray(b'x0cx03x19x02x1e')>

Hasta ahora hemos estudiado todas las estructuras de datos que vienen integradas en el núcleo de Python. Ahora profundicemos en Python y veamos el módulo de colecciones que proporciona algunos contenedores que son útiles en muchos casos y brindan más funciones que las funciones definidas anteriormente.

Módulo de Colecciones

Se introdujo el módulo de colección de Python para mejorar la funcionalidad de los tipos de datos integrados. Proporciona varios contenedores, veamos cada uno de ellos en detalle.

Contadores

Un contador es una subclase del diccionario. Se utiliza para mantener el recuento de los elementos en un iterable en forma de diccionario desordenado donde la clave representa el elemento en el iterable y el valor representa el recuento de ese elemento en el iterable. Esto equivale a una bolsa o conjunto múltiple de otros idiomas.

Ejemplo: operaciones de contador de Python

Python3

>

>

Counter({'B': 5, 'A': 3, 'C': 2}) Counter({'B': 5, 'A': 3, 'C': 2}) Counter({'B': 5, 'A': 4, 'C': 2, 1: 1})>

OrdenadoDict

Un OrdenadoDict También es una subclase de diccionario pero, a diferencia de un diccionario, recuerda el orden en que se insertaron las claves.

Ejemplo: operaciones OrderedDict de Python

Python3

>

>

Before deleting: a 1 b 2 c 3 d 4 After deleting: a 1 b 2 d 4 After re-inserting: a 1 b 2 d 4 c 3>

DefaultDict

DefaultDict se utiliza para proporcionar algunos valores predeterminados para la clave que no existe y nunca genera un KeyError. Sus objetos se pueden inicializar utilizando el método DefaultDict() pasando el tipo de datos como argumento.

Nota: default_factory es una función que proporciona el valor predeterminado para el diccionario creado. Si este parámetro está ausente, se genera KeyError.

Ejemplo: operaciones de Python DefaultDict

Python3

>

>

defaultdict(, {1: 2, 2: 3, 3: 1, 4: 2})>

Mapa de cadena

Un ChainMap encapsula muchos diccionarios en una sola unidad y devuelve una lista de diccionarios. Cuando es necesario encontrar una clave, se buscan todos los diccionarios uno por uno hasta encontrar la clave.

Ejemplo: operaciones de ChainMap de Python

Python3

>

>

Producción

ChainMap({'a': 1, 'b': 2}, {'c': 3, 'd': 4}, {'e': 5, 'f': 6}) 1>

KeyError: 'g'>

Tupla con nombre

A Tupla con nombre devuelve un objeto tupla con nombres para cada posición de los que carecen las tuplas ordinarias. Por ejemplo, considere una tupla de nombres de estudiante donde el primer elemento representa fname, el segundo representa lname y el tercer elemento representa la fecha de nacimiento. Supongamos que para llamar a fname en lugar de recordar la posición del índice, puede llamar al elemento usando el argumento fname, entonces será muy fácil acceder al elemento tupla. Esta funcionalidad la proporciona NamedTuple.

Ejemplo: operaciones NamedTuple de Python

Python3

>

>

The Student age using index is : 19 The Student name using keyname is : Nandini>

Deque

Deque (cola de doble terminación) es la lista optimizada para operaciones de agregar y extraer más rápidas desde ambos lados del contenedor. Proporciona una complejidad de tiempo O(1) para operaciones de agregar y extraer en comparación con la lista con una complejidad de tiempo O(n).

Python Deque se implementa utilizando listas doblemente enlazadas, por lo que el rendimiento para acceder aleatoriamente a los elementos es O(n).

Ejemplo: operaciones de deque de Python

Python3

cdr forma completa

>

>

The deque after appending at right is : deque([1, 2, 3, 4]) The deque after appending at left is : deque([6, 1, 2, 3, 4]) The deque after deleting from right is : deque([6, 1, 2, 3]) The deque after deleting from left is : deque([1, 2, 3])>

UsuarioDict

UserDict es un contenedor similar a un diccionario que actúa como un contenedor alrededor de los objetos del diccionario. Este contenedor se utiliza cuando alguien quiere crear su propio diccionario con alguna funcionalidad nueva o modificada.

Ejemplo: UserDict de Python

Python3

>

>

Producción

Original Dictionary {'a': 1, 'b': 2, 'c': 3}>

RuntimeError: Deletion not allowed>

Lista de usuarios

UserList es un contenedor similar a una lista que actúa como un contenedor alrededor de los objetos de la lista. Esto es útil cuando alguien quiere crear su propia lista con alguna funcionalidad modificada o adicional.

Ejemplos: Lista de usuarios de Python

Python3

>

>

Producción

Original List [1, 2, 3, 4] After Insertion [1, 2, 3, 4, 5]>

RuntimeError: Deletion not allowed>

Cadena de usuario

UserString es un contenedor similar a una cadena y, al igual que UserDict y UserList, actúa como un contenedor alrededor de objetos de cadena. Se utiliza cuando alguien quiere crear sus propias cadenas con alguna funcionalidad modificada o adicional.

Ejemplo: cadena de usuario de Python

Python3

>

>

Original String: Geeks String After Appending: Geekss String after Removing: Gkss>

Ahora, después de estudiar todas las estructuras de datos, veamos algunas estructuras de datos avanzadas, como pila, cola, gráfico, lista vinculada, etc., que se pueden usar en el lenguaje Python.

Lista enlazada

Una lista enlazada es una estructura de datos lineal, en la que los elementos no se almacenan en ubicaciones de memoria contiguas. Los elementos de una lista vinculada están vinculados mediante punteros como se muestra en la siguiente imagen:

Una lista vinculada está representada por un puntero al primer nodo de la lista vinculada. El primer nodo se llama cabeza. Si la lista vinculada está vacía, entonces el valor del encabezado es NULL. Cada nodo de una lista consta de al menos dos partes:

• Datos
• Puntero (o referencia) al siguiente nodo

Ejemplo: definición de lista enlazada en Python

Python3

>

>

Creemos una lista enlazada simple con 3 nodos.

Python3

>

>

Recorrido de lista enlazada

En el programa anterior, creamos una lista enlazada simple con tres nodos. Recorramos la lista creada e imprimamos los datos de cada nodo. Para el recorrido, escribamos una función de propósito general printList() que imprima cualquier lista dada.

Python3

>

>

1 2 3>

Pila

A pila es una estructura de datos lineal que almacena elementos en forma de último en entrar/primero en salir (LIFO) o primero en entrar/último en salir (FILO). En la pila, se agrega un nuevo elemento en un extremo y se elimina un elemento solo de ese extremo. Las operaciones de inserción y eliminación a menudo se denominan push y pop.

Las funciones asociadas a la pila son:

vacío() – Devuelve si la pila está vacía – Complejidad de tiempo: O(1) size() – Devuelve el tamaño de la pila – Complejidad de tiempo: O(1) top() – Devuelve una referencia al elemento superior de la pila – Complejidad del tiempo: O(1) push(a) – Inserta el elemento 'a' en la parte superior de la pila – Complejidad del tiempo: O(1) pop() – Elimina el elemento superior de la pila – Complejidad del tiempo: O( 1)

Implementación de la pila de Python

La pila en Python se puede implementar de las siguientes maneras:

• lista
• Colecciones.deque
• cola.LifoQueue

Implementación usando Lista

La lista de estructuras de datos integrada de Python se puede utilizar como pila. En lugar de push(), append() se usa para agregar elementos a la parte superior de la pila mientras pop() elimina el elemento en orden LIFO.

Python3

>

>

Initial stack ['g', 'f', 'g'] Elements popped from stack: g f g Stack after elements are popped: []>

Implementación usando colecciones.deque:

La pila de Python se puede implementar usando la clase deque del módulo de colecciones. Se prefiere Deque a la lista en los casos en los que necesitamos operaciones de agregar y extraer más rápidas desde ambos extremos del contenedor, ya que deque proporciona una complejidad de tiempo O(1) para las operaciones de agregar y extraer en comparación con la lista que proporciona O(n). complejidad del tiempo.

Python3

>

>

Initial stack: deque(['g', 'f', 'g']) Elements popped from stack: g f g Stack after elements are popped: deque([])>

Implementación utilizando el módulo de cola.

El módulo de cola también tiene una cola LIFO, que es básicamente una pila. Los datos se insertan en la cola usando la función put() y get() saca datos de la cola.

Python3

>

>

0 Full: True Size: 3 Elements popped from the stack g f g Empty: True>

Cola

Como pila, el cola es una estructura de datos lineal que almacena elementos según el principio Primero en entrar, primero en salir (FIFO). En una cola, el elemento agregado menos recientemente se elimina primero. Un buen ejemplo de cola es cualquier cola de consumidores de un recurso en la que el consumidor que llegó primero recibe el servicio primero.

Las operaciones asociadas con la cola son:

Enqueue: agrega un elemento a la cola. Si la cola está llena, se dice que es una condición de desbordamiento. Complejidad del tiempo: O(1) Quitar de la cola: elimina un elemento de la cola. Los elementos aparecen en el mismo orden en que se empujan. Si la cola está vacía, entonces se dice que es una condición de desbordamiento insuficiente – Complejidad de tiempo: O(1) Frontal: obtiene el elemento frontal de la cola – Complejidad de tiempo: O(1) Posterior: obtiene el último elemento de la cola – Complejidad de tiempo :O(1)

Implementación de la cola de Python

La cola en Python se puede implementar de las siguientes maneras:

• lista
• colecciones.deque
• cola.cola

Implementación usando lista

En lugar de poner en cola () y sacar de la cola (), se utilizan las funciones append () y pop ().

Python3

>

>

Initial queue ['g', 'f', 'g'] Elements dequeued from queue g f g Queue after removing elements []>

Implementación usando colecciones.deque

Se prefiere Deque a la lista en los casos en los que necesitamos operaciones de agregar y extraer más rápidas desde ambos extremos del contenedor, ya que deque proporciona una complejidad de tiempo O(1) para las operaciones de agregar y extraer en comparación con la lista que proporciona O(n). complejidad del tiempo.

Python3

>

>

Initial queue deque(['g', 'f', 'g']) Elements dequeued from the queue g f g Queue after removing elements deque([])>

Implementación usando queue.Queue

declaración de impresión en java

queue.Queue(maxsize) inicializa una variable a un tamaño máximo de maxsize. Un tamaño máximo de cero '0' significa una cola infinita. Esta cola sigue la regla FIFO.

Python3

>

>

0 Full: True Elements dequeued from the queue g f g Empty: True Empty: False Full: False>

Cola de prioridad

Colas prioritarias son estructuras de datos abstractas donde cada dato/valor en la cola tiene una cierta prioridad. Por ejemplo, en las aerolíneas el equipaje con el título Business o First-class llega antes que el resto. Priority Queue es una extensión de la cola con las siguientes propiedades.

• Un elemento con alta prioridad se retira de la cola antes que un elemento con baja prioridad.
• Si dos elementos tienen la misma prioridad, se sirven según su orden en la cola.

Python3

>

>

12 1 14 7 14 12 7 1>

Cola de montón (o heapq)

módulo heapq en Python proporciona la estructura de datos del montón que se utiliza principalmente para representar una cola de prioridad. La propiedad de esta estructura de datos en Python es que cada vez que se extrae el elemento del montón más pequeño (min-heap). Cada vez que se empujan o sacan elementos, se mantiene la estructura del montón. El elemento heap[0] también devuelve el elemento más pequeño cada vez.

Admite la extracción e inserción del elemento más pequeño en tiempos O (log n).

Python3

>

>

The created heap is : [1, 3, 9, 7, 5] The modified heap after push is : [1, 3, 4, 7, 5, 9] The popped and smallest element is : 1>

Árbol binario

Un árbol es una estructura de datos jerárquica que se parece a la siguiente figura:

 tree ---- j <-- root /  f k /   a h z <-- leaves>

El nodo superior del árbol se llama raíz, mientras que los nodos inferiores o los nodos sin hijos se denominan nodos hoja. Los nodos que están directamente debajo de un nodo se llaman hijos y los nodos que están directamente encima de algo se llaman padres.

Un árbol binario es un árbol cuyos elementos pueden tener casi dos hijos. Dado que cada elemento de un árbol binario puede tener sólo 2 hijos, normalmente los llamamos hijos izquierdo y derecho. Un nodo de árbol binario contiene las siguientes partes.

• Datos
• Puntero al niño izquierdo
• Puntero al niño correcto

Ejemplo: definición de clase de nodo

Python3

>

>

Ahora creemos un árbol con 4 nodos en Python. Supongamos que la estructura del árbol se ve como se muestra a continuación:

 tree ---- 1 <-- root /  2 3 / 4>

Ejemplo: agregar datos al árbol

Python3

>

>

Recorrido del árbol

Los árboles se pueden atravesar. En maneras diferentes. A continuación se detallan las formas generalmente utilizadas para atravesar árboles. Consideremos el siguiente árbol:

 tree ---- 1 <-- root /  2 3 /  4 5>

Primeros recorridos en profundidad:

• En orden (izquierda, raíz, derecha): 4 2 5 1 3
• Reserva (raíz, izquierda, derecha): 1 2 4 5 3
• Orden posterior (izquierda, derecha, raíz): 4 5 2 3 1

Orden del algoritmo (árbol)

• Atraviese el subárbol izquierdo, es decir, llame a Inorder(subárbol izquierdo)
• Visita la raíz.
• Atraviese el subárbol derecho, es decir, llame a Inorder(subárbol derecho)

Reserva de algoritmo (árbol)

• Visita la raíz.
• Atraviese el subárbol izquierdo, es decir, llame a Preorden (subárbol izquierdo)
• Atraviese el subárbol derecho, es decir, llame a Preorder(subárbol derecho)

Algoritmo Giro postal(árbol)

• Atraviese el subárbol izquierdo, es decir, llame a Postorder(subárbol izquierdo)
• Atraviese el subárbol derecho, es decir, llame a Postorder(subárbol derecho)
• Visita la raíz.

Python3

>

>

Preorder traversal of binary tree is 1 2 4 5 3 Inorder traversal of binary tree is 4 2 5 1 3 Postorder traversal of binary tree is 4 5 2 3 1>

Complejidad del tiempo: O (n)

Recorrido de orden de nivel o amplitud primero

recorrido de orden de nivel de un árbol es el recorrido en anchura del árbol. El recorrido de orden de nivel del árbol anterior es 1 2 3 4 5.

Para cada nodo, primero se visita el nodo y luego sus nodos secundarios se colocan en una cola FIFO. A continuación se muestra el algoritmo para el mismo:

• Crear una cola vacía q
• temp_node = raíz /*comenzar desde la raíz*/
• Bucle mientras temp_node no sea NULL
  • imprimir temp_node->datos.
  • Ponga en cola los hijos de temp_node (primero los hijos de la izquierda y luego los de la derecha) en q
  • Quitar de la cola un nodo de q

Python3

>

>

Level Order Traversal of binary tree is - 1 2 3 4 5>

Complejidad del tiempo: O(n)

Grafico

A grafico Es una estructura de datos no lineal que consta de nodos y aristas. A los nodos a veces también se les llama vértices y los bordes son líneas o arcos que conectan dos nodos cualesquiera en el gráfico. Más formalmente, un gráfico se puede definir como un gráfico que consta de un conjunto finito de vértices (o nodos) y un conjunto de aristas que conectan un par de nodos.

En el gráfico anterior, el conjunto de vértices V = {0,1,2,3,4} y el conjunto de aristas E = {01, 12, 23, 34, 04, 14, 13}.

Las dos siguientes son las representaciones de gráficos más utilizadas.

• Matriz de adyacencia
• Lista de adyacencia

Matriz de adyacencia

La matriz de adyacencia es una matriz 2D de tamaño V x V donde V es el número de vértices en un gráfico. Sea la matriz 2D adj [][], una ranura adj [i] [j] = 1 indica que hay un borde desde el vértice i al vértice j. La matriz de adyacencia de un gráfico no dirigido siempre es simétrica. La matriz de adyacencia también se utiliza para representar gráficos ponderados. Si adj[i][j] = w, entonces hay una arista desde el vértice i al vértice j con peso w.

Python3

>

>

Producción

Vértices del gráfico

['a B C D e F']

Bordes del gráfico

[('a', 'c', 20), ('a', 'e', ​​10), ('b', 'c', 30), ('b', 'e', ​​40), ( 'c', 'a', 20), ('c', 'b', 30), ('d', 'e', ​​50), ('e', 'a', 10), ('e ', 'b', 40), ('e', 'd', 50), ('e', 'f', 60), ('f', 'e', ​​60)]

Matriz de adyacencia del gráfico

[[-1, -1, 20, -1, 10, -1], [-1, -1, 30, -1, 40, -1], [20, 30, -1, -1, -1, -1], [-1, -1, -1, -1, 50, -1], [10, 40, -1, 50, -1, 60], [-1, -1, -1, -1, 60, -1]]

Lista de adyacencia

Se utiliza una serie de listas. El tamaño de la matriz es igual al número de vértices. Sea la matriz una matriz []. Una matriz de entrada [i] representa la lista de vértices adyacentes al i-ésimo vértice. Esta representación también se puede utilizar para representar un gráfico ponderado. Los pesos de las aristas se pueden representar como listas de pares. A continuación se muestra la representación de la lista de adyacencia del gráfico anterior.

Python3

>

>

Adjacency list of vertex 0 head ->4 -> 1 Lista de adyacencia de la cabeza del vértice 1 -> 4 -> 3 -> 2 -> 0 Lista de adyacencia de la cabeza del vértice 2 -> 3 -> 1 Lista de adyacencia de la cabeza del vértice 3 -> 4 -> 2 -> 1 Adyacencia lista de vértice 4 cabeza -> 3 -> 1 -> 0>

Recorrido de gráficos

Búsqueda en amplitud o BFS

Recorrido primero en amplitud porque un gráfico es similar al recorrido primero en amplitud de un árbol. El único inconveniente aquí es que, a diferencia de los árboles, los gráficos pueden contener ciclos, por lo que podemos llegar al mismo nodo nuevamente. Para evitar procesar un nodo más de una vez, utilizamos una matriz booleana visitada. Por simplicidad, se supone que todos los vértices son accesibles desde el vértice inicial.

Por ejemplo, en el siguiente gráfico, comenzamos a recorrer desde el vértice 2. Cuando llegamos al vértice 0, buscamos todos los vértices adyacentes. 2 también es un vértice adyacente a 0. Si no marcamos los vértices visitados, entonces 2 se procesará nuevamente y se convertirá en un proceso sin finalización. Un recorrido en amplitud primero del siguiente gráfico es 2, 0, 3, 1.

Python3

>

>

Following is Breadth First Traversal (starting from vertex 2) 2 0 3 1>

Complejidad del tiempo: O (V + E) donde V es el número de vértices del gráfico y E es el número de aristas del gráfico.

Primera búsqueda en profundidad o DFS

Primer recorrido en profundidad porque un gráfico es similar al primer recorrido en profundidad de un árbol. El único inconveniente aquí es que, a diferencia de los árboles, los gráficos pueden contener ciclos y un nodo puede visitarse dos veces. Para evitar procesar un nodo más de una vez, utilice una matriz booleana visitada.

Algoritmo:

• Cree una función recursiva que tome el índice del nodo y una matriz visitada.
• Marque el nodo actual como visitado e imprima el nodo.
• Recorra todos los nodos adyacentes y no marcados y llame a la función recursiva con el índice del nodo adyacente.

Python3

>

>

Following is DFS from (starting from vertex 2) 2 0 1 3>

Complejidad del tiempo: O (V + E), donde V es el número de vértices y E es el número de aristas del gráfico.