数据结构无向图,连通图 [复制链接]

一、图（Graph）

图是由顶点(vertex)的有穷非空集合和顶点之间边(edge)的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合a.若顶点之间Vi和Vj之间没有方向,则为无向边,用无序偶对(Vi,Vj)表示b.若顶点之间Vi和Vj之间有方向,则为有向边(也称弧),用有序偶对Vi,Vj表示,Vi为弧尾,Vj为弧头。无向图：任意两顶点之间的边都是无向边，则该图为无向图。有向图：任意两顶点之间的边都是有向边，则该图为有向图。

二、无向图的遍历

（1）深度优先遍历基本思路：a.访问顶点Vb.从V的未被访问的邻接点中选取一个顶点W，从W出发进行深度优先遍历c.重复以上2步，直到图中所有和V有路径相通的顶点被访问到

伪代码类似树的前序遍历)1.访问顶点,visited[v]=1;2.w=顶点v的第一个邻接点;3.while(w){if(w未被访问)从顶点w出发递归执行该算法w=顶点v的下一个邻接点}（2）广度优先遍历基本思路：1.访问顶点V2.依次访问V的各个未被访问的邻接点V1，V2，V3……VK3.分别V1，V2，V3……VK从出发依次访问他们未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问，直到图中所有与顶点V有路径相通的顶点都被访问到

伪代码类似树的层序遍历)1.初始化队列Q2.访问顶点v,visited[v]=1,顶点入队Q;3.while(队列Q非空){v=队列Q的队头元素出队w=顶点v的第一个邻接点while(w存在){if(w未访问){访问顶点w,visited[w]=1;顶点w入队列Q}w=顶点v的下一个邻接点}}

三、连通图和连通分量

1．顶点间的连通性在无向图G中，若从顶点vi到顶点vj有路径(当然从vj到vi也一定有路径)，则称vi和vj是连通的。2．连通图

　若V(G)中任意两个不同的顶点vi和vj都连通(即有路径)，则称G为连通图(Con-nectedGraph)。

图G2，和G3是连通图。

3．连通分量无向图G的极大连通子图称为G的最强连通分量(ConnectedComponent)。注意：

　　①任何连通图的连通分量只有一个，即是其自身　②非连通的无向图有多个连通分量。下图中的G4是非连通图，它有两个连通分量H1和H2。

强连通图和强连通分量1．强连通图

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

2．强连通分量

　有向图的极大强连通子图称为G的强连通分量。

注意：①强连通图只有一个强连通分量，即是其自身。②非强连通的有向图有多个强连分量。下图中的G1不是强连通图，因为v3到v2没有路径，但它有两个强连通分量，如右图所示。

网络(Network)若将图的每条边都赋上一个权，则称这种带权图为网络(Network)。注意：

　权是表示两个顶点之间的距离、耗费等具有某种意义的数。