Question

图的应用

本实验的目的是使学生深入了解图的定义及其存储结构，掌握复合数据结构的定义及说明，理解图的四大类存储结构之间的区别；并利用图的邻接表存储结构，对一个无向图进行深度优先搜索。
实验要求：
有必要的类型说明，并完成下述函数功能：
① bool visited[MAX_VERTEX_NUM]; //全局变量——访问标志数组
② void CreateGraph(Graph &); //生成图的邻接表
③ void DFS(Graph G, int v) //从第v个顶点出发递归地深度遍历图G
④ void DFSTraverse(Graph G) //深度优先搜索遍历图
⑤ int FirstAdjVex(Graph G, int v) //求图中某一顶点的第一个邻接顶点
⑥ int NextAdjVex(Graph G, int v, int w) //求某一顶点的下一个邻接顶点
在主函数main( )中调用各个子函数完成基本操作。
[实现提示]
首先建立图的邻接表存储结构，然后利用算法对图进行深度优先搜索DFSTraverse，过程中，需要求某个顶点的邻接点信息。
[测试数据]
由学生自己确定，注意边界数据。
程序检查时，由老师提供图的定义。
提示：
存储结构定义如下：
typedef struct ArcNode
{ int adjvex; //该边所指向的顶点的位置
struct ArcNode *nextarc; //指向下一条边的指针
}ArcNode; //边结点
typedef struct
{ ArcNode * AdjList[MAX_VERTEX_NUM]; //指向第一条依附该顶点的边的指针
/*这里的AdjList[ ]数组元素中省略了顶点的值，把顶点的位置，即数组下标当作顶点信息；只记录了指向ArcNode类型的指针，即指向弧头顶点的位置信息。*/
/*你也可以自己定义AdjList[ ]数组时，添加顶点信息 char data; */
int vexnum, arcnum; //图的当前顶点和弧数
}Graph;

构造图的邻接表存储结构函数如下：
void CreateGraph(Graph &G)
{//构造邻接表结构的图G
int i;
int start,end; //记录弧尾、弧头信息，或边的两个邻接点信息
ArcNode *s;
printf("请输入图的顶点数和边数:");
scanf("%d,%d",&G.vexnum,&G.arcnum); //输入图的顶点数和边数
for(i=1;i<=G.vexnum;i++) G.AdjList[i]=NULL; //初始化指针数组
printf("请输入各边, 格式：顶点,顶点\n");
for(i=1;i<=G.arcnum;i++)
{scanf("%d,%d",&start,&end); //输入边的起点和终点
s=(ArcNode *)malloc(sizeof(ArcNode)); //生成一个边结点
s->nextarc=G.AdjList[start]; //插入到邻接表中，注意此处为逆向插入到单链表中
s->adjvex=end;
G.AdjList[start]=s;
//无向图，注意是对称插入结点
s=(ArcNode *)malloc(sizeof(ArcNode));
s->nextarc=G.AdjList[end];
s->adjvex=start;
G.AdjList[end]=s;
}
}
求某一顶点的下一个邻接顶点的函数参考如下代码：
int NextAdjVex(Graph G, int v, int w)
{//在图G中寻找第v个顶点的相对于w的下一个邻接顶点
ArcNode *p;
p=G.AdjList[v];
while(p->adjvex!=w)
p=p->nextarc; //在顶点v的弧链中找到顶点w
if(p->nextarc= =NULL)
return 0; //若已是最后一个顶点，返回0
else
return(p->nextarc->adjvex); //返回下一个邻接顶点的序号
}

Answer 1

//采纳吧。。。费了不少时间
#include<stdio.h>
#include<stdlib.h>
#define MAX_VERTEX_NUM 20
bool visited[MAX_VERTEX_NUM];
typedef struct ArcNode{
int adjvex; //该边所指向的顶点的位置
struct ArcNode *nextarc; //指向下一条边的指针
}ArcNode;
typedef struct{
ArcNode * AdjList[MAX_VERTEX_NUM]; //指向第一条依附该顶点的边的指针
int vexnum, arcnum; //图的当前顶点和弧数
}Graph;
void CreateGraph(Graph &G)
{//构造邻接表结构的图G
int i;
int start,end; //记录弧尾、弧头信息，或边的两个邻接点信息
ArcNode *s;
printf("请输入图的顶点数和边数:");
scanf("%d,%d",&G.vexnum,&G.arcnum); //输入图的顶点数和边数
for(i=1;i<=G.vexnum;i++) G.AdjList[i]=NULL; //初始化指针数组
printf("请输入各边, 格式：顶点,顶点\n");
for(i=1;i<=G.arcnum;i++)
{scanf("%d,%d",&start,&end); //输入边的起点和终点
s=(ArcNode *)malloc(sizeof(ArcNode)); //生成一个边结点
s->nextarc=G.AdjList[start]; //插入到邻接表中，注意此处为逆向插入到单链表中
s->adjvex=end;
G.AdjList[start]=s;
//无向图，注意是对称插入结点
s=(ArcNode *)malloc(sizeof(ArcNode));
s->nextarc=G.AdjList[end];
s->adjvex=start;
G.AdjList[end]=s;
}
}
int FirstAdjVex(Graph G, int v)
{
ArcNode *p;
if(v>=1 && v<=G.vexnum)
{
p=G.AdjList[v];
if(p->nextarc==NULL)
return 0;
else
return (p->nextarc->adjvex);
}
return -1;
}
int NextAdjVex(Graph G, int v, int w)
{//在图G中寻找第v个顶点的相对于w的下一个邻接顶点
ArcNode *p;
if(v>=1 && v<=G.vexnum && w>=1 && w<=G.vexnum)
{
p=G.AdjList[v];
while(p->adjvex!=w)
p=p->nextarc; //在顶点v的弧链中找到顶点w
if(p->nextarc!=NULL)
return 0; //若已是最后一个顶点，返回0
else
return(p->nextarc->adjvex); //返回下一个邻接顶点的序号
}
return -1;
}
void DFS(Graph G, int v)
{
int i,w;
ArcNode *p;
visited[v]=1;
printf("%d ",v); //访问第v个顶点
p=G.AdjList[v];
while (p!=NULL)
{
w=p->adjvex;
if(visited[w]==0)
DFS(G,w);
p=p->nextarc;
}
}
void DFSTravel(Graph G)
{
int i,w,v=1;
ArcNode *p;
visited[v]=1;
printf("%d ",v); //访问第v个顶点
p=G.AdjList[v];
while (p!=NULL)
{
w=p->adjvex;
if(visited[w]==0)
DFS(G,w);
p=p->nextarc;
}
}
void main()
{
int i,v;
Graph G;
CreateGraph(G);
printf("请输入深度优先遍历开始点的名：");
scanf("%d",&v);
for(i=1;i<=G.vexnum;i++)
visited[i]=0;
DFS(G,v);
printf("\n");
for(i=1;i<=G.vexnum;i++)
visited[i]=0;
DFSTravel(G);
printf("\n");
}

Answer 2

你们要求是什么？能不能用C++来写？