连通性问题--Algorithms IN C读书笔记

近期在看《Algorithms IN C》这本书。刚開始看，读的是英文版的。感觉作者的叙述有点不太easy理解。就找了一本中文版的来看，发现还是看英文版的比較好。先看了第一章的大部分，后面的总结还没有看，我的感受是。一个小的问题仅仅须要找到一个正确的算法就能够了。根本不许要去考虑算法的效率和性能，仅仅有在解决一些大型的实际问题时，算法的优劣才干体现出来。另外，就是添加机器的性能远不如改善算法的性能贡献大。

第一章举了一个连通性的样例，作者一步一步的引导我们来改进算法，使得这个算法终于能够真正的用在实际问题中。这个问题的描写叙述及四个解决算法，例如以下：

问题描写叙述
   输入两个整数，代表两个节点。假设这两个整数没有建立连接（这包含直接连接和通过其它节点连接），那么我们就建立这两个节点之间的连接。否则，继续输入下一个节点

四个逐步改进的算法例如以下：

//算法一
#include <stdio.h>

#define N 10

int main(void)
{
    int id[N];
    int t,i,p,q;

    //一定要初始化啊
    for(i=0;i<N;i++)
    {
        id[i] = i;
    }

    while( scanf("%d%d",&p,&q)==2 )
    {
        if( id[p]==id[q] )
            continue;
        t = id[p];
        for(i=0;i<N;i++)
        {
            if( id[i]==t )
            {
                id[i] = id[q];
            }
        }

        for(i=0;i<N;i++)
        {
            printf("%d	",id[i]);
        }
        printf("
");
    }

    return 0;
}

这四个算法所使用的数据结构都是数组。算法一是把连接（包含直接连接和间接连接）在一起的整数所相应的数组元素都赋值为同样的值。

//算法二
#include <stdio.h>

#define N 10

int main(void)
{
    int id[N];
    int i,j,p,q;

    for(i=0;i<N;i++)
    {
        id[i] = i;
    }

    while( scanf("%d%d",&p,&q)==2 )
    {
        //必须使用以下两次循环。否则当心陷入死循环
        for(i=p;id[i]!=i;i=id[i]);
        for(j=q;id[j]!=j;j=id[j]);

        if( i==j )
            continue;
        id[i] = j;

        for(i=0;i<N;i++)
        {
            printf("%d	",id[i]);
        }
        printf("
");
    }

    return 0;
}

算法二採用的数据结构仍然是数组，可是逻辑上确实树的结构。我们首先依据输入的两个整数，分别找到其所在的树的根节点，然后检測两个节点所在的树的根节点是否同样。假设同样。就说明是同一棵树，否则就把这两个根节点连接起来。

//算法三
#include <stdio.h>

#define N 10

int main(void)
{
	int id[N],sz[N];
	int p,q,i,j;

	for(i=0;i<N;i++)
	{
		id[i] = i;
		sz[i] = 1;
	}	

	while( scanf("%d%d",&p,&q)==2 )
	{
		for(i=p;id[i]!=i;i=id[i]);
		for(j=q;id[j]!=j;j=id[j]);
		if( sz[i]<sz[j] )
		{
			id[i] = j;
			sz[j] += sz[i];
		}
		else
		{
			id[j] = i;
			sz[i] += sz[j];
		}
		
		printf("i=%d
j=%d
",i,j);

		for(i=0;i<N;i++)
		{
			printf("%d	",sz[i]);
		}
		printf("
");
		
		for(i=0;i<N;i++)
		{
			printf("%d	",id[i]);
		}
		printf("
");
	}

	return 0;
}

算法三是在算法二的基础之上改进而来的。可是它加入了一个数据结构，记录以每一个节点为根的树中的元素的个数。

通过这个数据结构，每次都把小树连接到大树上，防止树的深度过深。

//算法四
#include <stdio.h>

#define N 10

int main(void)
{
	int id[N];
	int sz[N];
	int p,q,i,j;

	//初始化
	for(i=0;i<N;i++)
	{
		id[i] = i;
		sz[i] = 1;
	}

	while( scanf("%d%d",&p,&q)==2 )
	{
		for(i=p;id[i]!=i;i=id[i])
		{
			id[i] = id[id[i]];
		}
		for(j=q;id[j]!=j;j=id[j])
		{
			id[j] = id[id[j]];
		}

		if( sz[i]<sz[j] )
		{
			id[i] = j;
			sz[j] += sz[i];
		} 
		else
		{
			id[j] = i;
			sz[i] += sz[j];
		}

        printf("i=%d
j=%d
",i,j);

        for(i=0;i<N;i++)
        {
            printf("%d	",sz[i]);
        }
        printf("
");

        for(i=0;i<N;i++)
        {
            printf("%d	",id[i]);
        }
        printf("
");
	}

	return 0;
}

算法四就是在算法三的基础之上又做了进一步的改进，将树的深度进一步的缩小。