连通分量的定义是什么？连通分量的内容有哪些？
今日热点
2023-04-20 10:24:33
无向图G的极大连通子图称为G的连通分量。任何连通图的连通分量只有一个，即是其自身，非连通的无向图有多个连通分量。无向图的极大连通子图称为的连通分量。任何连通图的连通分量只有一个，即是其自身，非连通的无向图有多个连通分量。
连通分量的内容有哪些?
作为遍历图的应用举例，下面我们来讨论如何求图的连通分量。无向图中的极大连通子图称为连通分量。求图的连通分量的目的，是为了确定从图中的一个顶点是否能到达图中的另一个顶点，也就是说，图中任意两个顶点之间是否有路径可达。这个问题从图上可以直观地看出答案，然而，一旦把图存入计算机中，答案就不大清楚了。对于连通图，从图中任一顶点出发遍历图，可以访问到图的所有顶点，即连通图中任意两顶点间都是有路径可达的。对于非连通图，从图中某个顶点出发遍历图，只能访问到包含顶点的那个连通分量中的所有顶点，而访问不到别的连通分量中的顶点。这就是说，在连通分量中的任意一对顶点之间都有路径，但是如果和分别处于图的不同连通分量之中，则图中就没有从到的路径，即从不可达。因此，只要求出图的所有连通分量，就可以知道图中任意两顶点之间是否有路径可达。
责任编辑：359
热点新闻
营业执照公示信息