在无向图中, 若从顶点v到顶点w有路径存在, 则称v和w是连通的. 若图G中任意两个顶点都是连通的, 则称图G为连通图, 否则称为非连通图. 无向图中的极大连通子图称为连通分量, 在图(a)中, 图G有3个连通分量如图(b)所示.

假设一个图有n个顶点, 如果边数小于n-1, 那么此图必是非连通图. 如果图是非连通图, 那么最多可以有多少条边?

在有向图中, 如果有一对顶点v和w, 从v到w和从w到v之间都有路径, 则称这两个顶点是强连通的. 若图中任何一对顶点都是强连通的, 则称此图为强连通图. 有向图中的极大强连通子图称为有向图的强连通分量, 图G的强连通分量如图(b)所示。

假设一个有向图有n个顶点, 如果是强连通图, 那么最少需要有多少条边.

图的遍历算法可以用来判断图的连通性.

对于无向图来说, 若无向图是连通的, 则从任一结点出发, 仅需一次遍历就能够访问图中的所有顶点; 若无向图是非连通的, 则从某一个顶点出发, 一次遍历只能访问到该顶点所在连通分量的所有顶点, 而对于图中其他连通分量的顶点, 则无法通过这次遍历访问.

对于有向图来说, 若从某一顶点到图中的每个顶点都有路径, 则能够访问到图中的所有顶点, 否则不能访问到所有顶点. 因此判断有向图的强连通性, 需要依次从所有顶点出发遍历, 只有从所有顶点出发遍历到其它所有顶点, 该有向图才具有强连通性, 如果从某一个顶点出发遍历, 不能连续遍历到其它顶点, 则该有向图不具有强连通性.

邻接表