Antes de continuar con cómo puede comenzar a codificar problemas de árbol o gráfico, veamos primero las diferencias entre árbol y gráfico.
- El árbol es una forma especial de gráfico, es decir, un gráfico mínimamente conectado y tiene exactamente una ruta entre dos vértices. En un gráfico puede haber más de una ruta entre dos nodos.
- Un árbol es un caso especial de gráficos sin bucles, sin circuitos y sin bucles propios.
- En un árbol hay exactamente un nodo raíz y cada nodo hijo tiene exactamente un padre. No hay un concepto de nodos raíz en un gráfico.
- Hay una cierta relación padre-hijo en un árbol, mientras que este concepto no se cumple en el caso de un gráfico.
- Los algoritmos de recorrido de árbol son recorridos de preorden, postorden , en orden, mientras que el recorrido de gráficos generalmente se realiza mediante DFS (Profund First Search) o BFS (Breadth First Search).
- Las aplicaciones de árbol son básicamente el recorrido de árbol y la búsqueda binaria (Búsqueda binaria. Los gráficos tienen un conjunto de aplicaciones muy general. Muchos problemas se simplifican si los representamos como problemas de gráficos.
Algunas de las aplicaciones gráficas típicas son las siguientes
- Trayectoria más corta.
- Max Flow.
- Detección de ciclos.
- Clasificación topológica.
- Componentes fuertemente conectados.
- Programación de trabajo.
- Coloración gráfica.
- Emparejamiento bipartito, etc.
El primer paso para codificar problemas relacionados con el gráfico o el árbol es comprender cómo puede realmente representarlos como una estructura de datos en el código. Por lo tanto, debe aprender el concepto de matriz de adyacencia y lista de adyacencia. Antes de practicar cualquier problema, sé minucioso con la representación gráfica o de árbol. Entonces, escriba el código solo para construir un árbol o un gráfico desde cero.
- ¿Cuándo debo usar un árbol de sufijos sobre una matriz de sufijos?
- ¿Puede un algoritmo descubrirse a sí mismo?
- Cada vez que intento resolver un problema en CodeChef o SPOJ, aparece el error de límite de tiempo excedido. ¿Qué tengo que hacer? ¿Me faltan algoritmos?
- ¿Por qué es importante almacenar y organizar datos de manera eficiente dentro de estructuras específicas al programar?
- Cómo encontrar proyectos en algoritmo
Cuando digo un árbol, no necesariamente me refiero a un árbol binario y esta suposición puede causar estragos en usted. Para practicar preguntas relacionadas con los árboles, resuelva los problemas disponibles en Archivos de árboles – GeeksforGeeks
En lo que respecta al contenido relacionado con gráficos, primero debe aprender el conjunto básico de algoritmos como
- Algoritmo de Dijkstra, Bellman Ford, Floyd Warshall.
- Profundidad primera búsqueda.
- Amplitud primera búsqueda.
- Algoritmo de Kosaraju.
- Algoritmo de Ford Fulkerson. etc.
Una vez que haya leído este conjunto básico de algoritmos y haya completado sus implementaciones básicas, puede practicar los problemas relacionados con los gráficos disponibles en los siguientes enlaces.
A2 Juez en línea DFS y BFS y problemas de Dijkstra
A2 Problemas de gráficos de jueces en línea
A2 Juez en línea MST, conjuntos disjuntos, problemas de SCC
Feliz codificación !!
