13
Graphs
Objectives
A review of terms and concepts in graph theory
The adjacency matrix representation of a graph
The sparse matrix representation of a graph
Breadth-first search/traversal in a graph
Depth-first search/traversal in a graph
An introduction to NP-completeness as the measure of complexity of a
problem
Easy and hard problems in computations on graphs
Key Terms
adjacency matrix
arc
Boolean satisfiability
clique
connected component
connected graph
cycle
density of a matrix
Dijkstra’s algorithm
directed graph
edge
edge weight
Eulerian cycle
Eulerian path
graph
Hamiltonian cycle
Hamiltonian path
incident
maximal clique
multigraph
node
node indegree
node ...
Get Data Structures Using Java now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
