题目：求无向连通图的生成树
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 );
}
}
看看这个吧 哈哈
///////图的邻接表表示与运算
#include<stdio.h>
#include<stdlib.h>
#define MaxNode 256
typedef char Element;
////////边结点声明
struct arctype
{
int adjvertex;
int weight;
struct arctype *nextarc;
};
///////顶点结点声明
typedef struct
{
Element vertex;
struct arctype *firstarc;
}vertextype;
//////找寻顶点V在图中的位置（序号）
int LocVertex(vertextype graph[],int v,int n);
//////建造图graph
void Creat_Graph(vertextype graph[],int n,int e);
//////深度搜索图
void Depth_Traver(vertextype graph[],int v);
void Dfs(vertextype graph[],int v,int visit[]);
/////输出图graph
void Show(vertextype graph[],int n);
int main()
{
int n,e;
vertextype graph[MaxNode];
printf("输入顶点数和边数用空格间隔：");
scanf("%d %d",&n,&e);
getchar();
Creat_Graph(graph,n,e);
Show(graph,n);
Depth_Traver(graph,n);
}
//////建立图graph
void Creat_Graph(vertextype graph[],int n,int e)
{
int i,j,k;
int v1,v2;
struct arctype *q=NULL;
struct arctype *p=NULL;
printf("输入图中顶点的数据：");
for(k=0;k<n;k++)
{
scanf("%c",&graph[k].vertex);
getchar();
graph[k].firstarc = NULL;
}
printf("输入图中的各边，次序为弧尾编号，弧头编号：\n");
for(k=0;k<e;k++)
{
scanf("%d %d",&v1,&v2);
i = LocVertex(graph,v1-1,n);
j = LocVertex(graph,v2-1,n);
q = (struct arctype *)malloc(sizeof(struct arctype));
q->nextarc = graph[i].firstarc;////新节点插入顶点结点
q->adjvertex = v2-1; /////
graph[i].firstarc = q;
p = (struct arctype *)malloc(sizeof(struct arctype));
p->nextarc = graph[j].firstarc;////新节点插入顶点结点
p->adjvertex = v1-1; /////
graph[j].firstarc = p;
}
}
int LocVertex(vertextype graph[],int v,int n)
{
int k;
for(k=0;k<n;k++)
{
if(graph[k].vertex == graph[v].vertex)
return k;
}
return -1;
}
///////深度搜索图graph
void Depth_Traver(vertextype graph[],int n)
{
int v,visit[MaxNode];
for(v=0;v<n;v++)
visit[v] = 0;
Dfs(graph,0,visit);
printf("\n");
}
void Dfs(vertextype graph[],int v,int visit[])
{
int w;
struct arctype *p;
visit[v] = 1;
printf("%5c",graph[v].vertex);
p = graph[v].firstarc;
w = p->adjvertex;
while(p != NULL)
{
if(visit[w] == 0)
Dfs(graph,w,visit);
p = p->nextarc;
if(p!=NULL)
w = p->adjvertex;
}
}
//////输出图graph
void Show(vertextype graph[],int n)
{
int i,v2;
char v1;
struct arctype *p=NULL,*q=NULL;
printf("图的邻接表结构为：\n");
for(i=0;i<n;i++)
{
printf("%d ",i); //////输出顶点序号
v1 = graph[i].vertex;
printf("Vertex:%c",v1); /////输出顶点信息
p = graph[i].firstarc;
while(p != NULL) ///////输出结点
{
v2 = p->adjvertex;
printf("-->%d ",v2);//////结点序号
p = p->nextarc;
}
printf("\n");
}
}