题目：求无向连通图的生成树
1.问题描述
求无向连通图的一棵生成树。
2.基本要求
(1)采用邻接矩阵存储；
(2)求深度优先生成树；
(3)输出该生成树的每一条边。
3.设计思想
在一个连通无向图G=(V,E)中，如果从任一个顶点开始进行深度优先遍历，必定将边集E分成两个集合T和B，其中T是遍历过程中经历的边的集合，B是剩余的边的集合。显然，边集T和图G中所有顶点一起构成连通图G的一棵生成树。因此，修改7.4.1节中邻接矩阵类MGraph的深度优先遍历算法，输出遍历所经过的边，算法如下：
深度优先生成树算法DFSTraverse
template <class T>
void MGraph :: DFSTraverse ( int v)
{
visited [v] =1;
for ( j=0; j<vertexNum; j++)
if (arc[ v ][ j ] = = 1 && visited[ j ] = = 0) {
cout<<“（”<<v<<j<<“）”；
DFSTraverse( j );
}
}
不知道你要的是不是这个
完整实现如下：
#define INFINITY 65535
typedef int status;
# include <stdio.h>
# include <stdlib.h>
# include <conio.h>
# include "string.h"
# define maxlen 10
typedef struct
{
char vexs[maxlen][maxlen];
int vexnum,arcnum;
int arcs[maxlen][maxlen];
}graph;
//定位输入节点的名称
int LocateVex(graph G,char u[maxlen])
{
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(u,G.vexs[i])==0)
return i;
return -1;
}
void prim(graph &g)
{
int i,j,k,min,w,flag;
int lowcost[maxlen];
int closet[maxlen];
char va[maxlen],vb[maxlen];
//初始化邻接矩阵
//printf("请输入顶点数和边数：\n");
//scanf("%d%d",&g.vexnum,&g.arcnum);
g.vexnum=6;
g.arcnum=10;
printf("请输入顶点信息(我们这里指名字)：\n");
for(int j=0;j<g.vexnum;j++)
scanf("%s",g.vexs[j]);
for(i=0;i<g.vexnum;++i)
for(j=0;j<g.vexnum;++j)//初始化邻接矩阵
{
g.arcs[i][j]=INFINITY; //任意两个顶点间距离为无穷大。
}//for
g.arcs[0][1]=6;
g.arcs[1][0]=6;
g.arcs[0][2]=1;
g.arcs[2][0]=1;
g.arcs[0][3]=5;
g.arcs[3][0]=5;
g.arcs[1][2]=5;
g.arcs[2][1]=5;
g.arcs[1][4]=3;
g.arcs[4][1]=3;
g.arcs[2][3]=5;
g.arcs[3][2]=5;
g.arcs[2][4]=6;
g.arcs[4][2]=6;
g.arcs[2][5]=4;
g.arcs[5][2]=4;
g.arcs[3][5]=2;
g.arcs[5][3]=2;
g.arcs[4][5]=6;
g.arcs[5][4]=6;
printf("最小生成树的边为:\n");
for(i=1;i<g.vexnum;i++)
{
lowcost[i]=g.arcs[0][i];
closet[i]=1;
}
closet[0]=0; //初始v1是属于集合U的，即设它是最小生成树中节点的一员
j=1; //V是顶点集合
for(i=1;i<g.vexnum;i++)
{
min=lowcost[j];
k=i;
for(j=1;j<g.vexnum;j++)
if(lowcost[j]<min&&closet[j]!=0)
{
min=lowcost[j];
k=j; //记录当前要加入集合U的节点号
}//if
if(i==1) flag=0;
else flag=closet[k]; //还没有加入集合U的节点的closet[]值是
//记录了上一次加入集合U的节点号
closet[k]=0; //将刚刚找到的点加入到集合U中
printf("(%s,%s),",g.vexs[k],g.vexs[flag]);//输出刚刚找到的最小生成树树枝
for(j=1;j<g.vexnum;j++)
if(g.arcs[k][j]<lowcost[j]&&closet[j]!=0)
{
lowcost[j]=g.arcs[k][j]; //更新lowcost[]的值，且在还没有加入U集合的
//的closet[]中记录刚刚加入U集合的节点号以备
//下一循环中输出用
closet[j]=k;
}
}
}
int main()
{
graph g;
prim(g);
}