// dfs非递归实现 void DFS(ALGraph G, int start) { bool visited[MAX_VERTEX_NUM]; for (int i = 0; i < G.vexnum; i++) { visited[i] = false; } int stack[MAX_VERTEX_NUM]; int top = -1; stack[++top] = start; visited[start] = true; while (top != -1) { int v = stack[top--]; printf("%d ", v); ArcNode* p = G.vertices[v].firstarc; while (p != NULL) { if (!visited[p->adjvex]) { visited[p->adjvex] = true; stack[++top] = p->adjvex; } p = p->nextarc; } } }

这是一个非递归实现的深度优先搜索（DFS）算法，用于遍历图数据结构。以下是代码的解释：

- 首先，定义了一个 bool 类型的数组 visited，用于记录顶点是否被访问过。将数组中的所有元素初始化为 false。
- 接着，定义了一个 int 类型的数组 stack，用于模拟栈结构。同时定义一个变量 top，表示栈顶的位置，初始值为 -1。
- 将起始顶点 start 压入栈中，并将 visited 数组中对应的位置设为 true。
- 进入 while 循环，只要栈不为空，就一直执行。在循环中，取出栈顶元素 v，并输出顶点的值。
- 遍历以顶点 v 为起点的所有边，如果边的终点未被访问过，则将其压入栈中，并将 visited 数组中对应的位置设为 true。
- 最后，当遍历完成后，所有的顶点都被访问过，算法结束。

需要注意的是，该算法的时间复杂度为 O(V+E)，其中 V 表示图中顶点的数量，E 表示边的数量。

相关问题

将这段代码改写为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); }

好的，下面是将代码改写为C语言bool visited[MAX_VERTEX_NUM];的实现方法：

#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常量。

试写一算法，判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径（i-->j）。 【输入形式】 顶点个数：n 边的条数：m 边的有向顶点对： （a,b）…… 待判断定点i，j 【输出形式】 True 或 False 【样例输入】 5 4 1 2 1 3 2 4 3 5 1 5 【样例输出】 True 【样例说明】 【评分标准】 【代码框架】 #include<stdio.h> #include<malloc.h> #define OK 1 #define ERROR 0 #define MAX_VEX_NUM 100 //最大顶点数量 typedef int Status; typedef enum{AG,AN,DG,DN} GKind; //图类型定义 typedef struct ArcNode{ int adjvex; //邻接点数组下标（从0开始） struct ArcNode *nextarc; int weight; }; typedef struct { int vertex; //顶点编号，从1开始 ArcNode *firstarc; }VNode,AdjList[MAX_VEX_NUM]; typedef struct{ AdjList vertices; int vexnum; int arcnum; GKind kind; }ALGraph; Status InitALGraph(ALGraph &G) { } //创建图的邻接表存储结构 //n: 顶点数 //vertices[]:顶点数组 //edges[][]:边数组 //edgesSize：边数目 Status CreateALGraph(ALGraph &G, int n, int vertices[ ], int edges[20][2], int edgesSize) { } //连通图的深度优先搜索 //v0: 起点的数组下标（从0开始） //visited[ ]:访问标志数组 void DFS(ALGraph G, int v0, int visited[]) { } //图的深度优先搜索 int DFSTraverse(ALGraph G) { } // 判断图的两个顶点是否连通，如果连通，返回true, 否则返回false //v: 起点的编号（从1开始） //w:终点的编号（从1开始） bool isConnect(ALGraph G, int v, int w) { }

#include<stdio.h>
#include<malloc.h>

#define OK 1
#define ERROR 0
#define MAX_VEX_NUM 100 //最大顶点数量

typedef int Status;
typedef enum{AG,AN,DG,DN} GKind; //图类型定义

typedef struct ArcNode{
    int adjvex;      //邻接点数组下标（从0开始）
    struct ArcNode *nextarc;
    int weight;
}ArcNode;

typedef struct VNode{
    int vertex;  //顶点编号，从1开始
    ArcNode *firstarc;
}VNode,AdjList[MAX_VEX_NUM];

typedef struct{
    AdjList vertices;
    int vexnum;
    int arcnum;
    GKind kind;
}ALGraph;

Status InitALGraph(ALGraph &G){
    G.vexnum = 0;
    G.arcnum = 0;
    G.kind = DG;    //默认为有向图
    for(int i = 0; i < MAX_VEX_NUM; i++){
        G.vertices[i].vertex = 0;
        G.vertices[i].firstarc = NULL;
    }
    return OK;
}

Status CreateALGraph(ALGraph &G, int n, int vertices[],  int edges[20][2], int edgesSize){
    G.vexnum = n;
    G.arcnum = edgesSize;
    for(int i = 0; i < n; i++){
        G.vertices[i].vertex = vertices[i];
    }
    for(int i = 0; i < edgesSize; i++){
        int v1 = edges[i][0]-1;
        int v2 = edges[i][1]-1;
        ArcNode *arc = (ArcNode*)malloc(sizeof(ArcNode));
        arc->adjvex = v2;
        arc->nextarc = G.vertices[v1].firstarc;
        G.vertices[v1].firstarc = arc;
    }
    return OK;
}

void DFS(ALGraph G, int v0, int visited[]){
    visited[v0] = 1;
    ArcNode *p = G.vertices[v0].firstarc;
    while(p != NULL){
        int w = p->adjvex;
        if(visited[w] == 0){
            DFS(G, w, visited);
        }
        p = p->nextarc;
    }
}

int DFSTraverse(ALGraph G){
    int visited[MAX_VEX_NUM] = {0};
    int count = 0;
    for(int i = 0; i < G.vexnum; i++){
        if(visited[i] == 0){
            count++;
            DFS(G, i, visited);
        }
    }
    return count;
}

bool isConnect(ALGraph G, int v, int w){
    int visited[MAX_VEX_NUM] = {0};
    int v0 = v-1, w0 = w-1;
    DFS(G, v0, visited);
    if(visited[w0] == 1){
        return true;
    }
    return false;
}

int main(){
    ALGraph G;
    int n, m, v, w;
    int vertices[MAX_VEX_NUM];
    int edges[20][2];
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++){
        scanf("%d", &vertices[i]);
    }
    for(int i = 0; i < m; i++){
        scanf("%d%d", &edges[i][0], &edges[i][1]);
    }
    InitALGraph(G);
    CreateALGraph(G, n, vertices, edges, m);
    scanf("%d%d", &v, &w);
    if(isConnect(G, v, w)){
        printf("True\n");
    }
    else{
        printf("False\n");
    }
    return 0;
}