Saltar al contenido ForoHackers

Graph theory: start here

Teoría de grafos
#907 · Ophuscado · · 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

Inicia sesión o únete para responder.