定义

无向图的极大连通子图称为的连通分量( Connected Component)。任何连通图的连通分量只有一个，即是其自身，非连通的无向图有多个连通分量。

相关概念

路径

①无向图的路径：在无向图中，若存在一个顶点序列 使得 均属于 ，则称顶点 到 存在一条路径(Path)。

②有向图的路径：在有向图中，路径也是有向的，它由  中的有向边 组成。

③路径长度：路径长度定义为该路径上边的数目。 

顶点间的连通性

在无向图中，若从顶点 到顶点 有路径（当然从 到 也一定有路径），则称 和 是连通的。

连通图

若中任意两个不同的顶点 和 都连通（即有路径），则称为连通图(Connected Graph)。例如，图2是连通图。

强连通图

有向图中，若对于中任意两个不同的顶点 和 ，都存在从 到 以及从 到 的路径，则称是强连通图。

强连通分量

有向图的极大强连通子图称为的强连通分量，强连通图只有一个强连通分量，即是其自身。非强连通的有向图有多个强连通分量。

无向图简介

作为遍历图的应用举例，下面我们来讨论如何求图的连通分量[1]。无向图中的极大连通子图称为连通分量。求图的连通分量的目的，是为了确定从图中的一个顶点是否能到达图中的另一个顶点，也就是说，图中任意两个顶点之间是否有路径可达。这个问题从图上可以直观地看出答案，然而，一旦把图存入计算机中，答案就不大清楚了。

对于连通图，从图中任一顶点出发遍历图，可以访问到图的所有顶点，即连通图中任意两顶点间都是有路径可达的。

对于非连通图，从图中某个顶点 出发遍历图，只能访问到包含顶点 的那个连通分量中的所有顶点，而访问不到别的连通分量中的顶点。这就是说，在连通分量中的任意一对顶点之间都有路径，但是如果 和 分别处于图的不同连通分量之中，则图中就没有从 到 的路径，即从 不可达 。因此，只要求出图的所有连通分量，就可以知道图中任意两顶点之间是否有路径可达。