本文还有配套的精品资源，点击获取

简介：数据结构是计算机科学的基础，严蔚敏教授的教材以实例详细阐述了数据的有效存储、组织及操作。本书不仅包含了C和C++语言实现的数据结构，还详细介绍了线性结构、栈、树、图、排序和查找等关键概念，帮助读者深入理解并应用于实际编程。源代码的使用增强了学习者的实践能力，并对数据结构的内存管理与算法应用有了更加直观的认识。

1. 数据结构核心概念

数据结构是计算机存储、组织数据的方式，是算法设计的基石。本章节将从数据结构的基本概念开始，逐步引导读者理解数据结构的类别、存储方式、操作及其重要性。对于任何从事软件开发的人员而言，掌握良好的数据结构知识能够显著提高程序性能与资源管理效率。

1.1 数据结构的基本概念

数据结构是关于数据如何组织、存储的数学理论和计算机实现技术。它涉及到数据的逻辑结构、物理存储以及数据的操作方法。数据结构服务于算法，它们是密不可分的。

1.2 数据的逻辑结构

逻辑结构是指数据元素之间的关系，它不依赖于数据元素在计算机中的存储位置。逻辑结构包括集合、线性结构、树形结构和图状结构。理解这些逻辑结构是设计高效数据结构的前提。

1.3 数据的物理结构

物理结构是指数据的逻辑结构在计算机内存中的表示，即数据的存储结构。常见的物理存储结构有顺序存储结构（数组）和链式存储结构（链表）。

通过本章内容，读者将对数据结构有一个全面的理解，为深入学习数据结构和相关算法奠定坚实的基础。

2. C/C++编程语言实现数据结构

C/C++语言因其强大的性能和灵活的操作而成为实现数据结构的首选语言。本章将回顾C/C++的基本语言特性，探讨面向对象编程在数据结构实现中的应用，以及如何有效地管理内存。

2.1 C/C++语言基础回顾

2.1.1 C/C++语言的特性与应用领域

C/C++语言以其高性能、系统级操作能力而广受开发者喜爱。C语言强调运行效率和硬件操作，使其在操作系统、嵌入式系统开发中占据主导地位。C++则在C语言的基础上增加了面向对象编程（OOP）的特性，使其在复杂系统开发、游戏开发、高性能服务器等领域得到广泛应用。

应用领域分析

• 操作系统： Linux内核和许多Unix系统使用C语言编写，因为C语言提供了接近硬件的编程能力。
• 嵌入式系统： C语言用于许多嵌入式设备的开发，如微控制器编程，因为其代码紧凑且执行效率高。
• 游戏开发： C++由于其对象继承、多态等特性，成为游戏开发的首选语言之一。
• 高性能计算： C++用于编写高性能的应用程序，如科学计算、金融服务行业的量化交易软件。
• 桌面应用和服务器应用： C++提供了丰富的库和框架，用于构建复杂、高性能的桌面应用和服务器端应用。

2.1.2 C/C++数据类型与运算符

C/C++提供了丰富的数据类型和运算符，这些是构建复杂数据结构的基础。

数据类型概述

• 基本数据类型： 包括 int , char , float , double 等，用于存储数值、字符和浮点数。
• 复合数据类型： 如 struct , class , union , enum 等，用于表示更复杂的数据结构。
• 指针类型： 允许存储内存地址，是C/C++语言处理动态内存和数据结构不可或缺的部分。

运算符详细说明

• 算术运算符： 如 + , - , * , / , % 用于执行基本数学运算。
• 关系运算符： 如 == , != , > , < , >= , <= 用于比较两个值。
• 逻辑运算符： 如 && , || , ! 用于组合条件表达式。
• 位运算符： 如 & , | , ^ , << , >> 用于直接操作内存中的位。
• 赋值运算符： 如 = 及复合赋值运算符 += , -= , *= , /= 等用于赋值操作。

2.2 面向对象的C++数据结构

面向对象编程是C++的核心特征之一，它提供了一种全新的方式来构建和组织程序代码。

2.2.1 类和对象的定义与使用

类是C++中创建新数据类型的基石，而对象则是类的实例。

类的定义与组件

• 成员变量： 定义对象的属性。
• 成员函数： 描述对象的行为。

class Book {
public:
    void setTitle(const std::string& title);
    void setAuthor(const std::string& author);
    std::string getTitle() const;
    std::string getAuthor() const;

private:
    std::string title;
    std::string author;
};

对象的创建与使用

• 通过 new 关键字动态创建对象。
• 通过成员函数访问和修改对象的内部状态。

Book* book = new Book();
book->setTitle("C++ Primer");
book->setAuthor("Stanley B. Lippman");

2.2.2 继承、封装与多态在数据结构中的应用

继承、封装和多态是面向对象编程的三大特性，它们在数据结构设计中发挥着重要的作用。

继承

继承允许创建具有父类属性和方法的新类，它增强了代码的复用性。

class TextBook : public Book {
public:
    void setPublisher(const std::string& publisher) {
        this->publisher = publisher;
    }

private:
    std::string publisher;
};

封装

封装隐藏了对象的内部实现细节，只暴露接口，增加了代码的安全性。

class Stack {
private:
    int* elements;
    int maxSize;
    int top;

public:
    Stack(int size);
    void push(int value);
    int pop();
    bool isEmpty() const;
    ~Stack();
};

多态

多态允许通过基类指针或引用调用派生类的方法，增强了程序的灵活性。

void processStack(Stack& stack) {
    while (!stack.isEmpty()) {
        int element = stack.pop();
        // Process the element.
    }
}

2.3 指针与内存管理

在C++中，指针是处理内存地址和数据动态分配的核心工具。正确的内存管理对于创建高效且稳定的程序至关重要。

2.3.1 指针的基本概念与操作

指针存储了变量的内存地址，通过指针可以间接访问和操作数据。

指针的声明与使用

int value = 5;
int* ptr = &value; // 指针声明并指向value变量的地址
std::cout << *ptr; // 输出指针指向地址上的值，即5

指针与数组

指针可以用于访问和操作数组。

int arr[] = {10, 20, 30};
int* ptr = arr; // 指针指向数组第一个元素的地址
std::cout << *(ptr + 1); // 输出数组第二个元素的值，即20

2.3.2 动态内存分配与释放技术

动态内存分配允许程序在运行时根据需要分配内存，而释放内存则需要程序员手动管理，以避免内存泄漏。

使用 new 和 delete 关键字

int* ptr = new int; // 动态分配内存给一个整数
*ptr = 15;          // 对分配的内存赋值
delete ptr;         // 释放分配的内存

动态数组的内存管理

int* arr = new int[10]; // 动态分配一个大小为10的整数数组
delete[] arr;           // 释放动态数组占用的内存

内存泄漏的风险与防范

在C++中，忘记释放动态分配的内存会导致内存泄漏。现代C++实践中，推荐使用智能指针如 std::unique_ptr 和 std::shared_ptr 来自动管理内存。

#include <memory>

std::unique_ptr<int> ptr = std::make_unique<int>(15); // 使用智能指针自动管理内存

本章节的详细介绍旨在为读者提供一个C/C++语言实现数据结构的全面概述，从基础语法的应用到面向对象编程的高级特性，再到内存管理的深入探讨，为理解和实现数据结构奠定了坚实的理论基础和实践指导。

3. 线性结构的实现与应用

3.1 线性表的实现

3.1.1 静态数组与链表的比较

线性表是数据结构中最基础和常见的结构之一，它代表了一系列有序的元素。在C/C++中，线性表可以通过静态数组或链表来实现。静态数组分配固定大小的内存空间，而链表则采用动态内存分配，每个节点包含数据和指向下一个节点的指针。

静态数组的优点在于访问速度快，因为它们在内存中连续存储。但缺点是其大小在定义时就固定了，不够灵活。对于链表而言，其优点是可以动态伸缩，适合大小未知或不断变化的数据集。缺点是由于内存不连续，访问速度较慢，并且需要额外的内存来存储指针信息。

为了对比这两种结构的性能差异，可以考虑实现一个简单的线性表，并对其中的元素进行插入、删除和查找等操作。以下是使用静态数组和链表分别实现的代码示例及其性能分析。

// 静态数组实现线性表
class StaticArrayLinearList {
private:
    int array[100]; // 假设线性表最多存储100个元素
    int size;        // 当前存储的元素数量

public:
    StaticArrayLinearList() : size(0) {}

    void insert(int index, int value) {
        if (size >= 100) return;
        if (index < 0 || index > size) return;
        for (int i = size; i > index; --i) {
            array[i] = array[i-1];
        }
        array[index] = value;
        size++;
    }

    // 其他线性表操作...
};

// 链表实现线性表
struct ListNode {
    int data;
    ListNode* next;
    ListNode(int val) : data(val), next(nullptr) {}
};

class LinkedListLinearList {
private:
    ListNode* head; // 链表头指针

public:
    LinkedListLinearList() : head(nullptr) {}

    void insert(int index, int value) {
        if (index < 0) return;

        ListNode* newNode = new ListNode(value);
        if (index == 0) {
            newNode->next = head;
            head = newNode;
        } else {
            ListNode* current = head;
            for (int i = 0; i < index - 1 && current != nullptr; i++) {
                current = current->next;
            }
            if (current != nullptr) {
                newNode->next = current->next;
                current->next = newNode;
            }
        }
    }

    // 其他线性表操作...
};

在上述代码中，静态数组和链表的 insert 操作被展示出来。对于静态数组来说，插入操作需要移动部分元素以腾出空间，时间复杂度为O(n)。而链表插入操作平均时间复杂度为O(1)，在尾部插入时更可达到O(1)。

3.1.2 单链表、双链表及循环链表的实现细节

单链表是一种基本的链表结构，每个节点由数据和指向下一个节点的指针组成。在单链表中，节点不持有对前一个节点的引用，使得从尾部向前遍历变得不直接。为了解决这个问题，引入了双链表，双链表中的每个节点除了存储下一个节点的指针，还存储了前一个节点的指针。

循环链表则是链表的一种特殊形式，其中最后一个节点的next指针指向链表的头节点，形成一个环。循环链表对于某些特定的应用场景特别有用，例如，约瑟夫问题（Josephus Problem）。

// 双链表节点定义
struct DoublyListNode {
    int data;
    DoublyListNode* prev;
    DoublyListNode* next;
    DoublyListNode(int val) : data(val), prev(nullptr), next(nullptr) {}
};

// 双链表实现
class DoublyLinkedList {
private:
    DoublyListNode* head;
    DoublyListNode* tail;

public:
    DoublyLinkedList() : head(nullptr), tail(nullptr) {}

    void insert(int index, int value) {
        // 双链表的插入操作代码省略...
    }

    // 其他双链表操作...
};

// 循环链表节点定义
struct CircularListNode {
    int data;
    CircularListNode* next;
    CircularListNode(int val) : data(val), next(nullptr) {}
};

// 循环链表实现
class CircularLinkedList {
private:
    CircularListNode* head;

public:
    CircularLinkedList() : head(nullptr) {}

    void insert(int index, int value) {
        // 循环链表的插入操作代码省略...
    }

    // 其他循环链表操作...
};

在实现细节上，双链表和循环链表主要增加和修改了节点之间的指针关系。对于双链表，需要在插入和删除操作时维护 prev 指针，而对于循环链表，最后一个节点的 next 指针需指向头节点。这些操作的实现需要小心处理各种边界情况以确保链表结构的正确性。

链表结构的实现和操作是面试和编程竞赛中的热门问题，掌握这些知识点对于任何希望深化数据结构理解的开发者来说都是必不可少的。通过编写和测试这些数据结构的代码，开发者能够更深入地理解指针和内存管理，这对编写高质量的程序至关重要。

4. 栈的基本操作与应用场景

栈是一种遵循后进先出（LIFO）原则的抽象数据结构，它有两个基本操作：进栈（push）和出栈（pop）。在很多编程问题中，栈都有其独特的应用方式，尤其在表达式求值和算法设计中。

4.1 栈的基本操作原理

4.1.1 栈的进栈、出栈和栈顶操作

栈的进栈（push）操作是指在栈顶添加一个元素，而出栈（pop）操作则是移除栈顶元素并返回。栈顶操作（peek）用于查看栈顶元素但不移除它。在C/C++中，这些操作可以通过数组或者链表实现。下面是一个使用数组实现栈的简单示例：

#include <stdio.h>
#define MAXSIZE 10 // 定义栈的最大容量

typedef struct {
    int data[MAXSIZE]; // 存储栈元素的数组
    int top;           // 栈顶指针
} Stack;

// 初始化栈
void initStack(Stack *s) {
    s->top = -1;
}

// 判断栈是否为空
int isEmpty(Stack *s) {
    return s->top == -1;
}

// 判断栈是否已满
int isFull(Stack *s) {
    return s->top == MAXSIZE - 1;
}

// 进栈操作
int push(Stack *s, int element) {
    if (isFull(s)) {
        printf("Stack overflow\n");
        return 0;
    }
    s->data[++s->top] = element; // 先移动栈顶指针，再赋值
    return 1;
}

// 出栈操作
int pop(Stack *s, int *element) {
    if (isEmpty(s)) {
        printf("Stack underflow\n");
        return 0;
    }
    *element = s->data[s->top--]; // 先取值，再移动栈顶指针
    return 1;
}

// 获取栈顶元素
int peek(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty\n");
        return -1;
    }
    return s->data[s->top];
}

int main() {
    Stack s;
    initStack(&s);
    push(&s, 10);
    push(&s, 20);
    int topElement;
    printf("Stack top element is %d\n", peek(&s)); // 输出栈顶元素
    pop(&s, &topElement);
    printf("Popped element is %d\n", topElement);
    return 0;
}

4.1.2 栈的应用实例：表达式求值

栈的一个经典应用是表达式求值，特别是后缀表达式（也称为逆波兰表达式）的计算。在后缀表达式中，运算符位于其操作数之后。例如，中缀表达式 (3 + 4) * 5 对应的后缀表达式是 3 4 + 5 * 。

为了计算后缀表达式，我们使用一个栈来存储操作数。遍历后缀表达式中的每个元素，如果是操作数，就进栈；如果是运算符，就从栈中弹出两个操作数，执行相应的运算，然后将结果压入栈中。下面是一个计算后缀表达式的函数：

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

int evaluatePostfix(char* expression) {
    Stack s;
    initStack(&s);

    int i = 0;
    while (expression[i] != '\0') {
        if (isdigit(expression[i])) {
            int val = 0;
            while (isdigit(expression[i])) {
                val = val * 10 + (expression[i] - '0');
                i++;
            }
            push(&s, val);
            i--; // 因为for循环中的i++会被执行
        } else if (expression[i] == '+' || expression[i] == '-' || 
                   expression[i] == '*' || expression[i] == '/') {
            int op2 = pop(&s, NULL);
            int op1 = pop(&s, NULL);

            switch (expression[i]) {
                case '+': push(&s, op1 + op2); break;
                case '-': push(&s, op1 - op2); break;
                case '*': push(&s, op1 * op2); break;
                case '/': push(&s, op1 / op2); break;
            }
        } else {
            // 无效的表达式
            return -1;
        }
    }
    return pop(&s, NULL);
}

int main() {
    char postExp[] = "100 200 + 2 / 5 * 7 +";
    printf("The value of the postfix expression %s is %d\n", postExp, evaluatePostfix(postExp));
    return 0;
}

4.2 栈在算法中的应用

4.2.1 栈与递归算法的关联

递归算法中，每次递归调用都相当于一个压栈操作，递归返回时相当于出栈操作。栈在这里隐式存在，并被自动管理。例如，计算阶乘的递归函数：

int factorial(int n) {
    if (n <= 1) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

在上面的函数中，每次调用 factorial 都会将当前的 n 压入调用栈，然后执行下一层递归。当递归到达基本情况（ n <= 1 ）时，开始出栈并返回结果。

4.2.2 栈在深度优先搜索中的角色

深度优先搜索（DFS）是图和树的遍历算法，它使用栈来存储路径。在遍历过程中，遇到新节点就进行递归搜索，搜索时将当前路径压入栈中。当访问到的节点没有未探索的邻居时，回溯到上一个节点（出栈）。

一个简单的深度优先搜索实现如下：

void dfs(int v, int visited[], Stack *path, int graph[][5], int n) {
    push(path, v);
    visited[v] = 1;
    printf("Visited %d\n", v);

    for (int i = 0; i < n; i++) {
        if (graph[v][i] && !visited[i]) {
            dfs(i, visited, path, graph, n);
        }
    }

    // 如果没有邻居节点，则回溯
    if (isEmpty(path)) {
        int temp;
        pop(path, &temp);
    }
}

以上代码段展示了如何利用栈在DFS算法中进行路径存储和回溯操作。

以上为第四章的内容，详细介绍了栈的基本操作原理和应用场景，包括栈的操作、表达式求值、递归算法的栈机制以及深度优先搜索中的应用。通过这些内容，读者能够深入理解栈这种数据结构的功能及其在算法中如何起到关键作用。

5. 树结构的构建与遍历

5.1 树的概念与分类

5.1.1 二叉树的定义与性质

二叉树是一种每个节点最多有两个子树的树结构，通常子树被称作“左子树”和“右子树”。二叉树在计算机科学中有着广泛的应用，因为它们在许多情况下可以大大简化数据结构的复杂度，尤其是在搜索、排序和查找应用中。

在深度优先搜索中，二叉树是一种特殊的数据结构，它允许我们用递归方法来遍历每个节点。在广度优先搜索中，我们可以使用队列来按层次遍历树中的节点。

一个二叉树的性质包括：

• 第i层的节点数目最多为2^(i-1)个（i >= 1）。
• 对于任意一棵二叉树，如果叶子节点数目为n0，度为2的节点数目为n2，则n0 = n2 + 1。

这些性质是了解二叉树复杂性的基础，并且在实现和分析算法时非常重要。

5.1.2 平衡树、B树与红黑树的特点与应用场景

平衡树是一种自平衡的二叉搜索树，其中任何节点的两个子树的高度差不会超过一。AVL树是最常见的平衡树，它通过旋转操作来维护树的平衡。平衡树特别适用于需要频繁插入和删除操作的场景，因为它们可以保持较低的高度，从而降低查找和更新操作的时间复杂度至O(log n)。

B树是一种平衡的多路搜索树，适用于读写大块数据的存储系统，如数据库和文件系统。由于B树可以拥有两个以上的子节点，它特别适合于磁盘操作，因为它减少了磁盘I/O次数。

红黑树是一种自平衡的二叉搜索树，它通过特定的红黑属性来维护树的平衡。红黑树在插入和删除操作上保证最坏情况下仍然能够达到O(log n)的性能，由于其良好的性能特性，它常用于实现关联数组，如C++ STL中的map和set。

以下是红黑树的一个基本性质，它定义了节点颜色和树结构的约束：

• 每个节点要么是红的，要么是黑的。
• 根节点是黑的。
• 每个叶子节点（NIL节点，空节点）是黑的。
• 如果一个节点是红的，那么它的两个子节点都是黑的。
• 对于每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑节点。

这些性质确保了树大体上是平衡的。

5.2 树的遍历算法

5.2.1 前序、中序与后序遍历的实现

树的遍历算法是算法和数据结构中的基本主题之一。有三种主要的遍历方法：前序遍历、中序遍历和后序遍历。

在前序遍历中，节点的访问顺序是“根-左-右”。在中序遍历中，节点的访问顺序是“左-根-右”。在后序遍历中，节点的访问顺序是“左-右-根”。每种方法都可以通过递归或迭代的方式实现。

这里是一个递归实现的中序遍历函数，假设我们有一个二叉树节点的结构体定义如下：

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

递归版本的中序遍历代码：

void inorderTraversal(struct TreeNode* root) {
    if (root == NULL) return;
    inorderTraversal(root->left);
    printf("%d ", root->val); // 处理根节点
    inorderTraversal(root->right);
}

该函数首先检查当前节点是否为空，如果不为空，则递归地调用左子树、处理根节点、递归地调用右子树。

5.2.2 层次遍历及其算法优化

层次遍历是一种按层次逐行遍历树的算法。它通常使用队列来实现。从根节点开始，我们首先访问根节点，然后将根节点的所有非空子节点入队。接着，我们按照出队顺序访问下一层的节点，并重复此过程，直到队列为空。

以下是一个层次遍历的实现：

void levelOrderTraversal(struct TreeNode* root) {
    if (root == NULL) return;
    struct TreeNode* nodeQueue[MAX_TREE_SIZE]; // 队列大小根据实际需要定义
    int front = 0, rear = 0;
    nodeQueue[rear++] = root;

    while (front < rear) {
        struct TreeNode* current = nodeQueue[front++];
        printf("%d ", current->val);
        if (current->left) nodeQueue[rear++] = current->left;
        if (current->right) nodeQueue[rear++] = current->right;
    }
}

在这个算法中，我们使用了一个静态数组作为队列来存储节点。这种实现方式简单，但是由于队列大小固定，因此只适用于较浅的树。对于深度较大的树，我们应该使用动态分配的队列，以避免溢出。

层次遍历除了基本的遍历外，还经常用于实现其他算法，如层序遍历构建二叉树、求二叉树的最大宽度等。层次遍历是计算机网络中Breadth-First Search (BFS)算法的基础。

6. 图结构及其相关算法

6.1 图的表示方法

图是数据结构中较为复杂的类型，它用于表示元素之间的多对多关系。图的表示有多种方法，但主要分为邻接矩阵和邻接表两种。

6.1.1 邻接矩阵与邻接表的构建与区别

邻接矩阵 使用一个二维数组来存储图中各个顶点之间的连接关系。邻接矩阵表示法的每个元素A[i][j]表示顶点i到顶点j之间是否存在边。如果存在，则A[i][j]为1或者边的权重；如果不存在，则为0。这种表示方法的优点在于能够快速判断任意两个顶点之间是否存在边以及边的权重，但其缺点是空间复杂度较高，特别是对于稀疏图来说，会浪费较多的空间。

// 一个简单的邻接矩阵的C++实现示例
#include <iostream>
#include <vector>
using namespace std;

const int MAX_VERTICES = 100;
int adjMatrix[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵

void initializeGraph(int vertices) {
    for (int i = 0; i < vertices; ++i) {
        for (int j = 0; j < vertices; ++j) {
            if (i == j)
                adjMatrix[i][j] = 0; // 顶点到自身的距离为0
            else
                adjMatrix[i][j] = INT_MAX; // 顶点之间无连接时使用最大值表示
        }
    }
}

void addEdge(int src, int dest, int weight) {
    adjMatrix[src][dest] = weight; // 添加有向边的权重
    adjMatrix[dest][src] = weight; // 如果是无向图，则需要添加这行
}

// ...其他函数定义...

与邻接矩阵相对应的是 邻接表 ，它使用链表来表示图中每个顶点的所有邻接顶点。一个顶点的所有邻接点用链表的节点表示，节点中包含邻接点的信息以及指向下一个邻接点的指针。邻接表的优点是节省空间，特别适合表示稀疏图；缺点是查找任意两个顶点之间的连接情况可能需要遍历链表，时间复杂度较高。

// 一个简单的邻接表的C++实现示例
#include <iostream>
#include <list>
using namespace std;

const int MAX_VERTICES = 100;
list<pair<int, int>> adjList[MAX_VERTICES]; // 邻接表

void addEdge(int src, int dest, int weight) {
    adjList[src].push_back(make_pair(dest, weight)); // 有向图的边添加
    // 如果是无向图，还需要添加以下代码
    // adjList[dest].push_back(make_pair(src, weight));
}

// ...其他函数定义...

6.1.2 图的深度优先搜索与广度优先搜索算法

深度优先搜索（DFS） 是一种用于遍历或搜索树或图的算法。这个算法会尽可能深地搜索图的分支。当节点v的所有边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这个过程一直进行到已发现从源节点可达的所有节点为止。

// 伪代码示例
DFS(v)
    if v 未被访问
        标记 v 为已访问
        对于 v 的每个未被访问的邻接节点 w
            DFS(w)

广度优先搜索（BFS） 从根节点开始，然后检查其所有邻近的节点，然后是未被访问的邻接节点的邻接节点。如此继续，直到所有节点都被访问为止。BFS 使用队列数据结构来处理按层次遍历的节点。

// 伪代码示例
BFS(v)
    标记 v 为已访问
    创建一个空队列 Q
    Q enqueue(v)
    while Q 不为空
        t = Q front()
        Q dequeue()
        对于 t 的每个未被访问的邻接节点 n
            标记 n 为已访问
            Q enqueue(n)

在实现图的搜索时，通常需要记录每个顶点的状态，如是否被访问过，这可以通过数组或字典来完成。此外，针对不同类型的图（有向图或无向图、加权图或非加权图），搜索的细节可能有所不同。

6.2 图的最短路径与最小生成树

图的算法中，研究最短路径和最小生成树的构建也是十分重要的。在这一小节中，我们将聚焦于这类问题及其解决方案。

6.2.1 迪杰斯特拉算法与弗洛伊德算法

迪杰斯特拉算法（Dijkstra） 用于在加权图中找到从单个源点到所有其他顶点的最短路径。该算法适用于没有负权重边的图。算法的基本思想是贪心策略，每次从未访问过的顶点中选择距离最小的顶点进行访问。

// 伪代码示例
Dijkstra(Graph, source)
    create vertex set Q

    for each vertex v in Graph
        dist[v] ← INFINITY
        prev[v] ← UNDEFINED
        add v to Q

    dist[source] ← 0

    while Q is not empty
        u ← vertex in Q with min dist[u]
        remove u from Q

        for each neighbor v of u
            alt ← dist[u] + length(u, v)
            if alt < dist[v]
                dist[v] ← alt
                prev[v] ← u

    return dist[], prev[]

弗洛伊德算法（Floyd-Warshall） 用于解决所有顶点对之间的最短路径问题，它能够处理包含负权重边的图，但不适用于包含负权重环的图。该算法逐步增加顶点的数量，通过动态规划计算出所有顶点对之间的最短路径。

// 伪代码示例
FloydWarshall(Graph)
    dist[][] ← 由 Graph 决定的初始距离矩阵
    n ← Graph 中的顶点数量

    for k from 1 to n
        for i from 1 to n
            for j from 1 to n
                dist[i][j] ← min(dist[i][j], dist[i][k] + dist[k][j])

    return dist[]

6.2.2 克鲁斯卡尔算法与普里姆算法

克鲁斯卡尔算法（Kruskal’s Algorithm） 用于在加权连通图中找到最小生成树。最小生成树是指在一个加权连通图中，包含图中所有顶点且边的权重之和最小的树。

// 伪代码示例
Kruskal(Graph, weight)
    mstSet = ∅
    tree = ∅
    Graph → sort by weight

    for each edge e in Graph
        if mstSet does not form a cycle with tree
            add e to tree
            add e's vertices to mstSet

    return tree

普里姆算法（Prim’s Algorithm） 同样用于求解加权连通图的最小生成树问题。与克鲁斯卡尔算法不同，普里姆算法从一个顶点开始，逐步添加边和顶点来构建最小生成树。

// 伪代码示例
Prim(Graph, startVertex)
    mstSet = {startVertex}
    while mstSet is not all vertices
        e = ∅
        minWeight = INFINITY
        for each vertex v in mstSet
            for each vertex u adjacent to v
                if weight of edge (v,u) < minWeight and u is not in mstSet
                    e = (v,u)
                    minWeight = weight of (v,u)
        add e to the tree
        add u to mstSet

    return tree

以上算法在图论中应用广泛，无论是网络设计、路径规划还是其他涉及图的场景，这些算法都是必备的工具。通过适当的优化，这些算法可以在不同的实际问题中有效地发挥其作用。

本文还有配套的精品资源，点击获取

简介：数据结构是计算机科学的基础，严蔚敏教授的教材以实例详细阐述了数据的有效存储、组织及操作。本书不仅包含了C和C++语言实现的数据结构，还详细介绍了线性结构、栈、树、图、排序和查找等关键概念，帮助读者深入理解并应用于实际编程。源代码的使用增强了学习者的实践能力，并对数据结构的内存管理与算法应用有了更加直观的认识。

本文还有配套的精品资源，点击获取