2. 搜索算法

①. 深度优先搜索 DFS

示例场景：在一个树结构中查找某个节点。

import React, { useState } from "react";

function dfs(tree, target) {
  const stack = [tree];
  while (stack.length > 0) {
    const node = stack.pop();
    if (node.name === target) {
      return true;
    }
    if (node.children) {
      for (let i = node.children.length - 1; i >= 0; i--) {
        stack.push(node.children[i]);
      }
    }
  }
  return false;
}

function TreeSearch() {
  const [target, setTarget] = useState("");
  const [result, setResult] = useState("");

  const search = () => {
    const found = dfs(folderTree[0], target);
    setResult(found ? "找到节点" : "未找到节点");
  };

  return (
    <div>
      <input
        type="text"
        placeholder="目标节点"
        value={target}
        onChange={(e) => setTarget(e.target.value)}
      />
      <button onClick={search}>搜索</button>
      <p>{result}</p>
    </div>
  );
}

function App() {
  return (
    <div>
      <h1>树搜索</h1>
      <TreeSearch />
    </div>
  );
}

export default App;

②. 广度优先搜索（BFS）

示例场景：在一个图结构中查找某个节点。

import React, { useState } from "react";

function bfs(graph, start, target) {
  const queue = [start];
  const visited = new Set([start]);

  while (queue.length > 0) {
    const node = queue.shift();
    if (node === target) {
      return true;
    }
    if (graph[node]) {
      for (const neighbor of graph[node]) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      }
    }
  }
  return false;
}

function GraphSearch() {
  const [startNode, setStartNode] = useState("");
  const [targetNode, setTargetNode] = useState("");
  const [result, setResult] = useState("");

  const graph = {
    A: ["B", "C"],
    B: ["A", "D", "E"],
    C: ["A", "F"],
    D: ["B"],
    E: ["B", "F"],
    F: ["C", "E"],
  };

  const search = () => {
    const found = bfs(graph, startNode, targetNode);
    setResult(found ? "找到节点" : "未找到节点");
  };

  return (
    <div>
      <input
        type="text"
        placeholder="起始节点"
        value={startNode}
        onChange={(e) => setStartNode(e.target.value)}
      />
      <input
        type="text"
        placeholder="目标节点"
        value={targetNode}
        onChange={(e) => setTargetNode(e.target.value)}
      />
      <button onClick={search}>搜索</button>
      <p>{result}</p>
    </div>
  );
}

function App() {
  return (
    <div>
      <h1>广度优先搜索</h1>
      <GraphSearch />
    </div>
  );
}

export default App;

③. 贪心算法

示例场景：活动选择问题，选择尽可能多的不重叠活动。

import React, { useState } from "react";

function selectActivities(activities) {
  activities.sort((a, b) => a.end - b.end);

  const selectedActivities = [activities[0]];
  let lastSelected = activities[0];

  for (let i = 1; i < activities.length; i++) {
    if (activities[i].start >= lastSelected.end) {
      selectedActivities.push(activities[i]);
      lastSelected = activities[i];
    }
  }

  return selectedActivities;
}

function ActivitySelector() {
  const [activities, setActivities] = useState([
    { start: 1, end: 3 },
    { start: 2, end: 5 },
    { start: 3, end: 9 },
    { start: 5, end: 8 },
    { start: 8, end: 10 },
  ]);
  const [selectedActivities, setSelectedActivities] = useState([]);

  const select = () => {
    const selected = selectActivities(activities);
    setSelectedActivities(selected);
  };

  return (
    <div>
      <h2>活动选择问题</h2>
      <button onClick={select}>选择活动</button>
      <h3>所有活动</h3>
      <ul>
        {activities.map((activity, index) => (
          <li key={index}>
            {`活动 ${index + 1}: 开始时间 ${activity.start}, 结束时间 ${
              activity.end
            }`}
          </li>
        ))}
      </ul>
      <h3>选中的活动</h3>
      <ul>
        {selectedActivities.map((activity, index) => (
          <li key={index}>
            {`活动 ${index + 1}: 开始时间 ${activity.start}, 结束时间 ${
              activity.end
            }`}
          </li>
        ))}
      </ul>
    </div>
  );
}

function App() {
  return (
    <div>
      <h1>贪心算法</h1>
      <ActivitySelector />
    </div>
  );
}

export default App;

④. 二分查找

示例场景：在一个已排序的数组中查找某个元素。

import React, { useState } from "react";

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

function BinarySearch() {
  const [array, setArray] = useState([1, 3, 5, 7, 9, 11, 13, 15, 17, 19]);
  const [target, setTarget] = useState("");
  const [result, setResult] = useState("");

  const search = () => {
    const index = binarySearch(array, parseInt(target, 10));
    setResult(index !== -1 ? `找到目标，索引为 ${index}` : "未找到目标");
  };

  return (
    <div>
      <input
        type="number"
        placeholder="目标值"
        value={target}
        onChange={(e) => setTarget(e.target.value)}
      />
      <button onClick={search}>搜索</button>
      <p>{result}</p>
    </div>
  );
}

function App() {
  return (
    <div>
      <h1>二分查找</h1>
      <BinarySearch />
    </div>
  );
}

export default App;

这些算法在实际应用中非常有用，特别是在处理复杂数据结构和优化性能时。