图——基本概念(Graph - Concepts)

图——基本概念(Graph - Concepts)

序言(Preface)
Graph algorithms are very practical as a lot of problems in real life can be modelled as graph. Such as, network design, flow design, planning, scheduling, route finding, etc. We will talk about two famous graph algorithms in next chapters: Depth-First Search and Breadth-First Search.

基本概念(Graph Concepts)

图的数学表示(Graph Representation - Mathematically)

图的矩阵表示(Adjacency Matrix)

图的邻接表表示(Adjacency List)

图的度(Graph Degree)
If (v, u) ∈ E, we say v and u are adjacent or neighbours.
The degree of v is the number of edges incident on v.
The in-degree of v is the number of edges going to v.
The out-degree of v is the number of edges going from v.

路径和环(Path and Cycle)
A path in G(V, E) is a sequence of nodes v0, v1, v2, … , vk from V. (vi, vi+1) ∈ E.
The path has length k.
A simple path has no duplicate nodes.
A cycle is a path which v0 = vk.

写在最后的话(PS)
We talk about some basic graph concepts. In the next a few chapters we will talk about some algorithms based on graph.

Ask yourself what problems in real life can we solve using graph concepts? Give specific examples.

Welcome questions always and forever.