Connected graph

As explained in Advanced Algorithms and Data Structures

A connected graph is a graph in which every pair of vertices is joined by a sequence of edges.

A connected graph lets you travel between every pair of vertices along a sequence of edges. Equivalently, every vertex has a path to every other vertex. section 14.2.2

Use these properties to distinguish connected graphs from related structures:

• A connected graph with |V| vertices must contain at least |V|-1 edges. section 14.2.2 section 14.1.1
• A tree is a simple, undirected, connected, and acyclic graph, so connectivity is one of its defining restrictions. section 14.2
• For directed graphs, strong connectivity is the more precise related notion: every vertex must be reachable from every other vertex. section 14.2.2
• Choose adjacency lists for sparse connected graphs and adjacency matrices when density makes matrix operations more practical. section 14.1.1

Connectivity as a planarity prerequisite

A simple connected graph with at least three vertices can be planar only if |E| ≤ 3|V| - 6. Checking this bound takes O(|V|+|E|); violating it immediately rules out planarity. section 15.2.2

Figure 14.5 Connected graphs ((A), (B)) versus disconnected graphs ((C), (D))

Compare connected and disconnected undirected graph shapes to make the path-between-vertices requirement concrete. section 14.2.2

How Advanced Algorithms and Data Structures covers it

How deep it goes

Defines connectivity, edge bounds, directed-graph distinctions, and planarity consequences without developing a connectivity-testing algorithm.

Examples

Uses connected-versus-disconnected figures, tree structure, adjacency representations, and planarity edge bounds.

What it assumes

Assumes vertices, edges, paths, and graph representations while defining connectivity and contrasting trees with directed graphs.

What you can do after

Evaluate graph structure using reachability, minimum-edge reasoning, representation trade-offs, and a preliminary planarity check.

How it connects

Connects graphs with trees, paths, directed graphs, strongly connected components, sparse graphs, dense graphs, and planarity.

liveBookmanning.com

Read Advanced Algorithms and Data Structures on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Classic Computer Science Problems in Swift: Essential techniques for practicing programmersA connected graph is a graph in which a path exists between every pair of vertices.

Compare how 2 books explain connected graph →

Related concepts

• graphkind of · A graph is a mathematical structure consisting of vertices connected by edges that represent relationships or connections.
• connected componenthas part · A connected component is a maximal subgraph in which every pair of vertices is connected by a path.
• treeincludes · A tree is a connected, acyclic structure of nodes, commonly organized hierarchically through parent-child relationships and optionally around a designated root.
• strongly connected componentcontrasts with · A strongly connected component is a maximal set of vertices in a directed graph where every vertex is reachable from every other vertex.

This explainer was generated by Manning's knowledge graph from the text of Advanced Algorithms and Data Structures. The section links point to the parts of the book it draws on.