?? cspanningtree.h
字號:
/*
1.最小生成樹
a)
static void CSpanningTree::Run(double *s, int n, int *result, int none);
b)參數(shù)
s: 二維數(shù)組第一行的地址,用法見下面例子
n: 鄰接矩陣的大小, n * n
result: 存儲結(jié)果,順序存儲n - 1條邊的兩條邊,也就是說result的大小為2 * (n - 1)個元素
none: 用戶標(biāo)示兩點之間不可達(dá)的一個數(shù)值.
c)例子
#include "header.h"
#include <iostream>
using namespace std;
int main()
{
int s[4][4] = {
{0, 1, 5, 3},
{1, 0, -1, 2},
{5, -1, 0, 4},
{3, 2, 4, 0}};
int result[6];
int i;
CSpanningTree::Run(s[0], 4, result, -1);
for(i = 0; i < 3; i++)
cout << result[i * 2] << " ---- " << result[i * 2 + 1] << endl;
return 0;
}
*/
#pragma once
#include "CUnionSet.h"
#include <queue>
using namespace std;
class CEdge
{
public:
CEdge(int _v1, int _v2, int _length): v1(_v1), v2(_v2), length(_length) {}
public:
int v1;
int v2;
int length;
};
bool operator < (const CEdge &m, const CEdge &n);
class CSpanningTree
{
public:
static void Run(double *s, int n, int *result, int none);
};
void CSpanningTree::Run(double *s, int n, int *result, int none)
{
priority_queue<CEdge> Q;
int i;
int j;
CUnionSet<int> uset;
CEdge edge(-1, -1, -1);
for(i = 0; i < n; i++)
for(j = i + 1; j < n; j++)
if(*(s + i * n + j) != none)
{
Q.push(CEdge(i, j, *(s + i * n + j)));
uset.MakeSet(i);
uset.MakeSet(j);
}
i = 0;
while(!Q.empty())
{
edge = Q.top();
Q.pop();
if(!uset.Together(edge.v1, edge.v2))
{
result[i++] = edge.v1;
result[i++] = edge.v2;
uset.JoinSet(edge.v1, edge.v2);
}
}
}
bool operator < (const CEdge &m, const CEdge &n)
{
return m.length >= n.length;
}
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -