Fluery.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Fluery算法：求无向欧拉图中的一条欧拉回路\n",
    "1. 任取G中一顶点$v_0$, 令 $P_0 = v_0$;\n",
    "2. 假设沿着 $P-i = v_0 e_1 v_1 e_2 ... e_i v_i $ 走到顶点 $v_i$, 按照下面方法从$E(G) - \\{e_1, e_2, ... , e_i\\}$中选择 $e_{i+1}$\n",
    "    1. $e_{i+1}$ 与 $v_i$ 相关联\n",
    "    2. 除非无别的边可以选择，否则 $e_{i+1}$ 不能是$G_i = G - \\{e_1, e_2, ... , e_i \\}$中的桥\n",
    "3. 当2不能进行时算法停止"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a - d\n",
      "d - b\n",
      "b - e\n",
      "e - c\n",
      "c - f\n",
      "f - b\n",
      "b - g\n",
      "g - c\n",
      "c - h\n",
      "h - i\n",
      "i - j\n",
      "j - h\n",
      "h - f\n",
      "f - d\n",
      "d - g\n",
      "g - e\n",
      "e - a\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# 判断图是否连通\n",
    "def dfs(graph, v, visited):\n",
    "    visited[v] = True\n",
    "    for neighbor in graph[v]:\n",
    "        if not visited[neighbor]:\n",
    "            dfs(graph, neighbor, visited)\n",
    "\n",
    "\n",
    "# Fluery算法\n",
    "# 判断uv是否是一条有效边\n",
    "def is_valid_next_edge(graph, u, v):\n",
    "    # 删除到最后如果是一个空图则返回\n",
    "    if not any(graph.values()):\n",
    "        return False\n",
    "    # 无边可选，只能选这条边\n",
    "    if (len(graph[u]) == 1):\n",
    "        return True\n",
    "    # 若有边可以选，则这一条边不能是割边，所以来统计连通分支数量\n",
    "    visited = {node : False for node in graph}\n",
    "    dfs(graph, u, visited)\n",
    "    count1 = sum(visited.values())\n",
    "\n",
    "    # 删除边uv来计算连通分支数量\n",
    "    graph[u].remove(v)    \n",
    "    graph[v].remove(u)\n",
    "    visited = {node : False for node in graph}\n",
    "    dfs(graph, u, visited)\n",
    "    count2 = sum(visited.values())\n",
    "    # 恢复边uv\n",
    "    graph[u].append(v)\n",
    "    graph[v].append(u)\n",
    "    # 若两个连通分支数量一样，则证明这条边不是割边可以选择\n",
    "    return count1 == count2\n",
    "\n",
    "# 递归的打印欧拉回路\n",
    "def print_euler_util(graph, u):\n",
    "    for v in list(graph[u]):\n",
    "        if is_valid_next_edge(graph, u, v):\n",
    "            print(f\"{u} - {v}\", end='\\n')\n",
    "            # 删除边uv\n",
    "            graph[u].remove(v)\n",
    "            graph[v].remove(u)\n",
    "            # 递归遍历v\n",
    "            print_euler_util(graph, v) \n",
    "\n",
    "# 判断是否有欧拉回路\n",
    "def print_euler_circuit(graph):\n",
    "    # 寻找起点，必须是偶度点\n",
    "    u = next((node for node in graph if len(graph[node]) % 2 == 0), None)\n",
    "    if u is None:\n",
    "        raise ValueError(\"No Euler Circuit\")\n",
    "    print_euler_util(graph, u)\n",
    "    print()\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    graph = {\n",
    "        'a':['d', 'e'],\n",
    "        'b':['d', 'e', 'f', 'g'],\n",
    "        'c':['e', 'f', 'g', 'h'],\n",
    "        'd':['a', 'b', 'f', 'g'],\n",
    "        'e':['a', 'b', 'c', 'g'],\n",
    "        'f':['b', 'c', 'd', 'h'],\n",
    "        'g':['b', 'c', 'd', 'e'],\n",
    "        'h':['c', 'f', 'i', 'j'],\n",
    "        'i':['h', 'j'],\n",
    "        'j':['h', 'i']\n",
    "    }\n",
    "    print_euler_circuit(graph)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "base",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}