Question

谁帮忙写下这个程序呀：建立无向图的邻接矩阵存储；对已经建立的无向图进行深度优先和广度优先遍历操作。

Answer 1

/* Graph.h */
#include<stdio.h>
#include<malloc.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>
#define ERROR 0
#define OK 1
#define MAX_VERTEX_NUM 20 //定义最大值
#define INFINITY 32768 //定义极大值
#define MAX_INFO 20
typedefint VerType; //定义新的类型
typedefint InfoType;
typedefchar VertexType;
typedefenum
{DG,DN,UDG,UDN}GraphKind;//有向图,有向网,无向图,无向网
typedefstruct ArcCell
{//邻接矩阵表示法的各个数据结构
VrType adj; // 顶点关系类型。对无权图，用或表示相邻否；对带权图，则为权值类型。
InfoType *info; // 该弧相关信息的指针
} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedefstruct
{
VertexType vertex[MAX_VERTEX_NUM]; // 顶点向量
AdjMatrix arcs; // 邻接矩阵
int vexnum, arcnum; // 图的当前顶点数和弧(边)数
GraphKind kind; // 图的种类标志
} MGraph;
typedefstruct
{//设置栈
int elem1[MAX_VERTEX_NUM];
int top;
}SeqStack;
int LocateVertex(MGraph G,VertexType v);
void CreateUDG(MGraph &G);
void CreateUDN(MGraph &G);
void DepthFirstSearch1(MGraph G);
void BreadthFirstSearch1(MGraph G);
int CreateGraph(MGraph &G);
void Display(MGraph G);

/* Graph.cpp */
int LocateVertex(MGraph G,VertexType v)
{//用于返回输弧端点所表示的数值
int j=0,k;
for(k=0;k<G.vexnum;++k)
if(G.vertex[k]==v)
{j=k;break;}
return(j);
}
void CreateUDG(MGraph &G)
{ // 采用数组(邻接矩阵)表示法,构造无向图
int i,j,k,IncInfo;
//i，j，k为计数器,IncInfo为标志符
char ch; //用于吃掉多余的字符
VertexType v1,v2; //用于放置输入的弧的两个顶点
printf("请输入无向图G的顶点数,边数,弧是否含相关信息（是：，否：）: \n");
scanf("%d,%d,%d",&G.vexnum,&G.arcnum,&IncInfo);
ch=getchar(); //用于吃掉回车
printf("请输入%d个顶点的值(1个字符，空格隔开):\n",G.vexnum);
for(i=0;i<G.vexnum;++i) // 构造顶点向量
{
scanf("%c",&G.vertex[i]);ch=getchar();
}
printf("请输入%d条边的顶点顶点(以空格作为间隔): \n",G.arcnum);
for(i=0;i<G.vexnum;++i) // 初始化邻接矩阵
for(j=0;j<G.vexnum;++j)
{
G.arcs[i][j].adj=0;
G.arcs[i][j].info=NULL; // {adj,info}
}
for(k=0;k<G.arcnum;++k)
{
scanf("%c %c",&v1,&v2);
ch=getchar();// ch吃掉回车符
i=LocateVertex(G,v1); j=LocateVertex(G,v2);
if(IncInfo)scanf("%d",&G.arcs[i][j].info);
G.arcs[i][j].adj=G.arcs[j][i].adj=1; // 置<v1,v2>的对称弧<v2,v1>
}
}//CreateUDG
void CreateUDN(MGraph &G)
{ // 采用数组(邻接矩阵)表示法,构造无向网
int i,j,k,w,IncInfo;
//i，j，k为计数器，w用于放置权值,IncInfo为标志符
char ch;
VertexType v1,v2; //用于放置输入的弧的两个顶点
printf("请输入无向图G的顶点数,边数,弧是否含相关信息（是：，否：）:\n ");
scanf("%d,%d,%d",&G.vexnum,&G.arcnum,&IncInfo);
ch=getchar();
printf("请输入%d个顶点的值(1个字符，空格隔开):\n",G.vexnum);
for(i=0;i<G.vexnum;++i) // 构造顶点向量
{
scanf("%c",&G.vertex[i]);ch=getchar();
}
printf("请输入%d条边的顶点顶点(以空格作为间隔): \n",G.arcnum);
for(i=0;i<G.vexnum;++i) // 初始化邻接矩阵
for(j=0;j<G.vexnum;++j)
{
G.arcs[i][j].adj=0;
G.arcs[i][j].info=NULL; //{adj,info}
}
for(k=0;k<G.arcnum;++k)
{
scanf("%c %c",&v1,&v2);
ch=getchar();
printf("请输入该边的权值: ");
scanf("%d",&w);
ch=getchar();
i=LocateVertex(G,v1);
j=LocateVertex(G,v2);
G.arcs[i][j].adj=w;
if(IncInfo)scanf("%d",&G.arcs[i][j].info);
G.arcs[i][j]=G.arcs[j][i]; // 置<v1,v2>的对称弧<v2,v1>
}
}//CreateUDN

void DepthFirstSearch1(MGraph G)
{//无向图、无向网深度优先遍历
int i,j,k,visited[20],t=1,a=1; //i,j,k为计数器，visited[20]为标志符用于表示是否已经访问过
SeqStack p;
for(i=0;i<G.vexnum;++i) //初始化标志符
visited[i]=0;
visited[0]=1; //规定以第一个字符开始遍历
printf("深度优先遍历开始：\n");
k=0;i=0;
printf("%c ",G.vertex[0]);
while(i<G.vexnum)
{//不断以行循环在遇到符合条件时打印，每打印出一个就让t加，把合适的值用栈来表示，把指针指向新的项
for(j=0;j<G.vexnum;++j)
{
if(G.arcs[i][j].adj!=0&&G.arcs[i][j].adj!=INFINITY&&visited[j]==0)
{
printf("%c ",G.vertex[j]);
visited[j]=1;
p.elem1[k]=i;
p.top=k;
k++;i++;a++;t++;
break;
}
}
if(j==G.vexnum)
{//当在某一行无法找到合适值时，输出栈内的值，返回上一行重新开始循环
i=p.elem1[p.top];
p.top--;
k--;
}
if(t==G.vexnum)break; //当全部的定点都打印出来了就退出循环
}
printf("\n");
}
void BreadthFirstSearch1(MGraph G)
{//无向图、无向网广度优先遍历
int i,j,k,visited[20],t=1; //i,j为计数器，visited[20]为标志符用于表示是否已经访问过
SeqStack p;
for(i=0;i<G.vexnum;++i) //初始化标志符
visited[i]=0;
visited[0]=1; //规定以第一个字符开始遍历
printf("广度优先遍历开始：\n");
k=0;i=0;
printf("%c ",G.vertex[0]);
while(i<G.vexnum)
{
for(j=0;j<G.vexnum;++j)//不断以行循环在遇到符合条件时打印，每打印出一个就让t加，把指针指向新的项
{
if(G.arcs[i][j].adj!=0&&G.arcs[i][j].adj!=INFINITY&&visited[j]==0)
{
printf("%c ",G.vertex[j]);
visited[j]=1;
p.elem1[k]=i;
p.top=k;
k++;
t++;
}
}
i++; //换行，重新开始循环
if(t==G.vexnum)break;
}
printf("\n");
}
int CreateGraph(MGraph &G)
{ //构造图
printf("请输入要构造的图的类型(有向图:0,有向网:1,无向图:2,无向网:3):\n");
scanf ("%d",&G.kind);
switch(G.kind)
{
case 2: CreateUDG(G);break;
case 3: CreateUDN(G);break;
default: return ERROR;
}
}//CreateGraph

void Display(MGraph G)
{//输出图的邻接矩阵
int i,j;
printf("该图的邻接矩阵为：\n");
for(i=0;i<G.vexnum;++i)
{for(j=0;j<G.vexnum;++j)<br> {<br> printf("%d ",G.arcs[i][j].adj);<br> }
printf("\n");
}
}

/* main.cpp */
void main()
{
int i;
MGraph G;
CreateGraph(G);
DepthFirstSearch1(G);
BreadthFirstSearch1(G);
Display(G);
scanf("%d",&i);
}