回复：（haroldi）无向图转换&遍历&MST
Status CreateALGraph(ALGraph *ALG,FILE *fp)//创立无向图的邻接表;
{
ArcType *p = NULL;
int i,j,w;
fscanf(fp,"%d",&ALG->VexNums);
for(i = 1;i <= ALG->VexNums;i++) //初始化;
{
ALG->Vex[i].VNode = i;
ALG->FirstArc[i] = NULL;
}
while(fscanf(fp,"%d%d%d",&i,&j,&w) == 3)
{
if(!(p = (ArcType *)malloc(sizeof(ArcType))))
{printf("\n内存溢出。");return 1;}
p->Adj = j;
p->Weight = w;
p->NextArc = ALG->FirstArc[i];
ALG->FirstArc[i] = p;
if(!(p = (ArcType *)malloc(sizeof(ArcType))))
{printf("\n内存溢出。");return 1;}
p->Adj = i; //无向邻接表,反向赋值...:-(
p->Weight = w;
p->NextArc = ALG->FirstArc[j];
ALG->FirstArc[j] = p;
}
return 0;
}
//=================================================================================
Status AL2AM(ALGraph ALG,AMGraph *AMG) //转换为图的邻接矩阵;
{
int i,j;
ArcType *p = NULL;
AMG->VexNums = ALG.VexNums;
for(i = 1;i <= AMG->VexNums;i++) //初始化;
for(j = 1;j <= AMG->VexNums;j++)
AMG->Weight[i][j] = INT_MAX;
for(i = 1;i <= ALG.VexNums;i++)
{
AMG->Vex[i] = ALG.Vex[i];
p = ALG.FirstArc[i];
while(p != NULL)
{
AMG->Weight[i][p->Adj] = p->Weight;
p = p->NextArc;
}
}
return 0;
}
//=================================================================================
Status ALG_Travers(ALGraph ALG) //图的遍历;
{
int i,Visited[MaxSize];
printf("\n 1. 图的深度遍历：");
printf("\n递 归：");
for(i = 1;i <= ALG.VexNums;i++) Visited[i] = 0;
for(i = 1;i <= ALG.VexNums;i++)
if(Visited[i] == 0) ALG_DFS(ALG,i,Visited);
printf("\n非递归：");
for(i = 1;i <= ALG.VexNums;i++) Visited[i] = 0;
for(i = 1;i <= ALG.VexNums;i++)
if(Visited[i] == 0) ALG_DFS_Uni(ALG,i,Visited);
printf("\n\n 2. 图的广度遍历：\n\t");
for(i = 1;i <= ALG.VexNums;i++) Visited[i] = 0;
for(i = 1;i <= ALG.VexNums;i++)
if(Visited[i] == 0) ALG_BFS(ALG,i,Visited);
return 0;
}
//=================================================================================
Status ALG_DFS(ALGraph ALG,int v,int *Visited) //图的深度遍历(递 归);
{
ArcType *p = NULL;
Visited[v] = 1;
printf("%2d ->",v);
p = ALG.FirstArc[v];
while(p != NULL)
{
if(Visited[p->Adj] == 0) ALG_DFS(ALG,p->Adj,Visited);
p = p->NextArc;
}
return 0;
}
//=================================================================================
Status ALG_DFS_Uni(ALGraph ALG,int v,int *Visited)//图的深度遍历(非递归);
{
ElemType Stack[MaxSize];
ArcType *p = NULL;
int top = -1;
Visited[v] = 1;
printf("%2d ->",v);
Stack[++top] = v;
while(top != -1)
{
p = ALG.FirstArc[Stack[top]];
while(p != NULL)
{
if(Visited[p->Adj] == 0)
{
Visited[p->Adj] = 1;
printf("%2d ->",p->Adj);
Stack[++top] = p->Adj;
break;
}
p = p->NextArc;
}
if(p == NULL) --top;
}
return 0;
}
//=================================================================================
Status ALG_BFS(ALGraph ALG,int v,int *Visited) //图的广度遍历;
{
int rear,front;
ElemType Queue[MaxSize];
ArcType *p = NULL;
rear = front = 0;
Visited[v] = 1;
printf("%2d ->",v);
rear =(rear + 1)%MaxSize;
Queue[rear] = v;
while(rear != front)
{
front = (front + 1)%MaxSize;
p = ALG.FirstArc[Queue[front]];
while(p != NULL)
{
if(Visited[p->Adj] == 0)
{
Visited[p->Adj] = 1;
printf("%2d ->",p->Adj);
rear =(rear + 1)%MaxSize;
Queue[rear] = p->Adj;
}
p = p->NextArc;
}
}
return 0;
}
//=================================================================================
Status CreateMST(ALGraph ALG,AMGraph AMG)//构造最小生成树;
{
MST MST_MP[MaxSize],MST_LP[MaxSize],MST_MK[MaxSize],MST_LK[MaxSize];
printf("\n\n 1. Prim普里姆(图的邻接矩阵)：\n");
AMG_Prim(AMG,MST_MP); PrintMST(MST_MP);
printf("\n\n 2. Kruskal克鲁斯卡尔(图的邻接表)：\n");
ALG_Kruskal(ALG,MST_LK); PrintMST(MST_LK);
printf("\n\n 3. Prim普里姆(图的邻接表)：\n");
ALG_Prim(ALG,MST_LP); PrintMST(MST_LP);
printf("\n\n 4. Kruskal克鲁斯卡尔(图的邻接矩阵)：\n");
AMG_Kruskal(AMG,MST_MK); PrintMST(MST_MK);
return 0;
}
//=================================================================================
Status AMG_Prim(AMGraph AMG,MST *MST_P) //Prim普里姆(邻接矩阵)，适于稠密网;
{
int i,j,k,Vex[MaxSize]; //最小生成树结点;
unsigned int min,lowcost[MaxSize]; //(由Vex[i]到i)权值;
for(i = 2;i <= AMG.VexNums;i++)
{
Vex[i] = 1; //表示V-U中各点与U(当前仅含顶点1)的关系;
lowcost[i] = AMG.Weight[1][i]; //各点对U的权值(1到各点的权值);
}
// Vex[1] = 1; //从顶点1开始遍历;
lowcost[1] = 0; //U中仅包含顶点1;
for(i = 1;i <= AMG.VexNums;i++)
{
k = i;
min = INT_MAX;
for(j = 1;j <= AMG.VexNums;j++)//得到与当前点i相临且权值最小min的顶点k;
{
if(lowcost[j] < min && lowcost[j] != 0)//找(V-U)各点对U中权值最小的;
{
min = lowcost[j];
k = j;
}
}
if(min == INT_MAX) break; //若U与V-U再没有边(不连通或V==U),退出循环;
printf("[%2d,%2d]；",Vex[k],k);
MST_P[i].head = Vex[k]; //将得到的MST各点送入MST_P;
MST_P[i].tail = k;
MST_P[i].Weight = lowcost[k];
// vex[k] = 0;
lowcost[k] = 0; //顶点k并入U;
for(j = 1;j <= AMG.VexNums;j++) //重新计算U与V-U间各个权值;
{
if(AMG.Weight[k][j] < lowcost[j])
{
Vex[j] = k;
lowcost[j] = AMG.Weight[k][j];
}
}
}
if(i == AMG.VexNums) MST_P[0].Weight = i - 1;
else MST_P[0].Weight = 0;//MST结点数如与图中总数不等,则不能生成MST或有误;
return 0;
}
//=================================================================================
Status ALG_Prim(ALGraph ALG,MST *MST_P) //(图的邻接表)Prim普里姆，适于稠密网;
{
// struct {ElemType Vex; unsigned int lowcost;}closedge[MaxSize];
int i,j,k,Vex[MaxSize];
unsigned int min,lowcost[MaxSize];
ArcType *p = NULL;
for(i = 1;i <= ALG.VexNums;i++)
{
Vex[i] = 1;
p = ALG.FirstArc[1]; //从[1]开始遍历;
while(p != NULL)
{
if(p->Adj == i) lowcost[i] = p->Weight;
p = p->NextArc;
}
}
// Vex[1] = 1;
lowcost[1] = 0;
for(i = 1;i <= ALG.VexNums;i++)
{
k = i;
min = INT_MAX;
for(j = 1;j <= ALG.VexNums;j++)
{
if(lowcost[j] < min && lowcost[j] != 0)
{
min = lowcost[j];
k = j;
}
}
if(min == INT_MAX) break; //若U与V-U再没有边(不连通或V==U),退出循环;
printf("[%2d,%2d]；",Vex[k],k);
MST_P[i].head = Vex[k]; //将得到的MST各点送入MST_P;
MST_P[i].tail = k;
MST_P[i].Weight = lowcost[k];
// vex[k] = 0;
lowcost[k] = 0; //顶点k并入U;
for(j = 1;j <= ALG.VexNums;j++)
{
p = ALG.FirstArc[k];
while(p != NULL)
{
if(p->Adj == j && p->Weight < lowcost[j])
{
lowcost[j] = p->Weight;
Vex[j] = k;
}
p = p->NextArc;
}
}
}
if(i == ALG.VexNums) MST_P[0].Weight = i - 1;
else MST_P[0].Weight = 0;//MST结点数如与图中总数不等,则不能生成MST或有误;
return 0;
}
//=================================================================================
Status FindVex(int *Vex,int v)//(Kruskal)找顶点所在树的根结点在数组Vex中的序号;
{
int t;
t = v;
while(Vex[t] > 0)
t = Vex[t];
return t;
}
//=================================================================================
Status AMG_Kruskal(AMGraph AMG,MST *MST_K)//Kruskal(邻接矩阵),适于稀疏网;
{
typedef struct{ ElemType v1,v2; unsigned int cost; }EdgeType;
EdgeType Edgs[MaxSize];
int i,j,k,vex1,vex2,Vex[MaxSize];
ElemType tv;
unsigned int tc;
k = 1;
Edgs[0].cost = 0; //记录总边数到Edgs[0].cost中;
for(i = 1;i <= AMG.VexNums;i++) //将所有两点间关系初始化到Edgs中;
{
for(j = 1;j < i;j++)
{
Edgs[k].v1 = AMG.Vex[j].VNode; //j变化快,赋予v1(较小的坐标在前);
Edgs[k].v2 = AMG.Vex[i].VNode;
Edgs[k].cost = AMG.Weight[i][j];
if(AMG.Weight[i][j] < INT_MAX) ++Edgs[0].cost;
++k;
}
}
for(i = 1;i < AMG.VexNums*AMG.VexNums;i++) //Edgs按cost值,非递减排序;
{
k = i;
for(j = i+1;j <= AMG.VexNums*AMG.VexNums;j++)
if(Edgs[k].cost > Edgs[j].cost) k = j;
if(k != i)
{
tv = Edgs[i].v1; Edgs[i].v1 = Edgs[k].v1; Edgs[k].v1 = tv;
tv = Edgs[i].v2; Edgs[i].v2 = Edgs[k].v2; Edgs[k].v2 = tv;
tc = Edgs[i].cost; Edgs[i].cost = Edgs[k].cost; Edgs[k].cost = tc;
}
}
for(i = 1;i <= AMG.VexNums;i++) Vex[i] = 0; //各点初始均独立;
i = k = 1;
while(k < AMG.VexNums)
{
vex1 = FindVex(Vex,Edgs[i].v1);
vex2 = FindVex(Vex,Edgs[i].v2);
if(vex1 != vex2)
{
Vex[vex2] = vex1;
printf("[%2d,%2d]；",Edgs[i].v1,Edgs[i].v2);
MST_K[k].head = Edgs[i].v1; //将得到的MST各点送入MST_K;
MST_K[k].tail = Edgs[i].v2;
MST_K[k].Weight = Edgs[i].cost;
if(++k >= (int)Edgs[0].cost - 1) break;
}
++i;
}
if(k - 1 == AMG.VexNums - 1) MST_K[0].Weight = AMG.VexNums - 1;
else MST_K[0].Weight = 0;
return 0;
}
//=================================================================================
Status ALG_Kruskal(ALGraph ALG,MST *MST_K)//Kruskal(邻接表),适于稀疏网;
{
typedef struct{ElemType v1,v2;unsigned int cost;} EdgeType;
int i,j,k;
ElemType Vex[MaxSize],v1,v2,tv;
unsigned int tc;
ArcType *p = NULL;
EdgeType Edge[MaxSize];
for(j = 1,i = 1;i <= ALG.VexNums;i++) //将所有两点间关系初始化到Edgs中;
{
Edge[j].v1 = ALG.Vex[i].VNode;
p = ALG.FirstArc[i];
while(p != NULL)
{
Edge[j].v2 = p->Adj;
Edge[j].cost = p->Weight;
p = p->NextArc;
Edge[j].v1 = ALG.Vex[i].VNode;
if(Edge[j].v1 < Edge[j].v2) ++j;
}
}
if(Edge[j].v1 > Edge[j].v2) Edge[0].cost = j - 1;
else Edge[0].cost = j; //记录总边数到Edgs[0].cost中;
for(i = 1;i < (int)Edge[0].cost;i++) //Edgs按cost值,非递减排序;
{
k = i;
for(j = i + 1;j <= (int)Edge[0].cost;j++)
if(Edge[k].cost > Edge[j].cost) k = j;
if(k != i)
{
tv = Edge[i].v1; Edge[i].v1 = Edge[k].v1; Edge[k].v1 = tv;
tv = Edge[i].v2; Edge[i].v2 = Edge[k].v2; Edge[k].v2 = tv;
tc = Edge[i].cost; Edge[i].cost = Edge[k].cost; Edge[k].cost = tc;
}
}
for(i = 1;i <= (int)Edge[0].cost;i++) Vex[i] = 0;
for(k = 1,i = 1;i <= (int)Edge[0].cost;i++)
{
v1 = FindVex(Vex,Edge[i].v1);
v2 = FindVex(Vex,Edge[i].v2);
if(v1 != v2)
{
Vex[v2] = v1;
printf("[%2d,%2d]；",Edge[i].v1,Edge[i].v2);
MST_K[k].head = Edge[i].v1;
MST_K[k].tail = Edge[i].v2;
MST_K[k].Weight = Edge[i].cost;
++k;
}
}
if(k - 1 == ALG.VexNums - 1) MST_K[0].Weight = ALG.VexNums - 1;
else MST_K[0].Weight = 0;
return 0;
}
//================================================================================
Status Prn_ALGraph(ALGraph ALG) //输出邻接表;
{
int i;
ArcType *p = NULL;
for(i = 1;i <= ALG.VexNums;i++)
{
printf("\n %2d ==> ",i);
p = ALG.FirstArc[i];
while(p != NULL)
{
printf("%2d(%3d) ->",p->Adj,p->Weight);
p = p->NextArc;
}
}
printf("\n");
return 0;
}
//=================================================================================
Status Prn_AMGraph(AMGraph AMG) //输出邻接矩阵;
{
int i,j;
for(i = 1;i <= AMG.VexNums;i++)
{
printf("\n\t");
for(j = 1;j <= AMG.VexNums;j++)
{
if(AMG.Weight[i][j] < INT_MAX) printf(" %3d ",AMG.Weight[i][j]);
else printf(" ∞ ");
}
printf("\n");
}
return 0;
}
//=================================================================================
Status PrintMST(MST *MT) //输出最小生成树;
{
unsigned int i = 1;
if(MT[0].Weight == 0) {printf("\n\t不能生成最小生成树。\n");return 1;}
printf("\n\t边 信 息\t权 值");
for(i = 1;i <= MT[0].Weight;i++)
printf("\n\t(%2d,%2d)\t\t[%4d]",MT[i].head,MT[i].tail,MT[i].Weight);
return 0;
}
