데이터 구조 - 그림 - 최소 생 성 트 리Prim
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXEDGE 20
#define MAXVEX 20
#define INFINITY 65535
typedef int Status; /* Status , , OK */
typedef struct
{
int arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}MGraph;
void CreateMGraph(MGraph *G)/* */
{
int i, j;
/* printf(" :"); */
G->numEdges=15;
G->numVertexes=9;
for (i = 0; i < G->numVertexes; i++)/* */
{
for ( j = 0; j < G->numVertexes; j++)
{
if (i==j)
G->arc[i][j]=0;
else
G->arc[i][j] = G->arc[j][i] = INFINITY;
}
}
G->arc[0][1]=10;
G->arc[0][5]=11;
G->arc[1][2]=18;
G->arc[1][8]=12;
G->arc[1][6]=16;
G->arc[2][8]=8;
G->arc[2][3]=22;
G->arc[3][8]=21;
G->arc[3][6]=24;
G->arc[3][7]=16;
G->arc[3][4]=20;
G->arc[4][7]=7;
G->arc[4][5]=26;
G->arc[5][6]=17;
G->arc[6][7]=19;
for(i = 0; i < G->numVertexes; i++)
{
for(j = i; j < G->numVertexes; j++)
{
G->arc[j][i] =G->arc[i][j];
}
}
}
/* Prim */
void MiniSpanTree_Prim(MGraph G)
{
int min, i, j, k;
int adjvex[MAXVEX]; /* */
int lowcost[MAXVEX]; /* */
lowcost[0] = 0;/* 0, v0 */
/* lowcost 0, */
adjvex[0] = 0; /* 0 */
for(i = 1; i < G.numVertexes; i++) /* 0 */
{
lowcost[i] = G.arc[0][i]; /* v0 */
adjvex[i] = 0; /* v0 */
}
for(i = 1; i < G.numVertexes; i++)
{
min = INFINITY; /* ∞, */
/* 32767、65535 */
j = 1;k = 0;
while(j < G.numVertexes) /* */
{
if(lowcost[j]!=0 && lowcost[j] < min)/* 0 min */
{
min = lowcost[j]; /* */
k = j; /* k */
}
j++;
}
printf("(%d, %d)
", adjvex[k], k);/* */
lowcost[k] = 0;/* 0, */
for(j = 1; j < G.numVertexes; j++) /* */
{
if(lowcost[j]!=0 && G.arc[k][j] < lowcost[j])
{/* k */
lowcost[j] = G.arc[k][j];/* lowcost */
adjvex[j] = k; /* k adjvex */
}
}
}
}
int main(void)
{
MGraph G;
CreateMGraph(&G);
MiniSpanTree_Prim(G);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.