图

基本概念

图是定点和边的集合。边表示为(v1,v2)

分为有向图和无向图。有向图中(v1,v2)和(v2,v1)是两条不同的边，而无向图中则相同。

有的图两个顶点之间有多条边，称为多重图，这里不讨论。

完全图：一张无向图中，任意两个顶点之间都有边相连。也就是n个定点共有n*(n-1)/2条边。而对于有向图，任意两个顶点作为起点和终点都有一条边，共有n*(n-1)条边。

度数：一个顶点引出了n条边，就称为度数为n。如果是有向图，一个顶点被n条边指向，称为入度为n；从一个顶点引出m条指向其他顶点的边，称为出度为m；度数=入度+出度。

子图：如果图B的顶点集和边集都是图A的子集，称为B是A的子图。

路径：从一个顶点到另一顶点的沿边走的路径，用沿途顶点序列表示。如果除了起点和终点，路径内没有重复的顶点，称为简单路径；如果起点和终点相同又是简单路径，称为简单环路。

连通图：无序图中，如果任意两个顶点之间都有一条路径，则称为连通图。有序图中，要求以任意两点为起点和终点都能找到一条路径，称为强连通图。如果一个图不是（强）连通图，可以找到最大（强）连通分量，即一个最大的（强）连通子图。

网络：如果连通图中的边上还有权重，则称为网络。

生成树：在连通的无向图中，可以找到n-1条边即可把所有顶点串联起来，形成一棵树，称为生成树。

用一个二维矩阵表示每两个顶点之间的联系。如果A(i,j)=1表示有一条(i,j)边，否则没有。

无向图的邻接矩阵应该是沿对角线对称的。

如果要表示网络也很方便，可以用无穷大表示没有边，而有限的数值表示边上的权重。

每个顶点引出一个链表，表示该顶点到链表中的顶点有边。

在无向图中, 如果边数为m, 则在邻接表表示中需2m个单位来存储. 为了克服这一缺点, 采用邻接多重表, 每条边用一个结点表示.

有广度优先遍历和深度优先遍历。

深度优先遍历：先走一条最长的路径，然后回退到有分叉的地方，去寻找其他路径。