图的深度优先搜索

本文主要是介绍图的深度优先搜索，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

输入格式

输入的第一行为两个整数 nn 和 mm（1 < n \leq 1001<n≤100，1 \leq m \leq 2001≤m≤200），代表图中的顶点数和边数。接下来的 mm 行，每行输入两个整数 xx（0 \leq x \leq n-10≤x≤n−1） 和 yy（0 \leq y \leq n-10≤y≤n−1），表示一条从 xx 连向 yy 的无向边。之后输入一个整数 kk（0 \leq k < n0≤k<n），表示深度优先搜索的起点。

输出格式

输出深度优先搜索的遍历结果，每个元素各占一行。

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

#define MAX_N 10000

typedef struct Node {
    int vertex;
    struct Node *next;
} Node, *LinkedList;

LinkedList insert_node(LinkedList head, int index) {
    Node *node = (Node *)malloc(sizeof(Node));
    node->vertex = index;
    node->next = head;
    head = node;
    return head;
}

typedef struct Graph {
    LinkedList edges[MAX_N];
    int n;
    int visited[MAX_N];
} Graph;

void init(Graph * g, int n) {
    g->n = n;
    for (int i = 0; i < g->n; ++i) {
        g->edges[i] = NULL;
    }
    memset(g->visited,0,sizeof(g->visited));
}

void insert(Graph *g, int x, int y) {
    if (x < 0 || x >= g->n || y < 0 || y >= g->n) {
        return ;
    }
    g->edges[x] = insert_node(g->edges[x], y);
    g->edges[y] = insert_node(g->edges[y], x);
}

void clear(Graph *g) {
    for (int i = 0; i < g->n; ++i) {
        Node *head = g->edges[i];
        while (head != NULL) {
            Node *delete_node = head;
            head = head->next;
            free(delete_node);
        }
    }
    free(g);
}

void dfs(Graph *g, int index) {
    printf("%d\n",index);
    g->visited[index]=1;
    for(Node *adj=g->edges[index];adj!=NULL;adj=adj->next)
    {
        if(g->visited[adj->vertex]!=1)
        {
            dfs(g,adj->vertex);
        }
    }
}

int main() {
    int n, m, k;
    scanf("%d %d", &n, &m);
    Graph *graph = (Graph *)malloc(sizeof(Graph));
    init(graph, n);
    for (int i = 0; i < m; ++i) {
        int x, y;
        scanf("%d %d", &x, &y);
        insert(graph, x, y);
    }
    scanf("%d", &k);
    dfs(graph, k);
    clear(graph);
    return 0;
}

这篇关于图的深度优先搜索的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！