¿Cuáles son las mejores fuentes y estrategias para aprender gráficos para una programación competitiva?

Una gráfica es una notación abstracta utilizada para representar la conexión entre pares de objetos. Una gráfica consta de

Vértices : los objetos interconectados en un gráfico se llaman vértices. Los vértices también se conocen como nodos .
Bordes – Los bordes son los enlaces que conectan los vértices.

Hay dos tipos de gráficos:

Gráfico dirigido : en un gráfico dirigido, los bordes tienen dirección, es decir, los bordes van de un vértice a otro.
Gráfico no dirigido : en un gráfico no dirigido, los bordes no tienen dirección.

La teoría de gráficos es un tema extenso que abarca varios subtemas como las estructuras de gráficos, los recorridos de gráficos, los gráficos dirigidos, la ruta más corta en los gráficos, etc.

Para una breve introducción al gráfico, vea este video.

Para el enfoque puramente matemático, el libro de Reinhard Diestel es excelente y tiene un precio asequible, con una vista previa en PDF gratuita disponible del autor.

Otro buen libro es Bondy and Murty “Graph Theory”. La versión más reciente de 2008 se lanzó después de la versión probada en los años 70. Me gusta el enfoque que toma. Haga una pregunta y guíe lentamente al lector hacia la respuesta.

Aquí hay 2 tutoriales que encontrará útiles para aprender los conceptos básicos de la teoría de grafos.

Teoría de gráficos: Parte I: cubre las definiciones básicas de gráficos y el recorrido de gráficos más popular: búsqueda en profundidad (DFS) y búsqueda en primer lugar (BFS)

Teoría de gráficos: Parte II: cubre uno de los algoritmos más importantes de la teoría de gráficos: la ruta más corta. Incluye tanto el algoritmo de Djikstra como el algoritmo de Bellman Ford.

Personalmente, soy un gran fanático del curso de búsqueda de gráficos, rutas más cortas y estructuras de datos de Stanford. TopCoder también tiene un tutorial al respecto, si planea usarlo, es posible que desee cambiar la fuente y aumentar su tamaño para facilitar la lectura. Algorithms, Part II de la Universidad de Princeton, impartido por Robert Sedgewick, es otro curso altamente recomendado para aprender sobre Gráficos. Soy un gran fan de Sedgewick.

Steve Yegge dice que este es un excelente libro sobre algoritmos que usa gráficos de manera extensa. Otro libro gratis, que es bastante bueno.

Enorme lista de algoritmos gráficos e implementaciones en GeeksforGeeks. También lea la respuesta de Pushkar Mishra a ¿Cómo puedo ser bueno en problemas de programación basados en la teoría de gráficos en programación competitiva?

Para problemas en gráficos,

Desafíos algorítmicos de la teoría de gráficos en HackerRank
Problemas de gráficos en GeeksForGeeks
Graficar problemas de algoritmo en HackerEarth
Problemas de la gráfica SPOJ