Saltar al contenido ForoHackers

Graph theory: start here

Teoría de grafos
#3413 · · Citar · Denunciar

A graph is a set of vertices joined by edges, and almost anything with connections can be modelled as one: roads, networks, dependencies, friendships, molecules. Graph theory studies their structure and the algorithms on them. A well-chosen graph often turns a messy question into a standard problem with a known solution.

Key concepts

  • Representations: adjacency lists suit sparse graphs, adjacency matrices dense ones.
  • Traversal: breadth-first search finds fewest-edge paths; depth-first search gives ordering, cycles and components.
  • Shortest paths: Dijkstra's algorithm for non-negative weights, Bellman-Ford when weights can be negative.
  • Spanning trees: Kruskal's and Prim's algorithms connect all vertices at minimum total weight.
  • Flows and matchings: maximum flow equals minimum cut; matching pairs vertices without sharing.

Vocabulary

  • Directed and undirected: whether edges have a direction.
  • DAG: directed acyclic graph, the shape of dependencies, which can be topologically sorted.
  • Connected component: a maximal set of vertices all reachable from each other.
  • Planar graph: one that can be drawn with no crossing edges.

What to study, in order

  1. Build a graph class with adjacency lists and read a graph from a file.
  2. Implement BFS and DFS and use them for connected components and cycle detection.
  3. Implement Dijkstra with a priority queue and check it against a brute-force search.
  4. Add topological sort, minimum spanning tree and strongly connected components.
  5. Model a real problem as a flow or a matching and solve it.

Related tags

#algorithms #combinatorics #discrete-math #data-structures #knowledge-graphs

No has iniciado sesión, así que esto se publica como anónimo: no se guarda con ello ninguna cuenta, nombre ni dirección, y no puede llevar enlaces ni imágenes. Inicia sesión o únete para publicar con tu nombre. Los registros de nuestro servidor web guardan la dirección y la hora de cada petición hasta 14 días; para que la tuya no quede en ellos, usa Tor. Para escribir al equipo de forma confidencial, usa el buzón. Firmar como fuente habitual (una clave guardada solo en este navegador)

Enviar tarda unos segundos aquí: tu navegador resuelve antes una prueba de trabajo contra el spam.

Responder