个人总结一下：
总的来说，可以用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 }
