代码随想录算法训练营第五十五天|Day55 图论

https://www.programmercarl.com/kamacoder/0107.%E5%AF%BB%E6%89%BE%E5%AD%98%E5%9C%A8%E7%9A%84%E8%B7%AF%E5%BE%84.html

思路

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

#define MAX_NODES 101

// 邻接表的节点结构
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

// 图的邻接表
typedef struct Graph {
    Node* adjacencyList[MAX_NODES];
} Graph;

// 初始化图
void initGraph(Graph* graph) {
    for (int i = 1; i < MAX_NODES; i++) {
        graph->adjacencyList[i] = NULL;
    }
}

// 创建邻接表节点
Node* createNode(int vertex) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = vertex;
    newNode->next = NULL;
    return newNode;
}

// 添加边
void addEdge(Graph* graph, int src, int dest) {
    // 添加从 src 到 dest 的边
    Node* newNode = createNode(dest);
    newNode->next = graph->adjacencyList[src];
    graph->adjacencyList[src] = newNode;

    // 添加从 dest 到 src 的边 (无向图)
    newNode = createNode(src);
    newNode->next = graph->adjacencyList[dest];
    graph->adjacencyList[dest] = newNode;
}

// DFS 函数
int dfs(Graph* graph, int visited[], int current, int destination) {
    if (current == destination) {
        return 1; // 找到目标
    }

    visited[current] = 1; // 标记当前节点为已访问

    Node* temp = graph->adjacencyList[current];
    while (temp != NULL) {
        int vertex = temp->vertex;
        if (!visited[vertex]) { // 如果未访问，递归 DFS
            if (dfs(graph, visited, vertex, destination)) {
                return 1;
            }
        }
        temp = temp->next;
    }
    
    return 0; // 没有找到目标
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m); // 输入节点数和边数

    Graph graph;
    initGraph(&graph);
    
    // 输入边信息
    for (int i = 0; i < m; i++) {
        int s, t;
        scanf("%d %d", &s, &t);
        addEdge(&graph, s, t);
    }

    int source, destination;
    scanf("%d %d", &source, &destination); // 输入起点和终点

    int visited[MAX_NODES] = {0}; // 访问标记数组

    // 调用 DFS 检查路径
    if (dfs(&graph, visited, source, destination)) {
        printf("1\n"); // 存在路径
    } else {
        printf("0\n"); // 不存在路径
    }

    return 0;
}

学习反思

代码是一个使用邻接表实现的图的深度优先搜索算法。代码首先定义了邻接表的节点结构和图的结构。然后通过initGraph函数初始化图，createNode函数创建节点，addEdge函数添加边。接着定义了DFS函数，用于递归地进行深度优先搜索。在主函数中，首先读取节点数和边数，然后根据输入添加边信息。接着读取起点和终点，然后定义一个访问标记数组，最后调用DFS函数检查是否存在路径，并输出结果。这段代码使用了递归的深度优先搜索算法来检查图中是否存在路径。它通过访问标记数组来标记已经访问过的节点，避免重复访问。在DFS函数中，当当前节点等于目标节点时，返回1表示找到路径；否则，递归地访问当前节点的邻接节点，直到找到路径或遍历完所有邻接节点。最后，根据DFS函数的返回值，输出是否存在路径。这段代码的时间复杂度为O(V+E)，其中V为节点数，E为边数。因为在最坏情况下，每个节点都需要遍历一次，并且每个节点的邻接节点都需要遍历一次。空间复杂度为O(V)，因为需要一个访问标记数组来记录节点的访问状态。总的来说，这段代码使用邻接表实现了图的深度优先搜索算法。可以用于检查图中是否存在路径。