将这段代码改写为C语言bool visited[MAX_VERTEX_NUM]; // MAX_VERTEX_NUM为顶点数的最大值,需根据实际情况调整 bool dfs(ALGraph G, int vi, int vj) { visited[vi] = true; for (ArcNode* p = G.vertices[vi].firstarc; p != NULL; p = p->nextarc) { int w = p->adjvex; if (w == vj) { return true; } if (!visited[w]) { if (dfs(G, w, vj)) { return true; } } } return false; } bool hasPath(ALGraph G, int vi, int vj) { memset(visited, false, sizeof(visited)); return dfs(G, vi, vj); }
时间: 2024-01-24 11:05:36 浏览: 71
最大值c语言代码
5星 · 资源好评率100%
好的,下面是将代码改写为C语言bool visited[MAX_VERTEX_NUM];的实现方法:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> // 引入bool类型和true/false常量
#define MAX_VERTEX_NUM 100 // 图中最大顶点数
// 邻接表中的边节点
typedef struct ArcNode {
int adjvex; // 该边所指向的顶点的位置
struct ArcNode *nextarc; // 指向下一条边的指针
} ArcNode;
// 邻接表中的顶点节点
typedef struct VNode {
int data; // 顶点的数据
ArcNode *firstarc; // 指向第一条依附该顶点的边的指针
} VNode, AdjList[MAX_VERTEX_NUM];
// 有向图的邻接表结构
typedef struct {
AdjList vertices; // 邻接表
int vexnum, arcnum; // 图的顶点数和边数
} ALGraph;
// 初始化有向图
void InitGraph(ALGraph *G) {
int i;
G->vexnum = G->arcnum = 0;
for (i = 0; i < MAX_VERTEX_NUM; i++) {
G->vertices[i].data = 0;
G->vertices[i].firstarc = NULL;
}
}
// 添加顶点
void AddVertex(ALGraph *G, int v) {
G->vertices[G->vexnum].data = v;
G->vexnum++;
}
// 添加边
void AddArc(ALGraph *G, int from, int to) {
ArcNode *arc = (ArcNode *) malloc(sizeof(ArcNode));
arc->adjvex = to;
arc->nextarc = G->vertices[from].firstarc;
G->vertices[from].firstarc = arc;
G->arcnum++;
}
// 深度优先搜索
bool dfs(ALGraph G, int vi, int vj, bool visited[]) {
visited[vi] = true; // 标记该顶点已访问过
if (vi == vj) { // 找到了从vi到vj的路径
return true;
}
ArcNode *arc = G.vertices[vi].firstarc;
while (arc != NULL) {
int w = arc->adjvex;
if (!visited[w]) { // 如果该顶点未被访问过
if (dfs(G, w, vj, visited)) { // 继续搜索
return true;
}
}
arc = arc->nextarc;
}
return false;
}
// 判断有向图中是否存在由顶点vi到顶点vj的路径
bool hasPath(ALGraph G, int vi, int vj) {
bool visited[MAX_VERTEX_NUM] = {false}; // 初始化所有顶点为未访问过
return dfs(G, vi, vj, visited); // 从vi开始搜索
}
int main() {
int i, n, m, v, w;
ALGraph G;
InitGraph(&G);
printf("请输入顶点数和边数:");
scanf("%d%d", &n, &m);
printf("请输入%d个顶点:\n", n);
for (i = 0; i < n; i++) {
scanf("%d", &v);
AddVertex(&G, v);
}
printf("请输入%d条边:\n", m);
for (i = 0; i < m; i++) {
scanf("%d%d", &v, &w);
AddArc(&G, v, w);
}
printf("请输入要查询的路径(格式:i j):");
scanf("%d%d", &v, &w);
if (hasPath(G, v, w)) {
printf("存在从顶点%d到顶点%d的路径。\n", v, w);
} else {
printf("不存在从顶点%d到顶点%d的路径。\n", v, w);
}
return 0;
}
```
以上就是将代码改写为C语言bool visited[MAX_VERTEX_NUM];的实现方法。注意,这里需要在函数参数中添加bool visited[],并在dfs函数中修改visited数组的值。同时,需要引入stdbool.h头文件来使用bool类型和true/false常量。
阅读全文