图算法入门：C语言中的图遍历和最短路径算法

## 第一章：图算法概述

### 1.1 什么是图

图是一种非线性的数据结构，由节点（顶点）和连接节点的边组成。图可以用来表示各种实际问题中的关系和交互情况，比如社交网络、电子电路、地理地图等。在图中，节点表示实体，边表示实体之间的关系。

### 1.2 图的表示方法

图可以用不同的方式来进行表示，常用的有邻接矩阵和邻接表两种方法。

**邻接矩阵：**

邻接矩阵是一个二维矩阵，其中每个元素表示两个节点之间是否存在边。如果节点i和节点j之间存在边，则矩阵中的第i行第j列元素为1，否则为0。

邻接矩阵的优点是查询两个节点之间是否存在边的时间复杂度为O(1)，但是对于稀疏图来说，矩阵中大部分元素为0，浪费了空间。

**邻接表：**

邻接表是一种链表的结构，其中每个节点保存着与该节点相邻的节点信息。可以通过数组和链表的组合来实现邻接表。数组的每个元素对应一个节点，链表中保存着与该节点相邻的节点。

邻接表的优点是对于稀疏图来说，节省了空间；缺点是查询两个节点之间是否存在边的时间复杂度取决于链表的长度。

### 1.3 图的遍历算法概述

图的遍历算法用于按照一定规则访问图中的所有节点。常用的两种图遍历算法是深度优先搜索（DFS）算法和广度优先搜索（BFS）算法。

**深度优先搜索（DFS）算法：**

深度优先搜索算法从一个起始节点开始，一直向下探索直到最深处，然后回溯到上一层继续探索。DFS算法的实现可以通过递归或者栈来实现。

以下是深度优先搜索算法的Python代码示例：

def dfs(graph, start, visited):
    visited[start] = True
    print("Visited node:", start)
  
    for neighbor in graph[start]:
        if not visited[neighbor]:
            dfs(graph, neighbor, visited)

**广度优先搜索（BFS）算法：**

广度优先搜索算法从一个起始节点开始，依次访问与该节点相邻的所有节点，然后再访问与这些节点相邻的节点，依此类推。BFS算法的实现可以通过队列来实现。

以下是广度优先搜索算法的Java代码示例：

void bfs(Map<Integer, List<Integer>> graph, int start) {
    Queue<Integer> queue = new LinkedList<>();
    boolean[] visited = new boolean[graph.size()];
    visited[start] = true;
    queue.offer(start);

    while (!queue.isEmpty()) {
        int node = queue.poll();
        System.out.println("Visited node: " + node);

        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.offer(neighbor);
            }
        }
    }
}

### 1.4 图的最短路径算法概述

图的最短路径算法用于求解两个节点之间的最短路径。常用的两种最短路径算法是Dijkstra算法和Floyd-Warshall算法。

**Dijkstra算法：**

Dijkstra算法用于求解单源最短路径，即求解一个节点到图中其他所有节点的最短路径。算法通过贪心策略逐步扩展已找到最短路径的节点集合，直到找到所有节点的最短路径。

**Floyd-Warshall算法：**

Floyd-Warshall算法用于求解任意两个节点之间的最短路径。算法通过三重循环依次更新节点之间的最短路径。

## 第二章：图的遍历算法实现
2.1 深度优先搜索（DFS）算法
2.2 广度优先搜索（BFS）算法
2.3 针对不同场景的应用案例
### 第三章：最短路径算法之Dijkstra算法

#### 3.1 Dijkstra算法原理分析

Dijkstra算法是一种用于解决单源最短路径问题的经典算法。该算法通过逐步确定从源节点到其他节点的最短路径，并将节点分为两部分：已确定最短路径的节点集合S和未确定最短路径的节点集合T。

#### 3.2 C语言实现Dijkstra算法的步骤

下面是使用C语言实现Dijkstra算法的关键代码步骤：

#include <stdio.h>
#include <stdbool.h>

#define MAX_SIZE 100
#define INF 9999

void Dijkstra(int graph[MAX_SIZE][MAX_SIZE], int n, int start)
{
    int dist[MAX_SIZE];     // 存储从起点到每个节点的最短路径长度
    bool visited[MAX_SIZE];  // 存储每个节点的访问状态

    // 初始化dist数组和visited数组
    for (int i = 0; i < n; i++)
    {
        dist[i] = INF;
        visited[i] = false;
    }

    dist[start] = 0;  // 起点到自身的距离为0

    // 遍历n-1次，每次确定一个节点的最短路径
    for (int i = 0; i < n - 1; i++)
    {
        int minDist = INF;
        int minNode = -1;

        // 在未确定最短路径的节点中找到距离最小的节点
        for (int j = 0; j < n; j++)
        {
            if (!visited[j] && dist[j] < minDist)
            {
                minDist = dist[j];
                minNode = j;
            }
        }

        visited[minNode] = true;  // 将该节点标记为已访问

        // 更新其他节点的最短路径长度
        for (int j = 0; j < n; j++)
        {
            if (!visited[j] && graph[minNode][j] && dist[minNode] != INF && dist[minNode]