普里姆算法动画演示.doc

图形库 EasyX
作者 CUIT----某

#include<stdio.h>
#include<stdlib.h>
#include<graphics.h>
#include<conio.h>
#include<windows.h>

#define INT_MAX 99 //32768
#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 10
#define VRType int
//#define InfoType int
#define VertexType int
#define Status int
#define ERROR 0
#define OK 1

//int IncInfo;

typedef enum {DG, DN, UDG, UDN} GraphKind;

struct zb//存放节点的横纵坐标
{
int x;
int y;
};

typedef struct point//节点结构体，包含节点标志和坐标信息
{
VertexType Vexs;
zb p;
}Point;

typedef struct ArcCell//邻接矩阵
{
VRType adj;
// InfoType *info;
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct//图的结构体
{
Point vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum, arcnum;
GraphKind kind;
}MGraph;

struct CLOSEDGE//辅助数组
{
VertexType adjvex;//存放生成树顶点集合外各点距离集合内哪个顶点最近
VRType lowcost;//存放生成树顶点集合内顶点到生成树外各顶点各边上的最小权值
}closedge[MAX_VERTEX_NUM];

//存放各种可能的图的节点的坐标
struct zb ZB[5][8] ={
{{200, 100}, {200, 500}, {600, 100}, {600, 500},{0,0},{0,0},{0,0},{0,0}},//4节点(0)
{{200, 100}, {600, 100}, {400, 300}, {200, 500}, {600, 500},{0,0},{0,0},{0,0}},//5节点(1)
{{400, 100}, {100, 200}, {400, 300}, {700, 200}, {200, 500}, {600, 500},{0,0},{0,0}},//6节点(2)
{{300, 100}, {500, 100}, {700, 300}, {400, 300}, {600, 500}, {200, 500}, {100, 300},{0,0}},//7节点(3)
{{300, 100}, {400, 100}, {500, 200}, {500, 300}, {400, 400}, {300, 400}, {200, 300}, {200, 200}}//8节点(4)
};

//书上例子中的弧的结构体
struct rec_book
{
int va;
int vb;
int W;
};

//存放弧的信息
struct rec_book Rec[10] = {{1,2,6},{1,3,1},{1,4,5},{2,3,5},{2,5,3},{3,4,5},{3,5,6},{3,6,4},{4,6,2},{5,6,6}};

void start();//开始页面
void show();//自定义演示
void show_book();//书上例子演示
void biaoge_show();//表格建立
Status CreateGraph(MGraph &G);//选择图是何种图
Status CreateUDN(MGraph &G);//建立图
void MiniSpanTree_PRIM(MGraph G, VertexType u);//普里姆算法
Status LocateVex(MGraph G, VertexType u);//定位节点u在存储中的位置
Status minimum(struct CLOSEDGE p[], int n);//k的下一个节点
void donghua();

int main()
{
start();

initgraph(1200,600);
biaoge_show();
show();

getchar();
closegraph();

return 0;
}

Status LocateVex(MGraph G, VertexType u)
{
int i;
for(i = 0; i < G.vexnum; i++)
if(G.vexs[i].Vexs == u)
{
return i; //返回在图中的位置，否则返回其他信息
}
return 0;
}

//void Input(InfoType &INFO)
//{

//}

Status CreateUDN(MGraph &G)
{
int i, j, k, v1, v2, w;
char s[10];
char S[10];
int num_x = 765, num_y = 220;

LOGFONT f;
getfont(&f);
f.lfHeight = 20;
strcpy(f.lfFaceName, "华文行楷");
f.lfQuality = ANTIALIASED_QUALITY;
f.lfWeight = 30;
setfont(&f);
setcolor(YELLOW);

InputBox(s, 10, "请输入图中的顶点数(4~8)");
sscanf(s, "%d", &G.vexnum);

InputBox(s, 10, "请输入图中的弧度数");
sscanf(s, "%d", &G.arcnum);

for(i = 0;i < G.vexnum;++i)
//scanf("%d", &G.vexs[i]);
{
num_x = num_x + 50;
InputBox(s, 10, "请输入顶点向量");
sscanf(s, "%d", &G.vexs[i].Vexs );
sprintf(S, "%d", G.vexs[i].Vexs );
clearrectangle(num_x - 14, num_y - 19, num_x + 34, num_y + 29);
outtextxy(num_x, num_y, S);
G.vexs[i].p = ZB[G.vexnum - 4][i];
setlinestyle(PS_SOLID, 3);
circle(ZB[G.vexnum - 4][i].x, ZB[G.vexnum - 4][i].y, 20);

sprintf(S, "%d", G.vexs[i].Vexs);
outtextxy(ZB[G.vexnum - 4][i].x - 5, ZB[G.vexnum - 4][i].y - 5, S);

}
for(i = 0; i < G.vexnum; ++i)
for( j = 0; j < G.vexnum; ++j)
{
G.arcs[i][j].adj = INFINITY;
// G.arcs[i][j].info = NULL;
}
for(k = 0; k < G.arcnum; ++k)
{
//scanf("%d%d%d", &v1, &v2, &w);
InputBox(s, 10, "请输入弧的起点");
sscanf(s, "%d", &v1);
InputBox(s, 10, "请输入弧的终点");
sscanf(s, "%d", &v2);
InputBox(s, 10, "请输入弧的权值");
sscanf(s, "%d", &w);

i = LocateVex(G, v1);
j = LocateVex(G, v2);
setlinestyle(PS_SOLID, 3);
setcolor(WHITE);
line(G.vexs[i].p.x, G.vexs[i].p.y, G.vexs[j].p.x, G.vexs[j].p.y);
setcolor(YELLOW);
sprintf(S, "%d", w);
setbkmode(TRANSPARENT);
outtextxy((G.vexs[i].p.x + G.vexs[j].p.x) / 2, (G.vexs[i].p.y + G.vexs[j].p.y) / 2, S);

G.arcs[i][j].adj = w;
// if(IncInfo)
//Input(*G.arcs[i][j].info);
G.arcs[j][i] = G.arcs[i][j];
}
return 0;
}

Status CreateGraph(MGraph &G)
{
char s[10];
InputBox(s, 10, "请输入选择何种图(建议输入：3)");
sscanf(s, "%d", &G.kind);
switch(G.kind)
{
//case DG: return CreateDG(G);
//case DN: return CreateDN(G);
//case UDG: return CreateUDG(G);
case UDN: CreateUDN(G); break;
default: return ERROR;
}
return 0;
}

Status minimum(struct CLOSEDGE p[], int n)
{
int Min_quan;
int i = 0;
int j = 0;
Min_quan = p[0].lowcost;

while(Min_quan == 0)
{
Min_quan = p[i].lowcost;

i++;
}
for( i = 0; i < n; i++)
{
if(p[i].lowcost != 0 && p[i].lowcost <= Min_quan)
{
Min_quan = p[i].lowcost;
j = i;
}
}

return j;
}

void MiniSpanTree_PRIM(MGraph G, VertexType u)
{

int i, j, k, y, z;
k = LocateVex(G, u);
char S[10];
int num_x = 765, num_y1 = 70, num_y2 = 120;
int num_x1 = 815, num_y = 320;
for(j = 0; j < G.vexnum; ++j)
{
num_x = num_x + 50;
if(j != k)
{
closedge[j].adjvex = u; //{u, G.arcs[k][j].adj};
sprintf(S, "%d", closedge[j].adjvex);
clearrectangle(num_x - 14, num_y1 - 19, num_x + 34, num_y1 + 29);
outtextxy(num_x, num_y1, S);

closedge[j].lowcost = G.arcs[k][j].adj;
sprintf(S, "%d", closedge[j].lowcost);
clearrectangle(num_x - 14, num_y2 - 19, num_x + 34, num_y2 + 29);
outtextxy(num_x, num_y2, S);
}
}

closedge[k].lowcost = 0;
sprintf(S, "%d", k + 1);
outtextxy(num_x1, num_y, S);

for(i = 1; i < G.vexnum; ++i)
{
num_x = 765;
k = minimum(closedge, G.vexnum);
printf("\n%d %d", closedge[k].adjvex, G.vexs[k]);
//定位顶点标志在vexs数组里的位置
y = LocateVex(G, closedge[k].adjvex);
z = LocateVex(G, G.vexs[k].Vexs);
setlinecolor(RED);
Sleep(1000);
setlinestyle(PS_SOLID, 3);
line(G.vexs[y].p.x, G.vexs[y].p.y, G.vexs[z].p.x, G.vexs[z].p.y);

closedge[k].lowcost = 0;
num_x1 = num_x1 + 50;
sprintf(S, "%d", k + 1);

outtextxy(num_x1, num_y, S);

for(j = 0; j < G.vexnum; ++j)
{
num_x = num_x + 50;
if(G.arcs[k][j].adj < closedge[j].lowcost)
//closedge[j] = {G.vexs[k], G.arcs[k][j].adj};
{
closedge[j].adjvex = G.vexs[k].Vexs; //{u, G.arcs[k][j].adj};
sprintf(S, "%d", closedge[j].adjvex);
clearrectangle(num_x - 14, num_y1 - 19, num_x + 34, num_y1 + 29);
outtextxy(num_x, num_y1, S);

closedge[j].lowcost = G.arcs[k][j].adj;
sprintf(S, "%d", closedge[j].lowcost);
clearrectangle(num_x - 14, num_y2 - 19, num_x + 34, num_y2 + 29);
outtextxy(num_x, num_y2, S);

}

}

}
}

void show()
{
MGraph G;
VertexType u;

CreateUDN(G);
//检验数组是否正确
/* for(i = 0; i < G.vexnum; i++)
{
for(j = 0; j < G.vexnum; j++)
{
printf(" %d ", G.arcs[i][j]);
}
printf("\n");
}*/

char s[10];
InputBox(s, 10, "请输入开始节点（节点标志）");
sscanf(s, "%d", &u);
MiniSpanTree_PRIM(G, u);
}

void show_book()
{
MGraph G;
VertexType u = 1;

int i, j, k, v1, v2, w;
char S[10];
int num_x = 765, num_y = 220;

LOGFONT f;
getfont(&f);
f.lfHeight = 20;
strcpy(f.lfFaceName, "华文行楷");
f.lfQuality = ANTIALIASED_QUALITY;
f.lfWeight = 30;
setfont(&f);
setcolor(YELLOW);

G.vexnum = 6;

G.arcnum = 10;

for(i = 0;i < G.vexnum;++i)
//scanf("%d", &G.vexs[i]);
{
num_x = num_x + 50;
G.vexs[i].Vexs = i + 1;
sprintf(S, "%d", G.vexs[i].Vexs );
clearrectangle(num_x - 14, num_y - 19, num_x + 34, num_y + 29);
outtextxy(num_x, num_y, S);
G.vexs[i].p = ZB[G.vexnum - 4][i];
setlinestyle(PS_SOLID, 3);
circle(ZB[G.vexnum - 4][i].x, ZB[G.vexnum - 4][i].y, 20);

sprintf(S, "%d", G.vexs[i].Vexs);
outtextxy(ZB[G.vexnum - 4][i].x - 5, ZB[G.vexnum - 4][i].y - 5, S);
Sleep(100);

}
for(i = 0; i < G.vexnum; ++i)
for( j = 0; j < G.vexnum; ++j)
{
G.arcs[i][j].adj = INFINITY;
// G.arcs[i][j].info = NULL;
}
for(k = 0; k < G.arcnum; ++k)
{
v1 = Rec[k].va;
v2 = Rec[k].vb;
w = Rec[k].W;

i = LocateVex(G, v1);
j = LocateVex(G, v2);
setlinestyle(PS_SOLID, 3);
setcolor(WHITE);
line(G.vexs[i].p.x, G.vexs[i].p.y, G.vexs[j].p.x, G.vexs[j].p.y);
setcolor(YELLOW);
sprintf(S, "%d", w);
setbkmode(TRANSPARENT);
outtextxy((G.vexs[i].p.x + G.vexs[j].p.x) / 2, (G.vexs[i].p.y + G.vexs[j].p.y) / 2, S);

G.arcs[i][j].adj = w;
// if(IncInfo)
//Input(*G.arcs[i][j].info);
G.arcs[j][i] = G.arcs[i][j];
Sleep(100);
}

MiniSpanTree_PRIM(G, u);

}

void start()
{
initgraph(1200,600);
MOUSEMSG n;
loadimage(NULL, "fongmian.jpg");
while(true)
{
n = GetMouseMsg();
if(n.uMsg == WM_LBUTTONDOWN && n.x > 513 && n.x < 715 && n.y > 120 && n.y < 180)
{
closegraph();
break;
}
if(n.uMsg == WM_LBUTTONDOWN && n.x > 513 && n.x < 715 && n.y > 205 && n.y < 262)
{
loadimage(NULL, "shuoming.jpg");
getchar();
loadimage(NULL, "fongmian.jpg");
}
if(n.uMsg == WM_LBUTTONDOWN && n.x > 513 && n.x < 715 && n.y > 367 && n.y < 425)
{
closegraph();
initgraph(1200,600);
donghua();
biaoge_show();
show_book();
LOGFONT f;
getfont(&f);
f.lfHeight = 40;
strcpy(f.lfFaceName, "华文行楷");
f.lfQuality = ANTIALIASED_QUALITY;
f.lfWeight = 50;
setfont(&f);
setcolor(LIGHTBLUE);
outtextxy(750, 550, "[演示完毕，任意键返回]");
getchar();
loadimage(NULL, "fongmian.jpg");
}

}

}

void biaoge_show()
{
LOGFONT f;
getfont(&f);
f.lfHeight = 40;
strcpy(f.lfFaceName, "华文行楷");
f.lfQuality = ANTIALIASED_QUALITY;
f.lfWeight = 50;
setfont(&f);
setcolor(LIGHTGREEN);
outtextxy(0, 10, "[普里姆算法求最小生成树]");
getfont(&f);
f.lfHeight = 20;
strcpy(f.lfFaceName, "华文行楷");
f.lfQuality = ANTIALIASED_QUALITY;
f.lfWeight = 30;
setfont(&f);

int i, line_x1 = 750, line_x2 = 750, line_y1 = 50, line_y2 = 150;
setcolor(GREEN);
rectangle(750, 50, 1200, 150);
line(750, 100, 1200, 100);
for(i = 1; i <= 8; i++)
{
line_x1 = line_x1 + 50;
line_x2 = line_x2 + 50;
line(line_x1, line_y1, line_x2, line_y2);
}
setcolor(WHITE);
outtextxy(754, 70, "adjvex");
outtextxy(754, 120, "lowcost");

setcolor(GREEN);
rectangle(750, 200, 1200, 250);
line_x1 = 750, line_x2 = 750, line_y1 = 200, line_y2 = 250;
for(i = 1; i <= 8; i++)
{
line_x1 = line_x1 + 50;
line_x2 = line_x2 + 50;
line(line_x1, line_y1, line_x2, line_y2);
}
setcolor(WHITE);
outtextxy(758, 220, "vexs");
setcolor(GREEN);
rectangle(750, 300, 1200, 350);
line_x1 = 750, line_x2 = 750, line_y1 = 300, line_y2 = 350;
for(i = 1; i <= 8; i++)
{
line_x1 = line_x1 + 50;
line_x2 = line_x2 + 50;
line(line_x1, line_y1, line_x2, line_y2);
}
setcolor(WHITE);
outtextxy(768, 320, "U");
setcolor(GREEN);

}

void jiang(char C[],int a)
{
int i;
for(i = 0; i < 200; i=i+5)

{
Sleep(10);
outtextxy(a, i, C);
}
}

void donghua()
{
LOGFONT f;
getfont(&f);
f.lfHeight = 100;
strcpy(f.lfFaceName, "华文行楷");
f.lfQuality = ANTIALIASED_QUALITY;
f.lfWeight = 200;
setfont(&f);
setcolor(GREEN);
char A[20] = "普";
jiang(A,100);
setcolor(RED);
char B[20] ="里";
jiang(B,300);
setcolor(BLUE);
char C[20] ="姆";
jiang(C,500);
setcolor(YELLOW);
char D[20] ="算";
jiang(D,700);
setcolor(MAGENTA);
char E[20] ="法";
jiang(E,900);

cleardevice();

}