图
相对于此前的线性以及半线性结构，图结构对其中元素的限定更少，因此反过来，它描述应用问题的能力也就更强。
与树类似：
\(G=(V; E)\)
vertex：\(n=|V|\)
edge|arc：\(e=|E|\)
存在连边的任何两个点都称作是彼此邻接的，那么这样一个关系，也称作邻接（adjancency）关系，而参与定义这种邻接关系的每一个顶点，与这个邻接关系之间的关系，我们也称作关联（jncidence）关系。形象地说，所谓的邻接关系就是顶点与顶点之间的关系，而关联关系实际上是描述顶点以及与它相关的某条边之间的关系。
若同一个节点与自身构成一个邻接关系，则称作自环，本节不讨论这种情况。
若邻接顶点 \(u\) 和 \(v\) 的次序无所谓，则 \((u, v)\) 为无向边（undirected edge）。例：若 \(u\) 是 \(v\) 的好友，则 \(v\) 也必是 \(u\) 的好友。
所有边均无方向的图，即无向图（undigraph）。
反之，有向图（digraph）中均为有向边（directed edge），\(u\)、\(v\) 分别称作边 \((u, v)\) 的尾（tail）、头（head）。例：“\(u\) 欠 \(v\) 的钱”与“\(v\) 欠 \(u\) 的钱”。
在有些情况下，图中的边有的是有向的，而另一部分却可能是无向的，这样的图称之为混合图（mixed graph）
本节重点研究有向图，因为通过有向图，完全可以表示并且实现无向图以及混合图。
与树类似：
路径 \(\pi=<v_0, v_1, ..., v_k>\)，长度 \(|\pi|=k\)
简单路径（simple path）：\(v_i=v_j\) 除非 \(i=j\)
环/环路：\(v_0=v_k\)
如果在一个有向图中，不包含任何的环路，则称之为有向无环图（DAG）。
经过所有的边一次而且恰好一次的环路称作欧拉环路（Eulerian tour）；对称的，经过每一个顶点一次而且恰好一次的环路称作哈密尔顿环路（Hamiltonian tour）。
一笔画问题即要找出欧拉路径。
邻接矩阵
图的表示可以采用邻接矩阵或关联矩阵来表示，本节我们主要采用邻接矩阵。
所谓邻接矩阵就是用以描述顶点之间相互邻接关系的一种形式，具体来说，这是一个方阵，如果图中包含 \(n\) 个顶点，这个矩阵也就是 \(n\times n\) 的，于是矩阵中的任何一个单元，比如对应于第 \(i\) 行第 \(j\) 列的那个单元，都表示顶点 \(i\) 与顶点 \(j\) 之间是否存在一条边（即是否关联）。
如果是无向图，那么它对应的邻接矩阵就应该是对称的，特别的，在该矩阵对角线上的元素都对应于自环。
如果是带权图（即网络），那么每个单元可以存储权值。
对于关联矩阵，如果当前的图有 \(n\) 个节点，那么这个矩阵就有 \(n\) 行，如果图中总共包含 \(e\) 条边，那么这个矩阵就对应的有 \(e\) 列，相应地，矩阵中的任何一个单元表示的也就是对应的顶点与对应的边之间。对于矩阵中的任何一列而言，应该恰好有两个单元的数值为 1，而其余的都是 0。