图的应用

答案:2 悬赏:80 手机版

解决时间 2021-01-23 02:28

提问者网友：温柔港
2021-01-22 04:22

图的应用

最佳答案

五星知识达人网友：煞尾
2021-01-22 05:30

//采纳吧。。。费了不少时间
#include
#include
#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");
}

全部回答

1楼网友：你可爱的野爹
2021-01-22 05:38

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

我要举报

如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！