> For the complete documentation index, see [llms.txt](https://lochiwei.gitbook.io/ios/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lochiwei.gitbook.io/ios/data-structures/graph.md).

# Graph

[Data Structures](/ios/data-structures.md) ⟩ Graph

{% tabs %}
{% tab title="🔸 定義" %}
{% hint style="success" %}

* <mark style="color:purple;">**vertex**</mark>: a point.
  * <mark style="color:purple;">**degree**</mark> of a vertex: <mark style="color:red;">**number**</mark> of <mark style="color:red;">**joined edges**</mark>.
* <mark style="color:purple;">**edge**</mark>: a line joining two vertices.&#x20;
  * can be <mark style="color:red;">**directed**</mark> or <mark style="color:red;">**undirected**</mark>.
  * can or cannot <mark style="color:red;">**join the same vertex**</mark>.
  * for <mark style="color:yellow;">**each pair of vertices**</mark>, either <mark style="color:red;">**only one edge**</mark> or <mark style="color:red;">**multiple edges**</mark> are allowed between them.
* <mark style="color:purple;">**graph**</mark>: consists of some vertices joined by some edges.
  * <mark style="color:purple;">**simple graph**</mark>: an <mark style="color:orange;">**edge**</mark> <mark style="color:red;">**cannot**</mark> <mark style="color:orange;">**join the same vertex**</mark>, <mark style="color:red;">**only one edge**</mark> is allowed for each pair of vertices.
  * <mark style="color:purple;">**directed graph**</mark>: a graph that has <mark style="color:red;">**directed**</mark> edges.
  * <mark style="color:purple;">**undirected graph**</mark>: a graph that has only <mark style="color:red;">**undirected**</mark> edges.
    * <mark style="color:purple;">**connected**</mark>: <mark style="color:yellow;">**any pair of vertices**</mark> is joined by edges.
      * [<mark style="color:purple;">**tree**</mark>](/ios/data-structures/graph/tree.md): <mark style="color:yellow;">**any pair of vertices**</mark> has a <mark style="color:red;">**unique route**</mark> between them.
        {% endhint %}
        {% endtab %}

{% tab title="📗 參考" %}

* [First Course in Algorithms Through Puzzles](https://www.academia.edu/41215050/First_Course_in_Algorithms_Through_Puzzles), Sec. 1.6, Graph
  {% endtab %}
  {% endtabs %}