Skip to the content ForoHackers
Log inJoin

Graph theory: start here

Graph theory
#3413 · · Quote · Report

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

You are not logged in, so this goes up anonymously: no account, no name and no address is stored with it, and it may carry no link and no image. Log in or join to post under your name. Our web server's logs keep the address and time of every request for up to 14 days; to keep yours out of them, use Tor. To reach the staff in confidence, use the drop. Sign as a returning source (a key kept only in this browser)

Sending takes a few seconds here: your browser first works out a proof of work against spam.

Reply