liveBook · Manning

Graph

As explained in The Coder Cafe

A graph is a data structure representing objects as vertices and relationships between them as edges.

A graph is a data structure for modeling relationships rather than sequences. It contains vertices, also called nodes, connected by edges, also called links. Graphs support practical models of social networks, maps, computer networks, and biological relationships. section 1.0 section 1.3

Classify a graph by the properties that determine which operations and algorithms apply:

  • Directed edges point from one vertex to another; undirected edges represent two-way relationships. section 1.3
  • Cyclic graphs contain a route that returns to its starting vertex; acyclic graphs contain no cycles. section 1.3
  • Weighted edges carry values such as travel time; unweighted edges treat every connection equally. section 1.3
  • Connected graphs provide a path between every vertex pair; disconnected graphs contain unreachable portions. section 1.3

Represent a graph with an adjacency matrix or adjacency list. A matrix stores whether each vertex pair has an edge, giving O(1) edge lookup but O(v²) space. A list stores each vertex’s neighboring edges, using O(v + e) space and O(d) edge lookup, where d is the vertex degree. section 1.3

Inspect the visual graph example alongside its in-memory representation. section 1.3

Algorithms that exploit graph properties

Use breadth-first search to find shortest paths in unweighted graphs, Floyd–Warshall to find shortest paths between all pairs in weighted graphs, and topological sort to order vertices in a directed acyclic graph. These algorithms depend on graph characteristics rather than treating them as incidental labels. section 1.4

How The Coder Cafe covers it

How deep it goes
Defines graph characteristics and representation complexities, then briefly names algorithms without developing their full implementations.
Examples
Uses Twitter follows, Facebook friendships, travel times, machine networks, social networks, maps, and biological relationships as examples.
What you can do after
Evaluate graph characteristics and representation costs before selecting graph algorithms for a problem.
How it connects
Connects vertices and edges with adjacency matrices, adjacency lists, breadth-first search, Floyd–Warshall, and topological sort.

Also explained in

Compare how 25 books explain graph →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of The Coder Cafe. The section links point to the parts of the book it draws on.