判断一个图是否连通

个人总结一下：

总的来说，可以用DFS（O（v^2））和BFS(O(v+e))的思想都能实现，只要从一个点出发，然后判断是否能遍历完所有的点。还有就是Tarjan算法和GABOW算法，这个没研究过，据说很好用。

实现办法一：用Floyd算法，时间复杂度为O（v^3），时间复杂度较大。

实现办法二：拓扑排序（多用于有向图）。

实现办法三：用BFS和visa[]标志数组，看看从一个点出发，是否能访问完所有的点。

实现办法四：用DFS，（思想和办法三相差无几，递归用while循环代替而已）核心代码如下：

用邻接链表表示的图

 1 void dfs(int s)
 2 {
 3       visit[s] = true;
 4       cnt++;
 5       node* p = vnode[s];
 6       for (;p; p = p->next)
 7       {
 8            if (!visit[p->v]) 
 9 
10                   dfs(p->v);
11       }
12       return;
13  }
14 
15 cnt为全局变量，当cnt与总结点数相等时，就连通。
16 
17 
18 
19 /*用了广度优先搜索的思想*/
20 bool Connectivity_BFS(MGraph m)
21 {
22  queue<int> q;
23  bool visa[MAX_VERTEX_NUM];//之前先初始化为false
24  int count=0;
25  memset(visa,0,sizeof(visa));
26  q.push(1);
27  while(!q.empty())
28  {
29   int v=q.front();
30   visa[v]=true;
31   q.pop();
32   count++;
33   for(int i=1;i<=m.vexnum;i++)//把与v连通并且没有被访问过的结点压进队列里面。
34   {
35    if(m.arc[v][i].weight)
36     if(!visa[i])
37     {
38      q.push(i);
39      visa[i]=true;//标志被访问过。
40     }
41   }
42  }
43  if(count==m.vexnum)//如果压进栈的结点个数刚好等于总结点的个数，则连通。
44   return true;
45  return false;
46 }