Search

(Depth-First Search) DFS and (Breadth-First Search) BFS

搜索问题，确保找到解：

frontier 集（边界），explored set 集（已探索集）

  • DFS stack: last-in first-out data type
  • BFS queue: first-in first-out data type

编程实现：

在 Python 中，class（类）是面向对象编程（OOP）的核心概念。你可以把“类”看作是创建对象的蓝图或模板，而“对象”（也叫实例）则是根据这个蓝图制造出来的具体实体。

1. 类的基本语法与实例化

定义一个类使用 class 关键字。类名通常采用大驼峰命名法（如 MyFirstClass）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
>class Dog:
   # __init__ 是类的构造函数（初始化方法），在创建对象时自动调用
   def __init__(self, name, age):
       self.name = name  # self.name 是实例属性
       self.age = age

   # 这是一个实例方法
   def bark(self):
       print(f"{self.name} 正在汪汪叫！它今年 {self.age} 岁了。")

># 实例化（创建对象）
>my_dog = Dog("旺财", 3)

># 调用对象的方法
>my_dog.bark()  # 输出: 旺财 正在汪汪叫！它今年 3 岁了。

2. 实例属性 vs 类属性

  • 实例属性： 绑定在特定的对象上（通过 self. 定义），每个对象都有自己独立的一份。
  • 类属性： 绑定在类本身上，所有该类的对象共享这一份数据。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
>class Employee:
   company_name = "Tech Corp"  # 类属性：所有员工共享

   def __init__(self, name):
       self.name = name        # 实例属性：每个员工独有

>emp1 = Employee("Alice")
>emp2 = Employee("Bob")

>print(emp1.company_name) # 输出: Tech Corp
>print(emp2.company_name) # 输出: Tech Corp

># 修改类属性，所有实例都会受到影响
>Employee.company_name = "Global Tech"
>print(emp1.company_name) # 输出: Global Tech

3. 方法的分类：实例方法、类方法、静态方法

除了普通的实例方法，Python 还提供了装饰器来定义其他类型的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
>class Calculator:
   count = 0  # 类属性：记录一共创建了多少个计算器
   
   def __init__(self):
       self.value = 0 # 实例属性：每个计算器独立的值，默认从0开始
       Calculator.count += 1 # 每次实例化时，让类属性 +1
       
   # 1. 实例方法：必须通过具体的对象来调用
   def add(self, num):
       self.value += num
       return self.value

   # 2. 类方法：通常通过类名直接调用，不需要创建对象
   @classmethod
   def get_count(cls):
       return f"当前共创建了 {cls.count} 个计算器"

   # 3. 静态方法：通常通过类名直接调用，当做一个普通的工具函数
   @staticmethod
   def multiply(a, b):
       return a * b

># ====== 下面是调用示例 ======

># 1. 测试静态方法 (不需要实例化，直接用类名调用)
>print("--- 静态方法 ---")
>print(f"3 乘 4 等于: {Calculator.multiply(3, 4)}") 
># 输出: 3 乘 4 等于: 12

># 2. 测试类方法 (查看当前创建了多少个计算器)
>print("\n--- 类方法 ---")
>print(Calculator.get_count()) 
># 输出: 当前共创建了 0 个计算器

># 3. 测试实例方法 (需要先创建具体的对象)
>print("\n--- 实例方法 ---")
>calc1 = Calculator()  # 创建第一个计算器对象，初始 value 为 0
>print(f"calc1 加 5 的结果: {calc1.add(5)}") 
># 输出: calc1 加 5 的结果: 5

>calc2 = Calculator()  # 创建第二个计算器对象
>print(f"calc2 加 100 的结果: {calc2.add(100)}") 
># 输出: calc2 加 100 的结果: 100
># (注意：calc1 和 calc2 的 value 是各自独立的实例属性)

># 再次测试类方法
>print("\n--- 再次查看类方法 ---")
>print(Calculator.get_count()) 
># 输出: 当前共创建了 2 个计算器

4. 类的继承 (Inheritance)

继承允许一个类（子类）继承另一个类（父类）的属性和方法，从而实现代码复用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
>class Animal:
   def __init__(self, name):
       self.name = name

   def speak(self):
       return "不知道怎么叫"

># Cat 继承了 Animal
>class Cat(Animal):
   def __init__(self, name, color):
       # 使用 super() 调用父类的初始化方法
       super().__init__(name)
       self.color = color

   # 重写 (Override) 父类的方法
   def speak(self):
       return "喵喵喵！"

>my_cat = Cat("小白", "白色")
>print(my_cat.name)   # 输出: 小白 (继承自父类)
>print(my_cat.speak()) # 输出: 喵喵喵！ (子类重写的方法)

5. 封装 (Encapsulation) 与私有属性

在 Python 中，没有像 Java 那样严格的 public / private 关键字。但有一个约定俗成的规则：如果在属性或方法名前加上双下划线 __，它就会变成“私有”的，外部无法直接访问。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
>class BankAccount:
   def __init__(self, owner, balance):
       self.owner = owner
       self.__balance = balance  # 私有属性

   def deposit(self, amount):
       if amount > 0:
           self.__balance += amount

   # 提供公共方法来访问私有属性
   def get_balance(self):
       return self.__balance

>account = BankAccount("Tom", 1000)
># print(account.__balance)  # 这行会报错：AttributeError
>print(account.get_balance()) # 输出: 1000

6. 魔法方法 (Magic Methods / Dunder Methods)

Python 类中有很多以双下划线开头和结尾的方法（如 __init__）。它们会在特定的语法下被自动调用。

  • __str__(self): 定义对象的字符串表示形式（给用户看），例如使用 print(obj) 时触发。
  • __len__(self): 定义对对象使用 len(obj) 时的行为。
  • __add__(self, other): 定义对对象使用 + 运算符时的行为。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
>class Book:
   def __init__(self, title, pages):
       self.title = title
       self.pages = pages

   def __str__(self):
       return f"《{self.title}》"

   def __len__(self):
       return self.pages

>my_book = Book("Python入门", 300)
>print(my_book)        # 输出: 《Python入门》 (触发 __str__)
>print(len(my_book))   # 输出: 300 (触发 __len__)