logo
English
Data Structures

04. Graph

Graph

1. Basic Concepts

  • Graph: Consists of a set of vertices and a set of edges; can be directed or undirected
  • Adjacency, degree, connectivity, weight, path, cycle, connected component

2. Storage Structures

  • Adjacency matrix: 2D array, suitable for dense graphs
  • Adjacency list: array + linked list, suitable for sparse graphs
  • Adjacency multilist, cross-linked list: suitable for complex graphs

3. Traversal

  • Depth-First Search (DFS): implemented recursively or with a stack, prioritizes depth
  • Breadth-First Search (BFS): implemented with a queue, prioritizes breadth

4. Basic Applications

  • Minimum spanning tree (Prim’s, Kruskal’s algorithms)
  • Shortest path (Dijkstra’s, Floyd’s algorithms)
  • Topological sorting: directed acyclic graphs
  • Critical path: AOV network, project management

Exercises

  1. Briefly describe the basic concepts and common terms of graphs.
  2. What are the advantages and disadvantages of adjacency matrix and adjacency list?
  3. What are the basic ideas and implementations of DFS and BFS?
  4. What are the common algorithms for minimum spanning tree and shortest path?
  5. What are the application scenarios of topological sorting?
Reference Answers

1. Basic Concepts

A graph consists of vertices and edges; can be directed/undirected, adjacency, degree, connectivity, weight, path, cycle, etc.

2. Advantages and Disadvantages of Storage Structures

Adjacency matrix: suitable for dense graphs, uses more space, fast lookup; adjacency list: suitable for sparse graphs, saves space, slower lookup

3. DFS and BFS

DFS: recursion/stack, prioritizes depth; BFS: queue, prioritizes breadth

4. Common Algorithms

Minimum spanning tree: Prim’s, Kruskal’s; shortest path: Dijkstra’s, Floyd’s

5. Applications of Topological Sorting

Task scheduling, course arrangement, project management, etc. in directed acyclic graphs