图的若干定义及表示

一个图(graph)由顶点集和边集组成。每一条边就是一幅点对，其中。有时也把边称作弧。如果点对是有序的，那么图就是有向的，称为有向图。顶点和邻接当且仅当，在一个有边就有边的无向图中，和邻接且和邻接。有时候边会有第三种成分，称作权或值。

图中的一条路径是一个顶点序列，其中。这样的一条路径长是该路径上的边数，即。如果一条路径上的顶点都是互异的（第一个顶点和最后一个顶点可以相同，即），那么这条路径就是简单路径。从一个顶点到它自身的边，有时候可以叫作环（自环），这个边也可以看作一条路径，路径长可以认为是0。如果一个图无自环，那么这个图就是简单图。

有向图中的圈是满足且至少长为1的路径，如果该路径是一个简单路径，那么圈就是简单圈。对于无向图，要求边是互异的，所以和就只能看作一条边，所以不存在路径形成一个圈。但在有向图中，它们可以形成一个圈。如果一个有向图无圈，那么这个有向图就称为无圈有向图(DAG)。

如果一个无向图中从每一个顶点到其他任何顶点都有一条路径，那么这个无向图就是连通的。具有这样性质的有向图是强连通的。如果一个有向图不是强连通的，但它的基础图（即去掉边上方向后形成的无向图）是连通的，那么这个有向图是弱连通的。如果图中的每一对顶点间都存在一条边，那么这个图就是完全图。

现实生活中能够用图进行模拟的一个例子是航空系统。机场可以看为顶点，航线（如果存在）可以看为边，图中的边是有权的，权可以是油耗、时间等费用，显然图是有向的，因为两个机场之间可能只能单向通行。我们希望图是强连通的，因为这样就可以从一个机场去到任何一个机场，我们也可以通过图来确定最佳航线，最佳可以指最小边数的路径，也可以是对一种权或所有权的综合考量。

图的表示：

以如下图为例：

                  

1.表示图的一种简单方法是使用一个二维数组，称为邻接矩阵表示法。对于每一条边，置；否则，数组的元素就是0，如果边具有权值，那么就置为权值，不存在的边置为0或者一个很大的数字。

 邻接矩阵法虽然简单，但是它的空间需求为。如果边的数量不是很多，那么这种方法的代价就太大了。若图是稠密的：，那么这种方法是很合适的。但在大部分应用中，图都是稀疏的，例如上面的例子，矩阵用大量的空间来存放并没有用的0值，只有很少一部分是有效值，所以邻接矩阵法是一个代价很大的并不实用的方法。

2.另一种表示方法是邻接表法，邻接表是表示图的标准方法。如果图是稀疏的，对于每一个顶点，我们使用一个表来存储和其邻接的顶点，此时的空间需求为。对于无向图来说，同一条边需要在两个表中出现，所以空间的需求增加了一倍，但这是可以接受的。

在实际应用中，顶点的名称可能并不是数字，而是字符串等，所以我们必须完成字符到数字的映射，这时候可以使用散列表，将顶点的名称映射为数字，就可以使用邻接表来表示图。但最终我们还是需要输出顶点的名字，所以还需要完成数字到名称的转换，可以使用数组来保存名称，但如果名称过长，需要的空间就很大，另一种方法是可以使散列表中存放结构体，结构体中既有保存编号的变量，也有保存对应名称的变量。