无向图的连通分量和生成树
在对无向图进行遍历时，对于连通图，仅需从图中任一顶点出发，进行深度优先搜索或广度优先收缩，便可访问到图中所有顶点。对非连通图，则需从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。这些顶点集加上边就是联通分量
用DFS或BFS将一个图连接成一个生成树，DFS生成的是深度优先生成树，BFS生成的是广度优先生成树。
对于非连通图，每个连通分量中的顶点集，和遍历时走过的边一起构成若干棵生成树，这些连通分量的生成树组成非连通图的生成森林。
void DFSForest(Graph G, CSTree &T) {
// 建立无向图G的深度优先生成森林的(最左)孩子(右)兄弟链表T
int v; int j=0;
CSTree p,q;
T = NULL;
for (v=0; v<G.vexnum; ++v) visited[v] = FALSE;
for (v=0; v<G.vexnum; ++v)
if (!visited[v]) { // 第v顶点为新的生成树的根结点
p= (CSTree)malloc(sizeof(CSNode)); // 分配根结点
p->data=GetVex(G,v); // 给该结点赋值
p->firstchild=NULL;
p->nextsibling=NULL;
if (!T) T = p; // 是第一棵生成树的根(T的根)
else q->nextsibling = p; // 其它生成树的根(前一棵的根的“兄弟”)
q = p; // q指示当前生成树的根
DFSTree(G, v,p); // 建立以p为根的生成树
}//if
} // DFSForest
void DFSTree(Graph G, int v, CSTree &T) {
// 从第v个顶点出发深度优先遍历图G，建立以T为根的生成树
int w;
CSTree p,q;
bool first =TRUE;
visited[v] = TRUE;
for (w=FirstAdjVex(G, v); w!=-1; w=NextAdjVex(G, v, w))
if (!visited[w]) {
p = (CSTree) malloc (sizeof (CSNode)); // 分配孩子结点
p->data = GetVex(G,w);
p->firstchild=NULL;
p->nextsibling=NULL;
if (first) { // w是v的第一个未被访问的邻接顶点
T->firstchild = p; first = FALSE; // 是根的左孩子结点
} else { // w是v的其它未被访问的邻接顶点
q->nextsibling = p; // 是上一邻接顶点的右兄弟结点
}
q = p;
DFSTree(G,w,q) ;
}//if
} // DFSTree
有向图的强连通分量
深度优先搜索是求有向图的强连通分量的一个新的有效方法。
- 从某一顶点开始，遍历全图，并记录遍历顺序
- 从最后一个遍历点开始，逆序 遍历
- 如果不能遍历到所有的点，则去掉这个点之后再找一个最后遍历的点向前遍历
- 如果可以遍历到所有的点，那途径的点击就是一个强连通分量的顶点集
也就是说，在DFS之后，按照最后一个遍历到第一个遍历的点再来一次逆向DFS，如果可以遍历到所有点（除了向前推进删掉的点），那么就确定了一条强连通分量
最小生成树
最小生成树就是构造连通网的最小代价生成树。
普利姆算法
因为最小生成树是要把所有的点连接起来，那么我们假设一个集合，这个集合存储已经被连接起来的点，我们就可以建一个数组，存储这个集合到任意未被连接的点的距离。
当我们每更新（加进一个点）的时候，就更新这个数组。
因此，prim就是一个贪心的思想，他首先取任意一个点作起点，然后生成这个起点到其他点的距离。如果这个点没有和其他点直接连接就假设为无穷大。
因为这个点终结是要纳入生成树的，那么就取最小的那个路，然后把与之相连的点纳入生成树集合，然后根据这个点更新距离数组（找与这个新入的点直接相连的）。
伪代码：
void MiniSpanTree_PRIM(MGraph G, VertexType u) {
// 用普里姆算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边。
// 记录从顶点集U到V－U的代价最小的边的辅助数组定义：
// struct {
// VertexType adjvex;
// VRType lowcost;
// } closedge[MAX_VERTEX_NUM];
int i,j,k;
k = LocateVex ( G, u );
for ( j=0; j<G.vexnum; ++j ) { // 辅助数组初始化
if (j!=k)
{ closedge[j].adjvex=u; closedge[j].lowcost=G.arcs[k][j].adj; }
}
closedge[k].lowcost = 0; // 初始，U＝{u}
for (i=1; i<G.vexnum; ++i) { // 选择其余G.vexnum-1个顶点
k = minimum(closedge); // 求出T的下一个结点：第k顶点
// 此时closedge[k].lowcost =
// MIN{ closedge[vi].lowcost | closedge[vi].lowcost>0, vi∈V-U }
printf(closedge[k].adjvex, G.vexs[k]); // 输出生成树的边
closedge[k].lowcost = 0; // 第k顶点并入U集
for (j=0; j<G.vexnum; ++j)
if (G.arcs[k][j].adj < closedge[j].lowcost) {
// 新顶点并入U后重新选择最小边
// closedge[j] = { G.vexs[k], G.arcs[k][j].adj };
closedge[j].adjvex=G.vexs[k];
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
} // MiniSpanTree
C语言实现：
它的本质就是贪心，先从任意一个点开始，找到最短边，然后不断更新更新len数组，然后再选取最短边并标记经过的点，直到所有的点被标记，或者说已经选好了n-1条边。
#include <stdio.h>
#include <string.h>
#define INF 1000000
//最小生成树
//普里姆
int G[200][200];
int len[200];
bool vis[200];
int prm (int n)
{
int i,k,ans = 0;
memset (vis,0,sizeof(vis));
for (i = 2;i <= n;i++)//初始化
len[i] = G[1][i];
vis[1] = 1;
for (i = 1;i < n;i++) //循环n - 1次
{ //因为n个顶点的MST一定是n-1条边
int imin = INF,xb;
for (k = 1;k <= n;k++)
if (!vis[k] && imin > len[k])
{
imin = len[k];
xb = k;
}
if (imin == INF) //没有找到最小值，说明图不连通
return -1;
vis[xb] = 1;
ans += imin;
for (k = 1;k <= n;k++)
if (!vis[k] && len[k] > G[xb][k])
len[k] = G[xb][k];
}
return ans;
}
int main()
{
int n,m;
while (~scanf ("%d%d",&n,&m))
{
int i,k;
for (i = 1;i <= n;i++)
for (k = 1;k <= n;k++)
if (i != k)
G[i][k] = INF;
else
G[i][k] = 0;
for (i = 0;i < m;i++)
{
int a,b,c;
scanf ("%d%d%d",&a,&b,&c);
if (G[a][b] > c) //如果有边多次录入，选权最小的那个
G[a][b] = G[b][a] = c;
}
int ans = prm(n);
printf ("%dn",ans);
}
return 0;
}
克鲁斯卡尔算法
一个排序一个并查集只是表面，实质还是贪心，只不过普里斯是任选一个点选最短路径，而克鲁斯卡尔是看全局，全体边排序。
我们贪心选择最短的路径，而且保证每加入一个新的路径就要有一个新的顶点加入生成树。
C语言实现：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INF 1000000
//最小生成树
//克鲁斯卡尔
int vis[200];
struct eg
{
int v,u,w;
}e[100000];
int cmp (const void *a,const void *b)
{
struct eg *ta = (struct eg *)a;
struct eg *tb = (struct eg *)b;
return ta->w - tb->w;
}
int fin (int a)
{
int r = a;
while (vis[r] != r)
r = vis[r];
int k;
while (vis[a] != a)
{
k = vis[a];
vis[a] = r;
a = vis[k];
}
return r;
}
int add (int a,int b)
{
vis[fin(a)] = fin (b);
return 0;
}
int kls(int n,int m)
{
int i;
int ans = 0;
for (i = 0;i <=n;i++)
vis[i] = i;
for (i = 0;i < m;i++)
{
if (fin(e[i].u) != fin(e[i].v))
{
add (e[i].u,e[i].v);
ans += e[i].w;
}
}
return ans;
}
int main()
{
int n,m;
while (~scanf ("%d%d",&n,&m))
{
int i,k;
for (i = 0;i < m;i++)
{
int a,b,c;
scanf ("%d%d%d",&a,&b,&c);
e[i].u = a;
e[i].v = b;
e[i].w = c;
}
qsort(e,m,sizeof(e[0]),cmp);
int ans = kls(n,m);
printf ("%dn",ans);
}
return 0;
}
关节点和重连通分量
假若在删去顶点v以及和v相关联的个边之后，将图的一个连通分量分割成两个或两个以上的连通分量，则称顶点v为该图 的一个关节点。一个没有关节点的连通图成为重连通图。
在重连通图上，任意一对顶点之间至少存在两条路径，则在删除某个顶点以及依附于该顶点的各边时也不破坏图的连通性。若在连通图上至少删除k个顶点才能破坏图的连通性，则称此图的连通度为k。
利用深度优先搜索便可求得图的关节点，并由此可判别图是否是重连通的。
友深度优先生成树可得出两类关节点的特性：
- 若生成树的根有两棵或两棵以上的子树，则此根顶点比为关节点。
- 若生成树中某个非叶子顶点v，其某棵子树的根和子树中的其他节点均没有指向v的祖先和回边，则v为关节点。
伪代码：
void FindArticul(ALGraph G) {
// 连通图G以邻接表作存储结构，查找并输出G上全部关节点。
// 全局量count对访问计数。
int v;
struct ArcNode *p;
visited[0] = 1; // 设定邻接表上0号顶点为生成树的根
for (int i=1; i<G.vexnum; ++i) visited[i] = 0; // 其余顶点尚未访问
p = G.vertices[0].firstarc;
if(p) {
v = p->adjvex;
DFSArticul(G, v); // 从第v顶点出发深度优先查找关节点。
if (count < G.vexnum) { // 生成树的根有至少两棵子树
printf (0, G.vertices[0].data); // 根是关节点，输出
while (p->nextarc) {
p = p->nextarc; v = p->adjvex;
if (visited[v]==0) DFSArticul(G, v);
}//while
}//if
}//if(p)
} // FindArticul
void DFSArticul(ALGraph G, int v0 ) {
// 从第v0个顶点出发深度优先遍历图G，查找并输出关节点
int min,w;
struct ArcNode *p;
visited[v0] = min = ++count; // v0是第count个访问的顶点
for (p=G.vertices[v0].firstarc; p!=NULL; p=p->nextarc) {
// 检查v0的每个邻接顶点
w = p->adjvex; // w为v0的邻接顶点
if (visited[w] == 0) { // w未曾被访问，是v0的孩子
DFSArticul(G, w); // 返回前求得low[w]
if (low[w] < min) min = low[w];
if (low[w] >= visited[v0])
printf(v0, G.vertices[v0].data); // 输出关节点
}
else if (visited[w] < min) min = visited[w];
// w已被访问，w是v0在生成树上的祖先
}//for
low[v0] = min;
} // DFSArticul
