unit1.~cpp

最小生成树的算法范例

#include<iostream>
#include<fstream>
#include<vector>
#include<string>
#include<math.h>
using namespace std;
//---------------------------------------------------------------------------
#include <vcl.h>
#pragma hdrstop
#include "Unit1.h"
#include<mmsystem.h>
#include<clsPrim.h>
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TfrmMain *frmMain;
//---------------------------------------------------------------------------
__fastcall TfrmMain::TfrmMain(TComponent* Owner)
        : TForm(Owner)
{
}
//---------------------------------------------------------------------------

void __fastcall TfrmMain::imgGraphMouseDown(TObject *Sender,
      TMouseButton Button, TShiftState Shift, int X, int Y)
{
    mouse_down = 1;
    mouse_old_x = X / 10;
    mouse_old_y = Y / 10;
    setBrush(X, Y);
    imgGraph->Canvas->Rectangle(rectBrush);
    //添加一个图节点
    if(vecGraphNodeIndex[X / 10][Y / 10] == 2500){
        clsNode Node;
        Node.x = X / 10;
        Node.y = Y / 10;
        vecGraphNode.push_back(Node);
        vecGraphNodeIndex[X / 10][Y / 10] = vecGraphNode.size() - 1;
    }
}
//---------------------------------------------------------------------------

void __fastcall TfrmMain::imgGraphMouseUp(TObject *Sender,
      TMouseButton Button, TShiftState Shift, int X, int Y)
{
    mouse_down = 0;
    if(vecGraphNodeIndex[X / 10][Y / 10] == 2500){
        //添加一个图节点
        clsNode Node;
        Node.x = X / 10;
        Node.y = Y / 10;
        vecGraphNode.push_back(Node);
        vecGraphNodeIndex[X / 10][Y / 10] = vecGraphNode.size() - 1;
    }
    AnsiString InputString = InputBox("最小生成树", "请输入该边权值G：(G>0)", "1");
    vecGraphEdge[vecGraphNodeIndex[X / 10][Y / 10]][vecGraphNodeIndex[mouse_old_x][mouse_old_y]] = InputString.ToInt();
    vecGraphEdge[vecGraphNodeIndex[mouse_old_x][mouse_old_y]][vecGraphNodeIndex[X / 10][Y / 10]] = InputString.ToInt();
    FreshGraph();

}
//---------------------------------------------------------------------------

void __fastcall TfrmMain::imgGraphMouseMove(TObject *Sender,
      TShiftState Shift, int X, int Y)
{
    //鼠标不为设置起点或设置终点才可以描绘
    if(mouse_down){
        FreshGraph();
        imgGraph->Canvas->MoveTo(mouse_old_x * 10 + 5, mouse_old_y * 10 + 5);
        imgGraph->Canvas->LineTo(X / 10 * 10 + 5, Y / 10 * 10 + 5);
        setBrush(X, Y);
        imgGraph->Canvas->Rectangle(rectBrush);
    }
}
//---------------------------------------------------------------------------
// 名称：FreshGraph
// 功能：刷新图
//---------------------------------------------------------------------------
void TfrmMain::FreshGraph(){
    //初始化imgMAP
    rectBrush.Left = 0;
    rectBrush.Top = 0;
    rectBrush.Right = imgGraph->Width;
    rectBrush.Bottom = imgGraph->Height;
    imgGraph->Canvas->Brush->Style = bsSolid;
    imgGraph->Canvas->Pen->Color = clBlue;
    imgGraph->Canvas->Brush->Color = clBlack;
    imgGraph->Canvas->Rectangle(rectBrush);
    imgGraph->Canvas->Font->Color = clBlue;
    int i, j;
    for(i = 0; i < vecGraphNode.size(); i++){
        setBrush(vecGraphNode[i].x * 10 + 5, vecGraphNode[i].y * 10 + 5);
        imgGraph->Canvas->Rectangle(rectBrush);
    }
    int xa, xb, ya, yb;
    for(i = 0; i < vecGraphNode.size(); i++){
        for(j = i; j < vecGraphNode.size(); j++){
            if(vecGraphEdge[i][j]){
                xa = vecGraphNode[i].x * 10 + 5;
                xb = vecGraphNode[j].x * 10 + 5;
                ya = vecGraphNode[i].y * 10 + 5;
                yb = vecGraphNode[j].y * 10 + 5;
                imgGraph->Canvas->Pen->Color = clBlue;
                imgGraph->Canvas->MoveTo(xa, ya);
                imgGraph->Canvas->LineTo(xb, yb);
                imgGraph->Canvas->Brush->Style = bsClear;
                imgGraph->Canvas->Font->Color = clBlue;
                imgGraph->Canvas->TextOutA((xa + xb) / 2, (ya + yb) / 2, IntToStr(vecGraphEdge[i][j]));
            }
        }
    }
}
//---------------------------------------------------------------------------
void __fastcall TfrmMain::FormCreate(TObject *Sender)
{
    //使用双缓冲，否则imgMAP会闪烁
    imgGraph->Parent->DoubleBuffered = True;
    //初始化imgMAP
    rectBrush.Left = 0;
    rectBrush.Top = 0;
    rectBrush.Right = imgGraph->Width;
    rectBrush.Bottom = imgGraph->Height;
    imgGraph->Canvas->Brush->Style = bsSolid;
    imgGraph->Canvas->Pen->Color = clBlue;
    imgGraph->Canvas->Brush->Color = clBlack;
    imgGraph->Canvas->Rectangle(rectBrush);
    //初始化图结构
    int i, j;
    vector<int> vecTempLineGraphEdge;
    vector<int> vecTempLineGraphNodeIndex;
    for(i = 0; i < 50; i++){
        for(j = 0; j < 50; j++){
            vecTempLineGraphNodeIndex.push_back(2500);
        }
        vecGraphNodeIndex.push_back(vecTempLineGraphNodeIndex);
        vecTempLineGraphNodeIndex.clear();
    }
    for(i = 0; i < 2500; i++){
        for(j = 0; j < 2500; j++){
            vecTempLineGraphEdge.push_back(0);
        }
        vecGraphEdge.push_back(vecTempLineGraphEdge);
        vecTreeEdge.push_back(vecTempLineGraphEdge);
        vecTempLineGraphEdge.clear();
    }
}
//---------------------------------------------------------------------------
// 名称：setBrush
// 功能：设置笔刷坐标和颜色；
//---------------------------------------------------------------------------
void TfrmMain::setBrush(int X, int Y)
{
    int new_x, new_y;
    new_x = X / 10 * 10;
    new_y = Y / 10 * 10;
    rectBrush.Left = new_x + 2;
    rectBrush.Top = new_y + 2;
    rectBrush.Right = new_x + 10 - 2;
    rectBrush.Bottom = new_y + 10 - 2;
    imgGraph->Canvas->Brush->Style = bsSolid;
    imgGraph->Canvas->Pen->Color = clBlue;
    imgGraph->Canvas->Brush->Color = clBlue;

}
//---------------------------------------------------------------------------
// 名称：setTreeBrush
// 功能：设置笔刷坐标和颜色；
//---------------------------------------------------------------------------
void TfrmMain::setTreeBrush(int X, int Y)
{
    int new_x, new_y;
    new_x = X / 10 * 10;
    new_y = Y / 10 * 10;
    rectBrush.Left = new_x + 2;
    rectBrush.Top = new_y + 2;
    rectBrush.Right = new_x + 10 - 2;
    rectBrush.Bottom = new_y + 10 - 2;
    imgGraph->Canvas->Brush->Style = bsSolid;
    imgGraph->Canvas->Pen->Color = clGreen;
    imgGraph->Canvas->Brush->Color = clGreen;

}
//---------------------------------------------------------------------------
// 名称：ShowTree
// 功能：显示树
//---------------------------------------------------------------------------
void TfrmMain::ShowTree(){
    //初始化imgMAP
    rectBrush.Left = 0;
    rectBrush.Top = 0;
    rectBrush.Right = imgGraph->Width;
    rectBrush.Bottom = imgGraph->Height;
    imgGraph->Canvas->Brush->Style = bsSolid;
    imgGraph->Canvas->Pen->Color = clBlue;
    imgGraph->Canvas->Brush->Color = clBlack;
    imgGraph->Canvas->Rectangle(rectBrush);
    int i, j;
    int xa, xb, ya, yb;
    for(i = 0; i < vecGraphNode.size(); i++){
        for(j = i; j < vecGraphNode.size(); j++){
            if(vecTreeEdge[i][j]){
                xa = vecGraphNode[i].x * 10 + 5;
                xb = vecGraphNode[j].x * 10 + 5;
                ya = vecGraphNode[i].y * 10 + 5;
                yb = vecGraphNode[j].y * 10 + 5;
                imgGraph->Canvas->Pen->Color = clGreen;
                imgGraph->Canvas->MoveTo(xa, ya);
                imgGraph->Canvas->LineTo(xb, yb);
                imgGraph->Canvas->Brush->Style = bsClear;
                imgGraph->Canvas->Font->Color = clGreen;
                imgGraph->Canvas->TextOutA((xa + xb) / 2, (ya + yb) / 2, IntToStr(vecGraphEdge[i][j]));
            }else if(vecGraphEdge[i][j]){
                xa = vecGraphNode[i].x * 10 + 5;
                xb = vecGraphNode[j].x * 10 + 5;
                ya = vecGraphNode[i].y * 10 + 5;
                yb = vecGraphNode[j].y * 10 + 5;
                imgGraph->Canvas->Pen->Color = clBlue;
                imgGraph->Canvas->MoveTo(xa, ya);
                imgGraph->Canvas->LineTo(xb, yb);
                imgGraph->Canvas->Brush->Style = bsClear;
                imgGraph->Canvas->Font->Color = clBlue;
                imgGraph->Canvas->TextOutA((xa + xb) / 2, (ya + yb) / 2, IntToStr(vecGraphEdge[i][j]));
            }
        }
    }
    for(i = 0; i < vecGraphNode.size(); i++){
        setTreeBrush(vecGraphNode[i].x * 10 + 5, vecGraphNode[i].y * 10 + 5);
        imgGraph->Canvas->Rectangle(rectBrush);
    }
}
//---------------------------------------------------------------------------
void __fastcall TfrmMain::btnFindPathClick(TObject *Sender)
{
    clsPrim TreeMaker;
    vecTreeEdge = TreeMaker.MiniSpanTree(vecGraphNode, vecGraphNodeIndex, vecGraphEdge);
    ShowTree();
}
//---------------------------------------------------------------------------