用c语言写采用邻接表存储结构,创建无向图求距离v0最短路径长度为k的所有顶点 功能:找出所有距离v0最短路径长度为k的顶点,并输出。输出语句为: printf("距离%s的最短路径为%d的顶点有%s",v0的值,k,顶点的值), 如果查询结果有多个,则补充打印printf(",%s",其他顶点); 提示:先声明一个一维数组,记录顶点的访问标志, 声明一个队列queue[][0]存储顶点的序号,queue[][1]存储当前顶点距离v0的路径长度, 遍历各顶点,然后输出queue[][1]是k的顶点。 参数:AdjGraph G 是需要操作的图,int v0是需要查找的参照点默认是v0(0),int k是距离v0最短路径的长度 返回值:无。 举例:查询结果是一个顶点:距离1的最短路径为3的顶点有4 查询结果是多个顶点:距离1的最短路径为3的顶点有5,3
时间: 2024-03-21 10:42:38 浏览: 59
数据结构实验3
这是一个比较具体的问题,需要一些代码实现,以下是我为您提供的实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20
typedef int VertexType;
typedef struct ArcNode{
int adjvex; // 该弧所指向的顶点的位置
struct ArcNode *nextarc; // 指向下一条弧的指针
}ArcNode;
typedef struct VNode{
VertexType data; // 顶点信息
ArcNode *firstarc; // 指向第一条依附该顶点的弧的指针
}VNode, AdjList[MAX_VERTEX_NUM];
typedef struct{
AdjList vertices;
int vexnum, arcnum; // 图的当前顶点数和弧数
}ALGraph;
void CreateGraph(ALGraph *G){
printf("请输入图的顶点数和弧数:");
scanf("%d%d", &G->vexnum, &G->arcnum);
printf("请输入图的顶点信息:");
for(int i = 0; i < G->vexnum; i++){
scanf("%d", &G->vertices[i].data);
G->vertices[i].firstarc = NULL;
}
printf("请输入每条弧的起点和终点(用空格隔开):\n");
for(int k = 0; k < G->arcnum; k++){
int i, j;
scanf("%d%d", &i, &j);
ArcNode *e = (ArcNode*)malloc(sizeof(ArcNode));
e->adjvex = j;
e->nextarc = G->vertices[i].firstarc;
G->vertices[i].firstarc = e;
e = (ArcNode*)malloc(sizeof(ArcNode));
e->adjvex = i;
e->nextarc = G->vertices[j].firstarc;
G->vertices[j].firstarc = e;
}
}
void PrintGraph(ALGraph G){
printf("图的邻接表:\n");
for(int i = 0; i < G.vexnum; i++){
printf("%d ->", G.vertices[i].data);
ArcNode *e = G.vertices[i].firstarc;
while(e != NULL){
printf(" %d", G.vertices[e->adjvex].data);
e = e->nextarc;
}
printf("\n");
}
}
void ShortestPath(ALGraph G, int v0, int k){
int visited[MAX_VERTEX_NUM] = {0}; // 记录顶点的访问标志
int queue[MAX_VERTEX_NUM][2] = {0}; // 存储顶点的序号和距离v0的路径长度
int front = 0, rear = 0;
queue[rear][0] = v0;
queue[rear][1] = 0;
rear++;
visited[v0] = 1;
while(front != rear){
int v = queue[front][0];
int dist = queue[front][1];
front++;
if(dist == k){
printf("距离%d的最短路径为%d的顶点有%d", G.vertices[v0].data, k, G.vertices[v].data);
for(int i = front; i < rear; i++){
if(queue[i][1] == k && queue[i][0] != v){
printf(",%d", G.vertices[queue[i][0]].data);
}
}
printf("\n");
return;
}
ArcNode *e = G.vertices[v].firstarc;
while(e != NULL){
int adjvex = e->adjvex;
if(visited[adjvex] == 0){
visited[adjvex] = 1;
queue[rear][0] = adjvex;
queue[rear][1] = dist + 1;
rear++;
}
e = e->nextarc;
}
}
}
int main(){
ALGraph G;
CreateGraph(&G);
PrintGraph(G);
int v0, k;
printf("请输入参照点(0-%d):", G.vexnum - 1);
scanf("%d", &v0);
printf("请输入距离v0的最短路径长度k:");
scanf("%d", &k);
ShortestPath(G, v0, k);
return 0;
}
```
这段代码使用邻接表存储结构创建图,并实现了查找距离v0最短路径长度为k的所有顶点的功能。具体实现细节可以参考代码注释。
阅读全文