【地铁上的面试题】--基础部分--数据结构与算法--树和图

喵叔

发布于 2023-06-04 14:40:16

4860

发布于 2023-06-04 14:40:16

文章被收录于专栏：喵叔's 专栏

一、树的基本概念和特点

1.1 树的定义和术语

树（Tree）是一种非线性的数据结构，由若干个节点（Node）组成。树的定义包括以下几个术语：

术语	解释
节点（Node）	树中的每个元素称为节点。每个节点包含一个值和指向其他节点的指针或引用。
根节点（Root）	树的顶层节点称为根节点，它没有父节点。
子节点（Child）	一个节点可以有零个或多个子节点，子节点是其父节点的直接后继。
父节点（Parent）	一个节点的直接上级节点称为父节点。
兄弟节点（Sibling）	具有相同父节点的节点互为兄弟节点。
叶节点（Leaf）	没有子节点的节点称为叶节点或终端节点。
子树（Subtree）	树中的任意一个节点及其所有后代节点构成一个子树。
深度（Depth）	根节点到某个节点的路径长度称为该节点的深度。
高度（Height）	树中节点的最大深度称为树的高度。
节点的度（Degree）	一个节点拥有的子节点数量称为节点的度。
树的度（Degree）	树中节点的最大度称为树的度。

Tip：树的定义和术语为我们理解树结构提供了基础概念。根据节点之间的关系和属性，树的形态和特性可以有很多种类，如二叉树、二叉搜索树、平衡树等。了解这些概念和术语有助于我们更好地理解树结构以及相关的操作和算法。

1.2 树的特点和性质

树（Tree）作为一种常见的数据结构，具有以下特点和性质：

特点与性质	解释
非线性结构	树是一种非线性的数据结构，与线性结构（如数组和链表）相对。树的节点之间通过边连接，形成分层关系。
层级关系	树中的节点按照层级进行组织，根节点位于最顶层，其他节点依次排列在下方的层级。
有且仅有一个根节点	树中只有一个根节点，它是整个树的起始节点，没有父节点。
子节点和父节点	每个节点可以有零个或多个子节点，每个节点除了根节点之外都有一个父节点。
分支结构	节点之间的连接称为边，用于表示节点之间的关系。从根节点到任意节点都有唯一的路径。
无环结构	树是无环的，即不存在节点之间的循环路径。
唯一路径	树中的任意两个节点之间有且仅有唯一的路径。
深度和高度	节点的深度是从根节点到该节点的路径长度，树的高度是所有节点深度的最大值。
子树	树中的任意一个节点及其所有后代节点构成一个子树。
叶节点	没有子节点的节点称为叶节点或终端节点。

Tip：树的特点和性质使其具有良好的层级结构，适用于许多实际应用场景，如文件系统、数据库索引、组织结构等。

1.3 常见的树结构

常见的树结构包括以下几种：

二叉树（Binary Tree）：每个节点最多有两个子节点的树结构称为二叉树。子节点分别称为左子节点和右子节点。二叉树可以是空树，也可以只有一个节点。
二叉搜索树（Binary Search Tree）：二叉搜索树是一种有序的二叉树，其中任意节点的左子树的值都小于该节点的值，而右子树的值都大于该节点的值。这个性质使得二叉搜索树可以进行高效的插入、查找和删除操作。
平衡树（Balanced Tree）：平衡树是一种高度平衡的二叉搜索树，通过特定的平衡因子或平衡条件来保持树的平衡状态。常见的平衡树包括AVL树、红黑树等，它们能够在插入和删除节点时自动进行调整，以保持树的平衡性，提高操作效率。
B树（B-Tree）：B树是一种多路搜索树，其特点是每个节点可以拥有多个子节点。B树常用于文件系统和数据库索引结构中，能够高效地支持范围查询和持久化存储。
Trie树（Trie Tree）：也称为字典树或前缀树，用于高效地存储和检索字符串集合。Trie树的特点是每个节点代表一个字符，从根节点到叶节点的路径表示一个字符串。

这些常见的树结构在不同场景下具有不同的应用和特点。二叉搜索树适用于快速的查找、插入和删除操作；平衡树解决了二叉搜索树在频繁插入和删除时可能导致的不平衡问题；B树和Trie树适用于大规模数据的存储和检索。

二、树的遍历和操作

2.1 深度优先遍历（DFS）：前序、中序、后序遍历

深度优先遍历（Depth-First Search，DFS）是一种用于遍历或搜索树或图的算法。在树的遍历中，DFS按照深度优先的顺序遍历树的节点，从根节点开始，先访问当前节点，然后递归地访问其左子树和右子树。DFS有三种常见的遍历方式：前序遍历、中序遍历和后序遍历。下面是这三种遍历方式的C语言代码示例：

前序遍历（Preorder Traversal）：访问当前节点，然后按照左子树和右子树的顺序递归遍历子树。

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

void preorderTraversal(struct TreeNode* root) {
    if (root == NULL) return;
    
    printf("%d ", root->val);  // 访问当前节点
    preorderTraversal(root->left);  // 遍历左子树
    preorderTraversal(root->right);  // 遍历右子树
}

中序遍历（Inorder Traversal）：先遍历左子树，然后访问当前节点，最后遍历右子树。

void inorderTraversal(struct TreeNode* root) {
    if (root == NULL) return;
    
    inorderTraversal(root->left);  // 遍历左子树
    printf("%d ", root->val);  // 访问当前节点
    inorderTraversal(root->right);  // 遍历右子树
}

后序遍历（Postorder Traversal）：先遍历左子树，然后遍历右子树，最后访问当前节点。

void postorderTraversal(struct TreeNode* root) {
    if (root == NULL) return;
    
    postorderTraversal(root->left);  // 遍历左子树
    postorderTraversal(root->right);  // 遍历右子树
    printf("%d ", root->val);  // 访问当前节点
}

Tip：这些深度优先遍历的代码示例可以帮助你理解DFS算法的具体实现。根据不同的遍历顺序，可以灵活选择合适的方式来处理树的节点。

2.2 广度优先遍历（BFS）

广度优先遍历（Breadth-First Search，BFS）是一种用于遍历或搜索树或图的算法。BFS按照广度优先的顺序遍历树的节点，即逐层地访问节点。BFS从根节点开始，先访问根节点，然后按照层级顺序依次访问每一层的节点，直到遍历完所有节点。下面是BFS的C语言代码示例：

#include <stdio.h>

#define MAX_QUEUE_SIZE 100

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

// 队列结构
struct Queue {
    struct TreeNode* data[MAX_QUEUE_SIZE];
    int front;  // 队头指针
    int rear;  // 队尾指针
};

// 初始化队列
void initQueue(struct Queue* queue) {
    queue->front = 0;
    queue->rear = 0;
}

// 入队操作
void enqueue(struct Queue* queue, struct TreeNode* node) {
    if (queue->rear >= MAX_QUEUE_SIZE) {
        printf("Queue is full.\n");
        return;
    }
    
    queue->data[queue->rear] = node;
    queue->rear++;
}

// 出队操作
struct TreeNode* dequeue(struct Queue* queue) {
    if (queue->front == queue->rear) {
        printf("Queue is empty.\n");
        return NULL;
    }
    
    struct TreeNode* node = queue->data[queue->front];
    queue->front++;
    return node;
}

// 广度优先遍历
void breadthFirstTraversal(struct TreeNode* root) {
    if (root == NULL) return;
    
    struct Queue queue;
    initQueue(&queue);
    
    enqueue(&queue, root);  // 根节点入队
    
    while (queue.front != queue.rear) {
        struct TreeNode* node = dequeue(&queue);  // 出队当前节点
        printf("%d ", node->val);  // 访问当前节点
        
        // 将当前节点的左右子节点入队
        if (node->left) {
            enqueue(&queue, node->left);
        }
        if (node->right) {
            enqueue(&queue, node->right);
        }
    }
}

int main() {
    // 构建一棵二叉树作为示例
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = 1;
    root->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->val = 2;
    root->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->val = 3;
    root->left->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->left->val = 4;
    root->left->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->right->val = 5;
    root->right->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->left->val = 6;
    root->right->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->right->val = 7;
    
    // 广度优先遍历
    breadthFirstTraversal(root);
    
    return 0;
}

以上代码示例演示了如何使用队列来实现广度优先遍历。通过维护一个队列，将当前节点的子节点按顺序入队，从而实现按层级遍历的效果。

2.3 树的插入、删除和查找操作及其复杂度

2.3.1 插入操作的时间复杂度和空间复杂度

树的插入操作的时间复杂度和空间复杂度取决于树的类型和结构。以下是常见树结构的插入操作的时间复杂度和空间复杂度：

二叉搜索树（Binary Search Tree，BST）的插入操作：

时间复杂度：
- 最好情况：O(log n)，当树为平衡树时，插入操作的时间复杂度是树的高度，即树的层数。
- 最坏情况：O(n)，当树退化为链表时，插入操作的时间复杂度为树的节点数，即线性时间复杂度。
- 平均情况：O(log n)，在随机插入节点的情况下，树的平衡性得到保持，插入操作的时间复杂度接近树的高度。
空间复杂度：O(1)，插入操作只需分配一个新节点的空间。

平衡树（如AVL树、红黑树）的插入操作：

时间复杂度：
- 最好情况：O(log n)，平衡树保持平衡的特性使得插入操作的时间复杂度保持在树的高度。
- 最坏情况：O(log n)，平衡树的插入操作会触发平衡调整，但这些操作仍然在树的高度范围内。
- 平均情况：O(log n)，平衡树在插入操作后会进行平衡调整，使得树的高度保持较低水平。
空间复杂度：O(1)，插入操作只需分配一个新节点的空间。

Tip：以上的时间复杂度和空间复杂度是基于平衡树的理想情况。在实际应用中，树的平衡性可能会受到数据的分布和插入顺序的影响，导致插入操作的时间复杂度稍有不同。因此，在选择树的类型和实现插入操作时，需要综合考虑数据特点和性能需求。

2.3.2 删除操作的时间复杂度和空间复杂度

树的删除操作的时间复杂度和空间复杂度取决于树的类型和结构。以下是常见树结构的删除操作的时间复杂度和空间复杂度：

二叉搜索树（Binary Search Tree，BST）的删除操作：

时间复杂度：
- 最好情况：O(log n)，当树为平衡树时，删除操作的时间复杂度是树的高度，即树的层数。
- 最坏情况：O(n)，当树退化为链表时，删除操作的时间复杂度为树的节点数，即线性时间复杂度。
- 平均情况：O(log n)，在随机删除节点的情况下，树的平衡性得到保持，删除操作的时间复杂度接近树的高度。
空间复杂度：O(1)，删除操作只需释放被删除节点的空间。

平衡树（如AVL树、红黑树）的删除操作：

时间复杂度：
- 最好情况：O(log n)，平衡树保持平衡的特性使得删除操作的时间复杂度保持在树的高度。
- 最坏情况：O(log n)，平衡树的删除操作会触发平衡调整，但这些操作仍然在树的高度范围内。
- 平均情况：O(log n)，平衡树在删除操作后会进行平衡调整，使得树的高度保持较低水平。
空间复杂度：O(1)，删除操作只需释放被删除节点的空间。

2.3.3 查找操作的时间复杂度和空间复杂度

树的查找操作的时间复杂度和空间复杂度取决于树的类型和结构。以下是常见树结构的查找操作的时间复杂度和空间复杂度：

二叉搜索树（Binary Search Tree，BST）的查找操作：

时间复杂度：
- 最好情况：O(log n)，当树为平衡树时，查找操作的时间复杂度是树的高度，即树的层数。
- 最坏情况：O(n)，当树退化为链表时，查找操作的时间复杂度为树的节点数，即线性时间复杂度。
- 平均情况：O(log n)，在随机查找节点的情况下，树的平衡性得到保持，查找操作的时间复杂度接近树的高度。
空间复杂度：O(1)，查找操作不需要额外的空间。

平衡树（如AVL树、红黑树）的查找操作：

时间复杂度：
- 最好情况：O(log n)，平衡树保持平衡的特性使得查找操作的时间复杂度保持在树的高度。
- 最坏情况：O(log n)，平衡树的查找操作会触发平衡调整，但这些操作仍然在树的高度范围内。
- 平均情况：O(log n)，平衡树在查找操作后会进行平衡调整，使得树的高度保持较低水平。
空间复杂度：O(1)，查找操作不需要额外的空间。

三、图的基本概念和特点

3.1 图的定义和术语

图（Graph）是由节点（Vertex）和边（Edge）组成的非线性数据结构。图中的节点表示实体，边表示节点之间的关系或连接。

术语	解释
节点（Vertex）	也称为顶点或结点，表示图中的实体。
边（Edge）	表示节点之间的连接关系，可以是有向的（指定方向）或无向的（不指定方向）。
权重（Weight）	边可以带有权重，表示节点之间的关联程度或距离。
邻接（Adjacent）	两个节点之间存在边，则它们被称为邻接节点。
入度（In-degree）	有向图中，指向某个节点的边的数量。
出度（Out-degree）	有向图中，从某个节点出发的边的数量。
路径（Path）	图中节点的序列，节点之间通过边连接。
环（Cycle）	路径中起始节点和结束节点相同的路径。
连通性（Connectivity）	图中节点之间是否存在路径，决定了图的连通性。
子图（Subgraph）	由图中的一部分节点和边组成的图。
无向图（Undirected Graph）	边没有方向性，节点之间的关系是双向的。
有向图（Directed Graph）	边具有方向性，节点之间的关系是单向的。

图可以用于表示各种实际问题，如社交网络、路网、电路等。

3.2 有向图和无向图

有向图（Directed Graph）和无向图（Undirected Graph）是图（Graph）中两种常见的类型。

无向图：无向图是一种图形结构，其中边没有方向性，节点之间的关系是双向的。也就是说，如果节点 A 与节点 B 之间存在边，那么可以从节点 A 到节点 B，也可以从节点 B 到节点 A。在无向图中，边表示的是节点之间的相互关系，而不区分起点和终点。
有向图：有向图是一种图形结构，其中边具有方向性，节点之间的关系是单向的。对于有向图中的每条边，有一个起点和一个终点。如果从节点 A 到节点 B 存在一条有向边，那么可以从节点 A 到节点 B，但不能反向。

比较：

连通性：在无向图中，两个节点之间存在边，表示它们之间是相互连通的。而在有向图中，两个节点之间需要同时存在两条边，表示它们之间是双向连通的。
方向性：无向图中的边没有方向性，可以从一个节点到另一个节点，也可以反向。而有向图中的边具有明确的方向性，从一个节点指向另一个节点。
表示方式：无向图可以用一个简单的线段表示边，而有向图的边需要箭头来表示方向。

3.3 图的表示方法

图可以使用多种方式进行表示，以下是几种常见的图表示方法：

邻接矩阵（Adjacency Matrix）：邻接矩阵是一种使用二维数组来表示图的方式。对于包含 N 个节点的图，邻接矩阵是一个 N×N 的矩阵。矩阵中的元素表示节点之间的连接关系，如果两个节点之间存在边，则对应位置的元素为 1 或边的权重值，否则为 0 或者其他特定的表示。邻接矩阵适用于稠密图，其中边的数量相对节点的数量较多。
邻接表（Adjacency List）：邻接表是一种使用链表或数组的列表来表示图的方式。对于每个节点，维护一个与之相邻节点的列表。这可以通过数组或链表的形式实现，其中每个元素表示一个节点，对应的值是一个列表，列出与该节点相邻的节点。邻接表适用于稀疏图，其中边的数量相对节点的数量较少。
关联矩阵（Incidence Matrix）：关联矩阵是一种使用二维数组来表示图的方式，其中行表示节点，列表示边。矩阵中的元素表示节点与边之间的关联关系，通常使用 1 或 -1 来表示节点是边的起点或终点。关联矩阵适用于多重图（允许多个相同节点之间的边）或带有边属性的图。

四、图的遍历和操作

4.1 深度优先遍历（DFS）

以下是使用深度优先遍历（DFS）算法遍历图的示例代码，使用C语言实现：

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

#define MAX_VERTICES 100

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

// 图的结构
struct Graph {
    int numVertices;             // 图中节点的数量
    struct ListNode* adjList[MAX_VERTICES];    // 邻接表数组
    bool visited[MAX_VERTICES];   // 标记节点是否已访问
};

// 初始化图
void initGraph(struct Graph* graph, int numVertices) {
    graph->numVertices = numVertices;
    // 初始化邻接表和visited数组
    for (int i = 0; i < numVertices; ++i) {
        graph->adjList[i] = NULL;
        graph->visited[i] = false;
    }
}

// 添加边
void addEdge(struct Graph* graph, int src, int dest) {
    // 创建新的邻接表节点
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    newNode->vertex = dest;
    newNode->next = graph->adjList[src];
    graph->adjList[src] = newNode;
}

// 深度优先遍历
void DFS(struct Graph* graph, int vertex) {
    // 标记当前节点为已访问
    graph->visited[vertex] = true;
    printf("%d ", vertex);

    // 递归访问当前节点的邻接节点
    struct ListNode* adjNode = graph->adjList[vertex];
    while (adjNode != NULL) {
        int adjVertex = adjNode->vertex;
        if (!graph->visited[adjVertex]) {
            DFS(graph, adjVertex);
        }
        adjNode = adjNode->next;
    }
}

// 测试DFS遍历
int main() {
    struct Graph graph;
    int numVertices = 6;
    initGraph(&graph, numVertices);

    // 添加边
    addEdge(&graph, 0, 1);
    addEdge(&graph, 0, 2);
    addEdge(&graph, 1, 3);
    addEdge(&graph, 2, 4);
    addEdge(&graph, 3, 4);
    addEdge(&graph, 3, 5);

    printf("DFS traversal: ");
    DFS(&graph, 0);

    return 0;
}

以上代码演示了如何使用深度优先遍历算法遍历图。通过创建一个邻接表来表示图的连接关系，并使用一个visited数组来标记节点是否已被访问。在DFS函数中，首先标记当前节点为已访问，并输出节点的值，然后递归地访问当前节点的邻接节点，直到所有节点都被访问过。输出的结果为：DFS traversal: 0 1 3 4 2 5，表示深度优先遍历图从节点0开始的路径。

4.2 广度优先遍历（BFS）

以下是使用广度优先遍历（BFS）算法遍历图的示例代码，使用C语言实现：

#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTICES 100
#define QUEUE_SIZE 100

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

// 图的结构
struct Graph {
    int numVertices;             // 图中节点的数量
    struct ListNode* adjList[MAX_VERTICES];    // 邻接表数组
    bool visited[MAX_VERTICES];   // 标记节点是否已访问
};

// 初始化图
void initGraph(struct Graph* graph, int numVertices) {
    graph->numVertices = numVertices;
    // 初始化邻接表和visited数组
    for (int i = 0; i < numVertices; ++i) {
        graph->adjList[i] = NULL;
        graph->visited[i] = false;
    }
}

// 添加边
void addEdge(struct Graph* graph, int src, int dest) {
    // 创建新的邻接表节点
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    newNode->vertex = dest;
    newNode->next = graph->adjList[src];
    graph->adjList[src] = newNode;
}

// 广度优先遍历
void BFS(struct Graph* graph, int startVertex) {
    bool visited[MAX_VERTICES] = { false };   // 用于标记节点是否已访问
    int queue[QUEUE_SIZE];                    // 队列用于存储待访问的节点
    int front = 0;                            // 队列的前指针
    int rear = 0;                             // 队列的后指针

    // 将起始节点入队并标记为已访问
    queue[rear++] = startVertex;
    visited[startVertex] = true;

    // 开始BFS遍历
    while (front < rear) {
        // 出队一个节点并输出
        int currentVertex = queue[front++];
        printf("%d ", currentVertex);

        // 遍历当前节点的邻接节点
        struct ListNode* adjNode = graph->adjList[currentVertex];
        while (adjNode != NULL) {
            int adjVertex = adjNode->vertex;
            // 如果邻接节点未被访问，则将其入队并标记为已访问
            if (!visited[adjVertex]) {
                queue[rear++] = adjVertex;
                visited[adjVertex] = true;
            }
            adjNode = adjNode->next;
        }
    }
}

// 测试BFS遍历
int main() {
    struct Graph graph;
    int numVertices = 6;
    initGraph(&graph, numVertices);

    // 添加边
    addEdge(&graph, 0, 1);
    addEdge(&graph, 0, 2);
    addEdge(&graph, 1, 3);
    addEdge(&graph, 2, 4);
    addEdge(&graph, 3, 4);
    addEdge(&graph, 3, 5);

    printf("BFS traversal: ");
    BFS(&graph, 0);

    return 0;
}

以上代码演示了如何使用广度优先遍历算法遍历图。通过创建一个邻接表来表示图的连接关系，并使用一个visited数组和队列来辅助遍历。在BFS函数中，首先将起始节点入队并标记为已访问，然后通过不断出队和入队的操作，遍历当前节点的邻接节点，直到队列为空。输出的结果为：BFS traversal: 0 1 2 3 4 5，表示广度优先遍历图从节点0开始的路径。

4.3 图的最短路径算法

常见的两种图的最短路径算法是迪杰斯特拉算法（Dijkstra’s algorithm）和弗洛伊德算法（Floyd’s algorithm）。

迪杰斯特拉算法：迪杰斯特拉算法用于解决单源最短路径问题，即从图中的一个节点出发，计算该节点到其他所有节点的最短路径。下面是使用C语言实现的迪杰斯特拉算法示例代码：

#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTICES 100
#define INF 9999

// 图的结构
struct Graph {
    int numVertices;      // 图中节点的数量
    int adjacencyMatrix[MAX_VERTICES][MAX_VERTICES];   // 邻接矩阵表示图的连接关系
};

// 迪杰斯特拉算法
void Dijkstra(struct Graph* graph, int startVertex) {
    int dist[MAX_VERTICES];     // 存储起始节点到各个节点的最短距离
    bool visited[MAX_VERTICES]; // 标记节点是否已被访问

    // 初始化距离数组和visited数组
    for (int i = 0; i < graph->numVertices; ++i) {
        dist[i] = INF;
        visited[i] = false;
    }

    // 起始节点距离设为0
    dist[startVertex] = 0;

    // 找到剩余节点中距离最小的节点
    for (int i = 0; i < graph->numVertices - 1; ++i) {
        int minDist = INF;
        int minIndex = -1;

        // 遍历节点找到距离最小的节点
        for (int j = 0; j < graph->numVertices; ++j) {
            if (!visited[j] && dist[j] < minDist) {
                minDist = dist[j];
                minIndex = j;
            }
        }

        // 将找到的最小距离节点标记为已访问
        visited[minIndex] = true;

        // 更新与该节点相邻节点的最短距离
        for (int j = 0; j < graph->numVertices; ++j) {
            if (!visited[j] && graph->adjacencyMatrix[minIndex][j] && dist[minIndex] != INF && dist[minIndex] + graph->adjacencyMatrix[minIndex][j] < dist[j]) {
                dist[j] = dist[minIndex] + graph->adjacencyMatrix[minIndex][j];
            }
        }
    }

    // 输出最短路径
    printf("Shortest paths from vertex %d:\n", startVertex);
    for (int i = 0; i < graph->numVertices; ++i) {
        printf("%d -> %d: %d\n", startVertex, i, dist[i]);
    }
}

// 测试迪杰斯特拉算法
int main() {
    struct Graph graph;
    int numVertices = 6;
    graph.numVertices = numVertices;

    // 初始化邻接矩阵
    for (int i = 0; i < numVertices; ++i) {
        for (int j = 0; j < numVertices; ++j) {
            graph.adjacencyMatrix[i][j] = INF;
        }
    }

    // 添加图的边
    graph.adjacencyMatrix[0][1] = 2;
    graph.adjacencyMatrix[0][2] = 4;
    graph.adjacencyMatrix[1][2] = 1;
    graph.adjacencyMatrix[1][3] = 7;
    graph.adjacencyMatrix[2][4] = 3;
    graph.adjacencyMatrix[3][4] = 1;
    graph.adjacencyMatrix[3][5] = 5;
    graph.adjacencyMatrix[4][5] = 2;

    int startVertex = 0;    // 起始节点
    Dijkstra(&graph, startVertex);

    return 0;
}

弗洛伊德算法：弗洛伊德算法用于解决多源最短路径问题，即计算图中任意两个节点之间的最短路径。下面是使用C语言实现的弗洛伊德算法示例代码：

#include <stdio.h>
#define MAX_VERTICES 100
#define INF 9999

// 图的结构
struct Graph {
    int numVertices;      // 图中节点的数量
    int adjacencyMatrix[MAX_VERTICES][MAX_VERTICES];   // 邻接矩阵表示图的连接关系
};

// 弗洛伊德算法
void Floyd(struct Graph* graph) {
    int dist[MAX_VERTICES][MAX_VERTICES];    // 存储任意两个节点之间的最短距离

    // 初始化距离矩阵
    for (int i = 0; i < graph->numVertices; ++i) {
        for (int j = 0; j < graph->numVertices; ++j) {
            dist[i][j] = graph->adjacencyMatrix[i][j];
        }
    }

    // 计算最短路径
    for (int k = 0; k < graph->numVertices; ++k) {
        for (int i = 0; i < graph->numVertices; ++i) {
            for (int j = 0; j < graph->numVertices; ++j) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    // 输出最短路径
    printf("Shortest paths between all pairs of vertices:\n");
    for (int i = 0; i < graph->numVertices; ++i) {
        for (int j = 0; j < graph->numVertices; ++j) {
            printf("%d -> %d: %d\n", i, j, dist[i][j]);
        }
    }
}

// 测试弗洛伊德算法
int main() {
    struct Graph graph;
    int numVertices = 4;
    graph.numVertices = numVertices;

    // 初始化邻接矩阵
    for (int i = 0; i < numVertices; ++i) {
        for (int j = 0; j < numVertices; ++j) {
            graph.adjacencyMatrix[i][j] = INF;
        }
    }

    // 添加图的边
    graph.adjacencyMatrix[0][1] = 3;
    graph.adjacencyMatrix[0][2] = 6;
    graph.adjacencyMatrix[1][0] = 3;
    graph.adjacencyMatrix[1][2] = 2;
    graph.adjacencyMatrix[1][3] = 1;
    graph.adjacencyMatrix[2][0] = 6;
    graph.adjacencyMatrix[2][1] = 2;
    graph.adjacencyMatrix[2][3] = 4;
    graph.adjacencyMatrix[3][1] = 1;
    graph.adjacencyMatrix[3][2] = 4;

    Floyd(&graph);

    return 0;
}

4.4 图的最小生成树算法

图的最小生成树算法主要用于找到一个连通图的最小生成树，即连接图中所有节点的边的集合，且边的权重之和最小。常见的最小生成树算法包括普里姆算法和克鲁斯卡尔算法。

普里姆算法：普里姆算法是一种贪心算法，从一个起始节点开始，逐步选择与当前生成树相连的最短边，并将相连的节点加入生成树，直到生成树包含了所有节点为止。以下是使用C语言实现的普里姆算法示例代码：

#include <stdio.h>
#define MAX_VERTICES 100
#define INF 9999

// 图的结构
struct Graph {
    int numVertices;      // 图中节点的数量
    int adjacencyMatrix[MAX_VERTICES][MAX_VERTICES];   // 邻接矩阵表示图的连接关系
};

// 普里姆算法
void Prim(struct Graph* graph) {
    int selected[MAX_VERTICES];     // 记录节点是否已加入生成树
    int parent[MAX_VERTICES];       // 记录节点的父节点
    int minWeight[MAX_VERTICES];    // 记录节点与生成树的最小权重

    // 初始化
    for (int i = 0; i < graph->numVertices; ++i) {
        selected[i] = 0;
        minWeight[i] = INF;
    }

    // 设置起始节点
    int startVertex = 0;
    minWeight[startVertex] = 0;
    parent[startVertex] = -1;

    // 生成最小生成树
    for (int i = 0; i < graph->numVertices - 1; ++i) {
        // 选择最小权重的节点
        int minWeightIndex = -1;
        for (int j = 0; j < graph->numVertices; ++j) {
            if (!selected[j] && (minWeightIndex == -1 || minWeight[j] < minWeight[minWeightIndex])) {
                minWeightIndex = j;
            }
        }

        // 将节点加入生成树
        selected[minWeightIndex] = 1;

        // 更新相邻节点的权重
        for (int j = 0; j < graph->numVertices; ++j) {
            if (!selected[j] && graph->adjacencyMatrix[minWeightIndex][j] != INF && graph->adjacencyMatrix[minWeightIndex][j] < minWeight[j]) {
                parent[j] = minWeightIndex;
                minWeight[j] = graph->adjacencyMatrix[minWeightIndex][j];
            }
        }
    }

    // 输出最小生成树
    printf("Minimum Spanning Tree:\n");
    for (int i = 1; i < graph->numVertices; ++i) {
        printf("%d - %d\n", parent[i], i);
    }
}

// 测试普里姆算法
int main() {
    struct Graph graph;
    int numVertices = 5;
    graph.numVertices = numVertices;

    // 初始化邻接矩阵
    for (int i = 0; i < numVertices; ++i) {
        for (int j = 0; j < numVertices; ++j) {
            graph.adjacencyMatrix[i][j] = INF;
        }
    }

    // 添加图的边
    graph.adjacencyMatrix[0][1] = 2;
    graph.adjacencyMatrix[0][3] = 6;
    graph.adjacencyMatrix[1][0] = 2;
    graph.adjacencyMatrix[1][2] = 3;
    graph.adjacencyMatrix[1][3] = 8;
    graph.adjacencyMatrix[1][4] = 5;
    graph.adjacencyMatrix[2][1] = 3;
    graph.adjacencyMatrix[2][4] = 7;
    graph.adjacencyMatrix[3][0] = 6;
    graph.adjacencyMatrix[3][1] = 8;
    graph.adjacencyMatrix[4][1] = 5;
    graph.adjacencyMatrix[4][2] = 7;

    Prim(&graph);

    return 0;
}

克鲁斯卡尔算法：克鲁斯卡尔算法是一种基于边的贪心算法，它按照边的权重递增的顺序，逐步选择不会形成环路的边，直到生成树包含了所有节点为止。以下是使用C语言实现的克鲁斯卡尔算法示例代码：

#include <stdio.h>
#define MAX_EDGES 100
#define MAX_VERTICES 100

// 边的结构
struct Edge {
    int source;     // 边的起始节点
    int destination;    // 边的目标节点
    int weight;     // 边的权重
};

// 图的结构
struct Graph {
    int numVertices;      // 图中节点的数量
    int numEdges;         // 图中边的数量
    struct Edge edges[MAX_EDGES];   // 图中的边
};

// 比较函数，用于边的排序
int compare(const void* a, const void* b) {
    struct Edge* edgeA = (struct Edge*)a;
    struct Edge* edgeB = (struct Edge*)b;
    return edgeA->weight - edgeB->weight;
}

// 查找节点的根节点
int findRoot(int parent[], int vertex) {
    while (parent[vertex] != -1) {
        vertex = parent[vertex];
    }
    return vertex;
}

// 克鲁斯卡尔算法
void Kruskal(struct Graph* graph) {
    int parent[MAX_VERTICES];   // 记录节点的父节点
    struct Edge result[MAX_VERTICES];   // 记录最小生成树的边

    // 初始化父节点
    for (int i = 0; i < graph->numVertices; ++i) {
        parent[i] = -1;
    }

    // 对边进行排序
    qsort(graph->edges, graph->numEdges, sizeof(struct Edge), compare);
    int edgeCount = 0;    // 记录已选择的边的数量
    int i = 0;    // 记录当前考虑的边的索引

    // 选择边，直到生成树包含了所有节点为止


    while (edgeCount < graph->numVertices - 1) {
        struct Edge currentEdge = graph->edges[i];

        int sourceRoot = findRoot(parent, currentEdge.source);
        int destinationRoot = findRoot(parent, currentEdge.destination);

        // 如果边的起始节点和目标节点不在同一个连通分量中，则选择该边
        if (sourceRoot != destinationRoot) {
            result[edgeCount++] = currentEdge;
            parent[sourceRoot] = destinationRoot;
        }

        i++;
    }

    // 输出最小生成树
    printf("Minimum Spanning Tree:\n");
    for (int i = 0; i < edgeCount; ++i) {
        printf("%d - %d\n", result[i].source, result[i].destination);
    }
}

// 测试克鲁斯卡尔算法
int main() {
    struct Graph graph;
    int numVertices = 5;
    int numEdges = 7;
    graph.numVertices = numVertices;
    graph.numEdges = numEdges;

    // 添加图的边
    graph.edges[0].source = 0;
    graph.edges[0].destination = 1;
    graph.edges[0].weight = 2;

    graph.edges[1].source = 0;
    graph.edges[1].destination = 3;
    graph.edges[1].weight = 6;

    graph.edges[2].source = 1;
    graph.edges[2].destination = 2;
    graph.edges[2].weight = 3;

    graph.edges[3].source = 1;
    graph.edges[3].destination = 3;
    graph.edges[3].weight = 8;

    graph.edges[4].source = 1;
    graph.edges[4].destination = 4;
    graph.edges[4].weight = 5;

    graph.edges[5].source = 2;
    graph.edges[5].destination = 4;
    graph.edges[5].weight = 7;

    graph.edges[6].source = 3;
    graph.edges[6].destination = 4;
    graph.edges[6].weight = 9;

    Kruskal(&graph);
    return 0;
}

五、经典面试题

经典面试题1：给定一个二叉树，判断它是否是对称的，即左子树和右子树镜像对称。 解题思路： 可以使用递归的方式来解决该问题。判断一棵二叉树是否对称可以转化为判断它的左子树和右子树是否镜像对称。具体步骤如下：

如果二叉树为空，直接返回 true。
否则，递归判断左子树和右子树是否镜像对称，判断条件为：
- 左子树的左子树和右子树的右子树是否镜像对称。
- 左子树的右子树和右子树的左子树是否镜像对称。
如果上述条件都满足，则二叉树是对称的。

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

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

// 辅助函数，判断两棵二叉树是否镜像对称
bool isSymmetricHelper(struct TreeNode* leftNode, struct TreeNode* rightNode) {
    // 左子树和右子树都为空，是对称的
    if (leftNode == NULL && rightNode == NULL) {
        return true;
    }
    // 左子树和右子树其中一个为空，不对称
    if (leftNode == NULL || rightNode == NULL) {
        return false;
    }
    // 当前节点的值相等，并且左子树的左子树和右子树的右子树对称
    // 左子树的右子树和右子树的左子树对称时，才是对称的
    return (leftNode->val == rightNode->val) &&
           isSymmetricHelper(leftNode->left, rightNode->right) &&
           isSymmetricHelper(leftNode->right, rightNode->left);
}

// 主函数，判断二叉树是否对称
bool isSymmetric(struct TreeNode* root) {
    if (root == NULL) {
        return true;
    }
    return isSymmetricHelper(root->left, root->right);
}

// 测试函数
int main() {
    // 构建二叉树
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = 1;

    struct TreeNode* node2 = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node2->val = 2;

    struct TreeNode* node3 = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node3->val = 2;

    struct TreeNode* node4 = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node4->val = 3;

    struct TreeNode* node5 = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node5->val = 3;

    root->left = node2;
    root->right = node3;
    node2->left = node4;
    node2->

right = NULL;
    node3->left = NULL;
    node3->right = node5;
    node4->left = NULL;
    node4->right = NULL;
    node5->left = NULL;
    node5->right = NULL;

    // 判断二叉树是否对称
    bool result = isSymmetric(root);

    if (result) {
        printf("The binary tree is symmetric.\n");
    } else {
        printf("The binary tree is not symmetric.\n");
    }

    return 0;
}

上述代码中，我们构建了一个对称的二叉树，并通过判断函数判断了该二叉树是否对称。输出结果表明该二叉树是对称的。

经典面试题2：给定一个无向图，通过深度优先遍历算法遍历图中的所有节点。 解题思路： 深度优先遍历（DFS）是一种递归的遍历算法，它从一个起始节点开始，沿着一条路径尽可能深地遍历图，直到无法继续为止，然后回溯到上一个节点，再选择另一条未访问过的路径继续遍历，直到所有节点都被访问。

创建一个visited数组，用于记录每个节点是否被访问过。
从起始节点开始进行递归遍历，具体步骤为：
- 标记当前节点为已访问。
- 遍历当前节点的邻接节点，如果邻接节点未被访问，则递归遍历该节点。
最终，所有节点都被访问过后，遍历结束。

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

#define MAX_VERTICES 100

struct Graph {
    int numVertices;
    bool adjMatrix[MAX_VERTICES][MAX_VERTICES];
};

void DFS(struct Graph* graph, int vertex, bool visited[]) {
    visited[vertex] = true;
    printf("Visited vertex: %d\n", vertex);

    for (int i = 0; i < graph->numVertices; ++i) {
        if (graph->adjMatrix[vertex][i] && !visited[i]) {
            DFS(graph, i, visited);
        }
    }
}

void depthFirstSearch(struct Graph* graph, int startVertex) {
    bool visited[MAX_VERTICES] = {false};

    DFS(graph, startVertex, visited);
}

// 测试函数
int main() {
    struct Graph graph;
    int numVertices = 6;
    graph.numVertices = numVertices;

    // 初始化邻接矩阵
    for (int i = 0; i < numVertices; ++i) {
        for (int j = 0; j < numVertices; ++j) {
            graph.adjMatrix[i][j] = false;
        }
    }

    // 添加边
    graph.adjMatrix[0][1] = true;
    graph.adjMatrix[0][2] = true;
    graph.adjMatrix

[1][3] = true;
    graph.adjMatrix[1][4] = true;
    graph.adjMatrix[2][5] = true;

    int startVertex = 0;

    // 执行深度优先遍历
    depthFirstSearch(&graph, startVertex);

    return 0;
}

上述代码中，我们创建了一个无向图，并使用深度优先遍历算法遍历了该图的所有节点。输出结果按照访问顺序打印了节点编号。