有向图的深度优先遍历c语言

深度优先遍历（Depth First Search, DFS）是一种常用的图遍历方法。它通过尽可能深的搜索图的分支，直到这条路走到尽头，然后回溯到前一步继续试探其他分支。

在C语言中，我们可以通过使用递归来实现有向图的深度优先遍历。首先，我们需要定义图的数据结构，通常可以使用邻接表或邻接矩阵来表示有向图。然后我们可以使用一个数组来记录节点是否被访问过，再定义一个递归函数来进行深度优先遍历。

具体地，我们可以使用一个递归函数来进行深度优先搜索，该函数在访问一个节点后，会递归地访问该节点的邻居节点，直到所有可达节点都被访问完。在访问节点时，需要标记该节点为已访问，并输出节点的值。当所有相邻节点都被访问过后，递归函数会回溯到上一层，继续访问其他未被访问过的节点。

需要注意的是，在递归函数中，我们需要判断节点是否已经被访问过，避免重复访问和陷入死循环。而且在实现中还需要考虑内存管理、遍历顺序等问题。

总之，深度优先遍历是一种常用的图遍历方法，在C语言中可以通过递归来实现。这种方法适用于有向图的遍历，并且可以轻松地找到从源节点开始到目标节点的一条路径。

相关问题

图的邻接表非递归深度优先遍历C语言代码

### 回答1：
以下是图的邻接表非递归深度优先遍历的C语言代码：

#include<stdio.h>
#include<stdlib.h>

#define MAX_VERTEX_NUM 20 // 最大顶点数
#define MAX_STACK_SIZE 20 // 最大栈深度

typedef int VertexType; // 顶点的数据类型

// 定义边表结构体
typedef struct ArcNode {
    int adjvex; // 邻接点在顶点数组中的下标
    struct ArcNode *nextarc; // 指向下一个邻接点的指针
} ArcNode;

// 定义顶点表结构体
typedef struct {
    VertexType data; // 顶点的数据
    ArcNode *firstarc; // 指向第一个邻接点的指针
} VNode;

// 定义邻接表结构体
typedef struct {
    VNode vertex[MAX_VERTEX_NUM]; // 顶点数组
    int vexnum, arcnum; // 顶点数和边数
} ALGraph;

// 初始化邻接表
void init(ALGraph *G) {
    int i;
    G->vexnum = G->arcnum = 0;
    for (i = 0; i < MAX_VERTEX_NUM; i++) {
        G->vertex[i].firstarc = NULL;
    }
}

// 添加边
void addEdge(ALGraph *G, int i, int j) {
    ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
    p->adjvex = j;
    p->nextarc = G->vertex[i].firstarc;
    G->vertex[i].firstarc = p;
    G->arcnum++;
}

// 非递归深度优先遍历
void DFS(ALGraph *G, int v) {
    int visited[MAX_VERTEX_NUM];
    int top = -1; // 栈顶指针
    int stack[MAX_STACK_SIZE]; // 栈
    ArcNode *p;
    int i;

    // 初始化visited数组
    for (i = 0; i < MAX_VERTEX_NUM; i++) {
        visited[i] = 0;
    }

    // 将起点v入栈并标记为已访问
    stack[++top] = v;
    visited[v] = 1;

    // 遍历栈中的元素
    while (top != -1) {
        // 取出栈顶元素
        i = stack[top--];
        printf("%d ", G->vertex[i].data);

        // 遍历邻接点
        p = G->vertex[i].firstarc;
        while (p != NULL) {
            // 如果邻接点未被访问，则入栈并标记为已访问
            if (visited[p->adjvex] == 0) {
                stack[++top] = p->adjvex;
                visited[p->adjvex] = 1;
            }
            p = p->nextarc;
        }
    }
}

int main() {
    ALGraph G;
    init(&G);
    addEdge(&G, 0, 1);
    addEdge(&G, 0, 2);
    addEdge(&G, 1, 2);
    addEdge(&G, 2, 0);
    addEdge(&G, 2, 3);
    addEdge(&G, 3, 3);

    printf("非递归深度优先遍历结果：");
    DFS(&G, 2);

    return 0;
}

### 回答2：
下面是图的邻接表非递归深度优先遍历的C语言代码。首先，我们需要定义一个图的结构体，包含顶点数量和邻接表数组。

#include <stdio.h>
#include <stdlib.h>

// 定义图的结构体
typedef struct GraphNode{
    int vertex;
    struct GraphNode* next;
} GraphNode;

typedef struct Graph{
    int vertices;
    GraphNode** adjList;
} Graph;

// 创建图的函数
Graph* createGraph(int vertices){
    Graph* graph = (Graph*) malloc(sizeof(Graph));
    graph->vertices = vertices;

    graph->adjList = (GraphNode**) malloc(vertices * sizeof(GraphNode*));
    for(int i = 0; i < vertices; i++){
        graph->adjList[i] = NULL;
    }

    return graph;
}

// 添加边的函数
void addEdge(Graph* graph, int src, int dest){
    GraphNode* newNode = (GraphNode*) malloc(sizeof(GraphNode));
    newNode->vertex = dest;
    newNode->next = graph->adjList[src];
    graph->adjList[src] = newNode;

    // 若为无向图，则也需添加反向边
    newNode = (GraphNode*) malloc(sizeof(GraphNode));
    newNode->vertex = src;
    newNode->next = graph->adjList[dest];
    graph->adjList[dest] = newNode;
}

// 深度优先遍历函数
void DFS(Graph* graph, int startVertex){
    int* visited = (int*) malloc(graph->vertices * sizeof(int));
    for(int i = 0; i < graph->vertices; i++){
        visited[i] = 0;
    }

    // 使用栈来实现非递归遍历
    int stack[graph->vertices];
    int top = -1;

    stack[++top] = startVertex;
    visited[startVertex] = 1;

    while(top != -1){
        int currentVertex = stack[top--];
        printf("%d ", currentVertex);

        GraphNode* temp = graph->adjList[currentVertex];
        while(temp){
            int adjVertex = temp->vertex;
            if(!visited[adjVertex]){
                stack[++top] = adjVertex;
                visited[adjVertex] = 1;
            }
            temp = temp->next;
        }
    }
}

// 主函数
int main(){
    int vertices = 6;
    Graph* graph = createGraph(vertices);

    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 4);
    addEdge(graph, 3, 4);
    addEdge(graph, 3, 5);

    printf("深度优先遍历结果: ");
    DFS(graph, 0);

    return 0;
}

代码中的`createGraph`函数用于创建具有指定数量顶点的图。`addEdge`函数用于在两个顶点之间添加一条边。`DFS`函数用于执行深度优先遍历。在`main`函数中，我们创建了一个具有6个顶点的图，并添加了一些边。最后，我们调用`DFS`函数从第一个顶点开始进行深度优先遍历，并打印结果。

### 回答3：
深度优先遍历（Depth First Search，简称DFS）是图的一种遍历算法，其中邻接表是一种图的表示方式。下面是一个非递归的深度优先遍历的C语言代码：

#include <stdio.h>
#include <stdlib.h>

#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;                // 顶点数
} Graph;

// 非递归DFS遍历
void DFS(Graph G, int v) {
    int visited[MAX_VERTEX_NUM] = {0}; // 记录顶点是否被访问过的数组
    ArcNode *stack[MAX_VERTEX_NUM];    // 用数组实现栈
    int top = -1;                      // 栈顶指针
    int i;

    printf("DFS遍历顺序: ");
    stack[++top] = &(G.vertices[v]);   // 将起始顶点的邻接表节点入栈
    visited[v] = 1;                    // 标记起始顶点已经被访问
    while (top != -1) {                // 栈不为空时
        ArcNode *p = stack[top--];     // 弹出栈顶元素
        printf("%d ", p->data);        // 访问该顶点
        for (ArcNode *q = p->firstarc; q != NULL; q = q->nextarc) {  // 遍历该顶点的邻接点
            if (visited[q->adjvex] == 0) { // 若邻接点未被访问过
                stack[++top] = &(G.vertices[q->adjvex]); // 入栈
                visited[q->adjvex] = 1;                   // 标记已访问
            }
        }
    }
}

int main() {
    Graph G;

    G.vexnum = 4;  // 假设有4个顶点
    for (int i = 0; i < G.vexnum; i++) {
        G.vertices[i].data = i;      // 顶点数据
        G.vertices[i].firstarc = NULL; // 初始化邻接表节点指针为空
    }

    // 添加边
    ArcNode *arc0 = (ArcNode *)malloc(sizeof(ArcNode));
    arc0->adjvex = 1;
    arc0->nextarc = NULL;
    G.vertices[0].firstarc = arc0;

    ArcNode *arc1 = (ArcNode *)malloc(sizeof(ArcNode));
    arc1->adjvex = 2;
    arc1->nextarc = NULL;
    G.vertices[1].firstarc = arc1;

    ArcNode *arc2 = (ArcNode *)malloc(sizeof(ArcNode));
    arc2->adjvex = 3;
    arc2->nextarc = NULL;
    G.vertices[2].firstarc = arc2;

    // 顶点0的邻接点为1
    // 顶点1的邻接点为2
    // 顶点2的邻接点为3

    DFS(G, 0);

    return 0;
}

此代码采用邻接表的形式存储图，并使用非递归的深度优先遍历算法遍历图中的顶点和边。首先定义了邻接表节点和顶点节点的数据结构，然后定义了图的数据结构，包括顶点数组和顶点数。接下来，使用非递归的深度优先遍历算法实现了DFS()函数，在DFS()函数中，使用栈来记录待访问的节点，并使用visited数组来标记节点是否被访问过。最后，在主函数中创建了一个具有4个顶点的图，并添加了相应的边，然后调用DFS()函数进行遍历。

图的深度遍历和广度遍历c语言 代码

图的深度遍历和广度遍历都可以用C语言来实现。

深度遍历代码示例：

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20 // 最大顶点数
typedef int VertexType; // 顶点数据类型

// 边表结点
typedef struct ArcNode {
    int adjvex; // 邻接点下标
    struct ArcNode *next; // 指向下一个邻接点的指针
} ArcNode;

// 顶点表结点
typedef struct VNode {
    VertexType data; // 顶点数据
    ArcNode *firstarc; // 指向第一个邻接点的指针
} VNode, AdjList[MAX_VERTEX_NUM];

// 图的结构体
typedef struct {
    AdjList vertices; // 顶点表
    int vexnum, arcnum; // 顶点数和边数
} ALGraph;

// 初始化一个空图
void initGraph(ALGraph *G) {
    int i;
    G->vexnum = 0;
    G->arcnum = 0;
    for (i = 0; i < MAX_VERTEX_NUM; i++) {
        G->vertices[i].firstarc = NULL;
    }
}

// 添加一个顶点
void addVertex(ALGraph *G, VertexType v) {
    G->vertices[G->vexnum].data = v;
    G->vexnum++;
}

// 添加一条边（有向图）
void addArc(ALGraph *G, int i, int j) {
    ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
    p->adjvex = j;
    p->next = G->vertices[i].firstarc;
    G->vertices[i].firstarc = p;
    G->arcnum++;
}

// 深度优先遍历
void DFS(ALGraph *G, int v, int visited[]) {
    visited[v] = 1; // 标记为已访问
    printf("%d ", G->vertices[v].data); // 输出当前顶点
    ArcNode *p = G->vertices[v].firstarc;
    while (p) { // 遍历邻接点
        if (!visited[p->adjvex]) { // 如果邻接点未被访问，递归遍历
            DFS(G, p->adjvex, visited);
        }
        p = p->next;
    }
}

// 图的深度优先遍历
void DFSTraverse(ALGraph *G) {
    int visited[MAX_VERTEX_NUM] = {0}; // 初始化所有顶点为未访问
    int i;
    for (i = 0; i < G->vexnum; i++) { // 遍历所有顶点
        if (!visited[i]) { // 如果顶点未被访问，从该顶点开始遍历
            DFS(G, i, visited);
        }
    }
}

int main() {
    ALGraph G;
    initGraph(&G);
    addVertex(&G, 1);
    addVertex(&G, 2);
    addVertex(&G, 3);
    addVertex(&G, 4);
    addVertex(&G, 5);
    addArc(&G, 0, 1);
    addArc(&G, 0, 2);
    addArc(&G, 1, 3);
    addArc(&G, 2, 3);
    addArc(&G, 3, 4);
    printf("DFS: ");
    DFSTraverse(&G);
    return 0;
}

广度遍历代码示例：

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20 // 最大顶点数
#define MAX_QUEUE_SIZE 20 // 队列最大长度
typedef int VertexType; // 顶点数据类型

// 边表结点
typedef struct ArcNode {
    int adjvex; // 邻接点下标
    struct ArcNode *next; // 指向下一个邻接点的指针
} ArcNode;

// 顶点表结点
typedef struct VNode {
    VertexType data; // 顶点数据
    ArcNode *firstarc; // 指向第一个邻接点的指针
} VNode, AdjList[MAX_VERTEX_NUM];

// 图的结构体
typedef struct {
    AdjList vertices; // 顶点表
    int vexnum, arcnum; // 顶点数和边数
} ALGraph;

// 初始化一个空图
void initGraph(ALGraph *G) {
    int i;
    G->vexnum = 0;
    G->arcnum = 0;
    for (i = 0; i < MAX_VERTEX_NUM; i++) {
        G->vertices[i].firstarc = NULL;
    }
}

// 添加一个顶点
void addVertex(ALGraph *G, VertexType v) {
    G->vertices[G->vexnum].data = v;
    G->vexnum++;
}

// 添加一条边（有向图）
void addArc(ALGraph *G, int i, int j) {
    ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
    p->adjvex = j;
    p->next = G->vertices[i].firstarc;
    G->vertices[i].firstarc = p;
    G->arcnum++;
}

// 初始化一个队列
void initQueue(int *front, int *rear) {
    *front = *rear = 0;
}

// 判断队列是否为空
int isQueueEmpty(int front, int rear) {
    return front == rear;
}

// 入队
void enqueue(int *queue, int *rear, int data) {
    queue[(*rear)++] = data;
}

// 出队
int dequeue(int *queue, int *front) {
    return queue[(*front)++];
}

// 广度优先遍历
void BFS(ALGraph *G, int v, int visited[]) {
    int queue[MAX_QUEUE_SIZE]; // 定义一个队列
    int front, rear; // 队列的前后指针
    initQueue(&front, &rear); // 初始化队列
    visited[v] = 1; // 标记为已访问
    printf("%d ", G->vertices[v].data); // 输出当前顶点
    enqueue(queue, &rear, v); // 将当前顶点入队
    while (!isQueueEmpty(front, rear)) { // 队列不为空时循环
        int w = dequeue(queue, &front); // 出队
        ArcNode *p = G->vertices[w].firstarc;
        while (p) { // 遍历所有邻接点
            int u = p->adjvex;
            if (!visited[u]) { // 如果邻接点未被访问，标记为已访问，输出，入队
                visited[u] = 1;
                printf("%d ", G->vertices[u].data);
                enqueue(queue, &rear, u);
            }
            p = p->next;
        }
    }
}

// 图的广度优先遍历
void BFSTraverse(ALGraph *G) {
    int visited[MAX_VERTEX_NUM] = {0}; // 初始化所有顶点为未访问
    int i;
    for (i = 0; i < G->vexnum; i++) { // 遍历所有顶点
        if (!visited[i]) { // 如果顶点未被访问，从该顶点开始遍历
            BFS(G, i, visited);
        }
    }
}

int main() {
    ALGraph G;
    initGraph(&G);
    addVertex(&G, 1);
    addVertex(&G, 2);
    addVertex(&G, 3);
    addVertex(&G, 4);
    addVertex(&G, 5);
    addArc(&G, 0, 1);
    addArc(&G, 0, 2);
    addArc(&G, 1, 3);
    addArc(&G, 2, 3);
    addArc(&G, 3, 4);
    printf("BFS: ");
    BFSTraverse(&G);
    return 0;
}