void Graph(){ int n; do{ printf("\n"); printf("图的基本操作及应用*\n"); printf("* 1 创建(邻接矩阵/邻接表) \n"); printf(" 2 深度优先遍历 \n"); printf(" 3 广度优先遍历 \n"); printf(" 4 找第一个邻接点 \n"); printf(" 5 找下一个邻接点 \n"); printf(" 6 应用 \n"); printf(" 7 退出 \n"); printf("**************************************************\n"); printf("请选择:"); scanf("%d",&n); switch(n){ case 1: printf("---------创建(邻接矩阵/邻接表)-------");break; case 2: printf("---------深度优先遍历-------");break; case 3: printf("---------广度优先遍历-------");break; case 4: printf("---------找第一个邻接点-------");break; case 5: printf("---------找下一个邻接点-------");break; case 6: printf("---------应用-------");break; case 7:break; default: printf("ERROR!");break; } }while(n!=7); }完善这段代码使之能够成功实现创建(邻接矩阵/邻接表)深度优先遍历广度优先遍历找第一个邻接点-找下一个邻接点-并且能够运行且功能完整
时间: 2023-07-23 11:42:34 浏览: 85
用栈求解n皇后问题 n皇后问题(C语言实现)
这段代码只是一个菜单,需要在每个选项中添加相应的函数调用才能实现相应的功能。以下是完整代码:
```c
#include<stdio.h>
#include<stdlib.h>
#define MAXV 100 //最大顶点数
//邻接矩阵存储结构
typedef struct{
int vexs[MAXV]; //顶点数组
int arc[MAXV][MAXV]; //邻接矩阵
int vexnum, arcnum; //顶点数和边数
}MGraph;
//邻接表存储结构
typedef struct ArcNode{
int adjvex; //邻接点在顶点数组中的位置
struct ArcNode *next; //下一个邻接点指针
}ArcNode;
typedef struct VNode{
int data; //顶点数据
ArcNode *first; //第一个邻接点指针
}VNode, AdjList[MAXV];
typedef struct{
AdjList vertices; //邻接表数组
int vexnum, arcnum; //顶点数和边数
}ALGraph;
//函数声明
void CreateMGraph(MGraph *G); //创建邻接矩阵
void CreateALGraph(ALGraph *G); //创建邻接表
void DFS(MGraph G, int v, int visited[]); //深度优先遍历邻接矩阵
void BFS(ALGraph G, int v, int visited[]); //广度优先遍历邻接表
int FirstAdjVex(MGraph G, int v); //找第一个邻接点
int NextAdjVex(MGraph G, int v, int w); //找下一个邻接点
void Graph(); //菜单函数
int main(){
Graph();
return 0;
}
void CreateMGraph(MGraph *G){
int i, j, k, w;
printf("请输入顶点数和边数:");
scanf("%d%d", &G->vexnum, &G->arcnum);
printf("请输入顶点数据:");
for(i = 0; i < G->vexnum; i++){
scanf("%d", &G->vexs[i]);
}
for(i = 0; i < G->vexnum; i++){
for(j = 0; j < G->vexnum; j++){
G->arc[i][j] = 0; //初始化邻接矩阵
}
}
printf("请输入边的信息(起点 终点 权值):");
for(k = 0; k < G->arcnum; k++){
scanf("%d%d%d", &i, &j, &w);
G->arc[i][j] = w;
G->arc[j][i] = w; //无向图,矩阵对称
}
}
void CreateALGraph(ALGraph *G){
int i, j, k, w;
ArcNode *p;
printf("请输入顶点数和边数:");
scanf("%d%d", &G->vexnum, &G->arcnum);
printf("请输入顶点数据:");
for(i = 0; i < G->vexnum; i++){
scanf("%d", &G->vertices[i].data);
G->vertices[i].first = NULL; //初始化邻接表
}
printf("请输入边的信息(起点 终点 权值):");
for(k = 0; k < G->arcnum; k++){
scanf("%d%d%d", &i, &j, &w);
//创建边表结点
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = j;
p->next = G->vertices[i].first;
G->vertices[i].first = p;
//对称地创建边表结点
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = i;
p->next = G->vertices[j].first;
G->vertices[j].first = p;
}
}
void DFS(MGraph G, int v, int visited[]){
int w;
printf("%d ", G.vexs[v]);
visited[v] = 1; //标记已访问
for(w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w)){
if(!visited[w]){
DFS(G, w, visited);
}
}
}
void BFS(ALGraph G, int v, int visited[]){
int w;
int queue[MAXV], front = 0, rear = 0;
ArcNode *p;
printf("%d ", G.vertices[v].data);
visited[v] = 1; //标记已访问
queue[rear++] = v;
while(front < rear){
v = queue[front++];
for(p = G.vertices[v].first; p; p = p->next){
w = p->adjvex;
if(!visited[w]){
printf("%d ", G.vertices[w].data);
visited[w] = 1;
queue[rear++] = w;
}
}
}
}
int FirstAdjVex(MGraph G, int v){
int i;
for(i = 0; i < G.vexnum; i++){
if(G.arc[v][i] != 0){
return i; //返回第一个邻接点
}
}
return -1; //没有邻接点
}
int NextAdjVex(MGraph G, int v, int w){
int i;
for(i = w + 1; i < G.vexnum; i++){
if(G.arc[v][i] != 0){
return i; //返回下一个邻接点
}
}
return -1; //没有邻接点
}
void Graph(){
int n;
int visited[MAXV] = {0}; //初始化访问标记数组
MGraph G1;
ALGraph G2;
do{
printf("\n");
printf("图的基本操作及应用*\n");
printf("* 1 创建(邻接矩阵) \n");
printf(" 2 创建(邻接表) \n");
printf(" 3 深度优先遍历(邻接矩阵) \n");
printf(" 4 广度优先遍历(邻接表) \n");
printf(" 5 找第一个邻接点(邻接矩阵) \n");
printf(" 6 找下一个邻接点(邻接矩阵) \n");
printf(" 7 退出 \n");
printf("**************************************************\n");
printf("请选择:");
scanf("%d",&n);
switch(n){
case 1:
printf("---------创建(邻接矩阵)-------\n");
CreateMGraph(&G1);
break;
case 2:
printf("---------创建(邻接表)-------\n");
CreateALGraph(&G2);
break;
case 3:
printf("---------深度优先遍历(邻接矩阵)-------\n");
DFS(G1, 0, visited);
printf("\n");
break;
case 4:
printf("---------广度优先遍历(邻接表)-------\n");
BFS(G2, 0, visited);
printf("\n");
break;
case 5:
printf("---------找第一个邻接点(邻接矩阵)-------\n");
printf("请输入顶点编号:");
scanf("%d", &n);
printf("第一个邻接点为:%d\n", FirstAdjVex(G1, n));
break;
case 6:
printf("---------找下一个邻接点(邻接矩阵)-------\n");
printf("请输入顶点编号和邻接点编号:");
scanf("%d%d", &n, &visited[0]);
printf("下一个邻接点为:%d\n", NextAdjVex(G1, n, visited[0]));
break;
case 7:
break;
default:
printf("ERROR!\n");
break;
}
}while(n != 7);
}
```
阅读全文