連通問題算法

書籍<<算法:C語言實作>>

快速查找算法

void connect()
{
	int a[N];
	for (int i = 0; i < N; i++)
	{
		a[i] = i;//初始化，假設它們的祖先是它們自己
	}
	int p, q;
	while (cin >> p >> q)
	{
		if (a[p] == a[q])
			cout << p << " 連通" << q << endl;
		int t = a[q];
		for (int i = 0; i < N; i++)
		{
			if (a[i] == t)//把所有與q連通的全部變為p，意思是換成共同的祖先
				a[i] = a[p];
		}
	}
}
           

我們把合并操作完成到最後，也就是這是一個隻有兩層的樹。

或者我們把合并操作簡化，讓查找變得麻煩一點

void connect1()
{
	int a[N];
	for (int i = 0; i < N; i++)
	{
		a[i] = i;
	}
	int q, p;
	int i, j;
	while (cin >> p >> q)
	{
		for ( i = p; i != a[i]; i = a[i]);//這裡是查找，我們從底層逐層向上
		for ( j = q; j != a[j]; j = a[j]);
		cout << endl;
		if (i == j)
		{
			cout << p << " 連通" << q << endl;
			continue;
		}
		a[i] = j; 
		、
	}
}
           

這是一種快速合并的算法，我們關注的隻是把樹合并，而不是合并到隻有兩層

的數。不過不太好的是，大的樹又可能連接配接到小的樹上，你可以試着畫畫，我們的路徑

絕對會變長。

于是我們便有了權重快速合并算法，我們隻要比較節點的數目，我們就可以很容易的避免這種問題

#define N 10000
void connect2()
{
	int a[N], b[N];
	for (int i = 0; i < N; i++)
	{
		a[i] = i;//初始化，假設它們的祖先是它們自己
		b[i] = i;
	}
	int p, q, i, j;
	
	while (cin >> p >> q)
	{
		for (i = p; i != a[i]; i = a[i]);
		for (j = q; j != a[j]; j = a[j]);//這兩個的含義都是沿着樹一直向上，知道找到祖先為止
		if (a[i] == a[j])
		{
			printf("連通");
			continue;
		}
		if (b[i] > b[j])
		{
			a[j] = i;
			b[i] += b[i];
		}
		else
		{	a[i] = j;
		b[j] += a[i];
	}

	}
}
           

還有一種等分路徑算法，我會下次更新