实验项目名称：图的操作的实现
实验目的与要求:
1.基础知识:掌握数据结构中图的相关知识;掌握C或VC+ +语言中程序设计的方法.
2.参考教材相关算法，完成以下程序功能:
(1)利用邻接矩阵完成建图(能力好的同学可以选用邻接表结构建图) ;
(2)利用广度优先搜索或深度优先搜索遍历算法编写对已建图的遍历工作;
(3)打印输出图的顶点表和邻接矩阵(若选作邻接表，则打印邻接表的相应元素值)
(4)实验性质:验证性(4学时)
说明:程序包含的主要函数:主函数、建图、搜索遍历、打印图、操作菜单函数和以上函数中的嵌套子函数，以及主函数，另外添加相关注释。
注意:在主函数调用子函数流程中体现先建图后遍历和其它操作的条件控制，即在调用除建图算法以外的其它所有算法前，先判断图是否已经建立，若没建图，只能先建图，不能做其它操作。由于实验中图采用邻接矩阵结构，该结构在参考代码中被设计成静态二维数组，因此可以考虑使用状态开关变量flag的方式来判断建图是否完成，即没建图前flag=0,建图后就置flag=1,在其它运算前判断flag==1时才可以操作。
图源代码：
#include<stdio.h>
#include<limits.h>
#include<windows.h>
#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20
#define OK 1
typedef int Status;
typedef enum{DG,DN,UDG,UDN}GraphKind;
typedef int VRType;
typedef char VertexType;
typedef char* InfoType;
typedef struct ArcCell
{
VRType adj;//顶点间关系，无权图取1或0;有权图取权值类型
InfoType *info;//该弧相关信息的指针
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
VertexType vexs[MAX_VERTEX_NUM];//顶点表，用一维向量即可（n）
AdjMatrix arcs; //邻接矩阵n*n
int vexnum,arcnum;//顶点总数n，弧(边)总数e
GraphKind kind;//图的种类标志
}MGraph;
boolean visited[MAX_VERTEX_NUM];
Status(*VisitFunc)(MGraph G,int v);
Status LocateVex(MGraph G,char v)//定位操作：对顶点v定位，返回该顶点在数组的下标，若找不到返回-1
{
for(int i=0;i<G.vexnum;i++)
{
if(v==G.vexs[i])
return i;
}
return -1;
}
Status CreateUDN(MGraph &G)//采用数组(邻接矩阵)表示法，构造无向网。
{
G.kind=UDN;
printf("输入顶点个数和边数(以“,”作分界)：\n");
scanf("%d,%d",&G.vexnum,&G.arcnum);//输入顶点个数和边数
while(G.vexnum>MAX_VERTEX_NUM)
{
printf("最大顶点数为7，请重新输入");
scanf("%d,%d",&G.vexnum,&G.arcnum);
}
printf("\n请依次输入向量值\n");
for(int i=0;i<G.vexnum;i++)
{
fflush(stdin);
printf("第%d个:",i+1);
scanf("%c",&G.vexs[i]);
}
for(int i=0;i<G.vexnum;i++)
{//初始化邻接矩阵
for(int j=0;j<G.vexnum;j++)
{
G.arcs[i][j].adj=INFINITY;
G.arcs[i][j].info=NULL;//该弧相关信息的指针，可在实验中删除？
}
}
char front,rear;
int values;
printf("\n输入一条边依附的两个顶点及权值(以“,”作分界)\n");
for(int i=0;i<G.arcnum;i++){
printf("第%d条：",i+1);
fflush(stdin);
scanf("%c,%c,%d",&rear,&front,&values);
int m,n;
m= LocateVex (G,rear);
n= LocateVex (G,front);
if(m==-1||n==-1){
printf("输入顶点或不在此图中，请重新输入\n");
i--;
continue;
}
G.arcs[m][n].adj=values;
G.arcs[n][m].adj=values;
}
return OK;
}
Status printArcs(MGraph G)//打印图
{
int i;
printf("#");
for(i=0;i<G.vexnum;i++)
{
printf(" %c",G.vexs[i]);
}
for(i=0;i<G.vexnum;i++)
{
printf("\n%c",G.vexs[i]);
for(int j=0;j<G.vexnum;j++)
{
if(G.arcs[i][j].adj==INFINITY)
printf(" #");
else
printf(" %d",G.arcs[i][j].adj);
}
}
printf("\n");
return OK;
}
Status FirstAdjVex(MGraph G,int v)//查找与顶点v的第一个邻接点，找到后立刻返回下标，
{
for(int i=1;i<G.vexnum;i++)
{
if(G.arcs[v][i].adj!=INFINITY)
return i;
}
return -1;
}
Status NextAdjVex(MGraph G,int v,int w)//查找与顶点v的w邻接点的下一个邻接点，找到后立刻返回下标，
{
for(int i=w+1;i<G.vexnum;i++)
{
if(G.arcs[v][i].adj!=INFINITY)
return i;
}
return -1;
}
Status DFS(MGraph G,int v)//从第v个顶点出发递归深度优先遍历图G
{
visited[v]=TRUE;
VisitFunc(G,v);
for(int w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
{
if(!visited[w])
DFS(G,w);
}
return OK;
}
Status DFSTraverse(MGraph G,Status(*Visit)(MGraph G,int v))//深度优先遍历
{
VisitFunc = Visit;
int v;
for(v=0;v<G.vexnum;v++)
visited[v]=false;
for(v=0;v<G.vexnum;v++)
if(!visited[v])
DFS(G,v);
printf("\n");
return OK;
}
Status printAdjVex(MGraph G,int v)//访问顶点v输出
{
printf("%c ",G.vexs[v]);
return OK;
}
Status DestroyGraph(MGraph &G)//销毁图
{
G.vexnum=NULL;
G.arcnum=NULL;
return OK;
}
Status OperateMenu(int num)//菜单函数
{
printf("------****操作菜单****------\n");
printf("------ 0 退出系统\n");
printf("------ 1 建图\n");
printf("------ 2 打印图\n");
printf("------ 3 深度遍历\n");
printf("------ 4 销毁图\n");
printf("------ 请选择你所需要的操作\n");
scanf("%d",&num);
return num;
}
main()
{
MGraph G;
int flag=0;
int num=-1;
while(num!=0)
{
{
num=OperateMenu(num);
}
switch(num)
{
case 1:
flag=1;
CreateUDN(G);break;
case 2:
if(flag==0)
{printf("图不存在\n");break;}
else
printArcs(G);break;
case 3:
if(flag==0)
{printf("图不存在\n");break;}
else
DFSTraverse(G,printAdjVex);break;
case 4:
if(flag==0)
{printf("图不存在\n");break;}
else
{DestroyGraph(G);
flag=0；
printf("已销毁图\n");}break;
}
}
}