本文引用自文献：1）《大话数据结构》作者：程杰；
图的定义
在线性表中，数据元素之间是被串起来的，仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继。在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素相关，但只能和上一层中的一个元素相关。而图这种数据结构比线性表和树要更加复杂，如下图所示。
图的定义：
图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：,其中，表示一个图，是图中顶点的集合，是图中边的集合。
对于图的定义，有几点需要额外说明一下：
- 线性表中我们把数据元素叫做元素，树中将数据元素叫结点，在图中，数据元素我们称之为顶点（Vertex）。
- 线性表中可以没有数据元素，称为空表。树中没有可以没有结点，叫做空树。但对于图中则不能没有顶点，在图的定义中，强调了顶点集合V是有穷非空的。
- 线性表中，相邻的数据元素之间具有线性关系，树结构中，相邻两层的结点具有层次关系，而图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。
有向图和无向图
无向边：若顶点到之间的边没有方向，则称这条边为无向边，用无序偶对来表示。如果图中任意两个顶点之间的边都是无向边，则称改图为无向图（Undirected Graphs）。图7-2-2就是一个无向图，由于边是无方向的，连接顶点A和D的边，可以表示成无序对，也可以写成。对于图7-2-2中的无向图来说， ，其中顶点集合 ；边集合 。
有向边：若从顶点到的边有方向，则称这条边为有向边，也称为弧（Arc）。用有序偶对来表示。称为弧尾（Tail），称为弧头（Head）。如果图中任意两个顶点之间的边都是有向边，则称该图为有向图（Directed Graphs）。图7-2-3就是一个有向图。连接顶点A到D的有向边就是弧，A是弧尾，D是弧头，表示弧，注意不能写成。
对于图7-2-3中的有向图来说， ，其中顶点集合 ；边集合 。
注意：无向边是小括号“”表示，而有向边则是用尖括号“”表示。
网（网络）
有些图的边或弧具有与他相关的数字，这种与图的边或弧相关的数叫做权(Weight)。这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为网(Network)。
图7-2-3就是一张带权的图，即标识中国四大城市的直线距离的网，此图中的权就是两地的距离。
子图
假设有两个图 和 ，如果是的子集（即 ），且是的子集（即 ），则称为的子图。如下图7-2-8带底纹的图均为左侧无向图与有向图的子图。
度
无向图的度
对于无向图 ， 如果边属于（即 ）， 则称顶点和互为邻接点，即和相邻接、边依附于顶点和，或者说与顶点和相关联。
顶点的度是和相关联的边的数目，记为。
例如图7-2-8左侧上方的无向图，顶点与互为邻接点，边依附于顶点与上，顶点的度为3。而此图的边数是5，各个顶点度的和=3+2+3+2=10，推敲后发现，边数其实就是各顶点度数和的一半，多出的一半是因为重复两次计数。得出公式， 。
有向图的度
对于有向图 ， 如果弧属于（即 ）， 则称顶点邻接到顶点互为邻接点，顶点邻接自。弧和顶点、相关联。
以顶点为头的弧的数目称为的入度（InDegree），记为；以为尾的弧的数目称为的出度（OutDegree），记为；顶点的度 。
例如图7-2-8左侧下方的有向图，顶点的入度是2（从到的弧，从到的弧），出度是1（从到的弧），所以顶点A的度为2+1=3。此有向图的弧有4条，而各顶点的出度和=1+2+1+0=4，各顶点的入读和=2+0+1+1=4。所以得到公式： 。