Graph

Data Structures ⟩ Graph

🔸 定義

• vertex: a point.

  • degree of a vertex: number of joined edges.

• edge: a line joining two vertices.

  • can be directed or undirected.

  • can or cannot join the same vertex.

  • for each pair of vertices, either only one edge or multiple edges are allowed between them.

• graph: consists of some vertices joined by some edges.

  • simple graph: an edge cannot join the same vertex, only one edge is allowed for each pair of vertices.

  • directed graph: a graph that has directed edges.

  • undirected graph: a graph that has only undirected edges.

    • connected: any pair of vertices is joined by edges.

      • tree: any pair of vertices has a unique route between them.

📗 參考

• First Course in Algorithms Through Puzzles, Sec. 1.6, Graph