fork download
copy 
  1. #include <stdio.h>
  2.  
  3. #define NUM_NODES 8
  4. #define TOTAL_EDGES 9
  5.  
  6. // グラフの隣接行列（元データ）
  7. // graph[u][v] は、頂点uから頂点vへの有向辺の数を示します
  8. int base_graph[NUM_NODES][NUM_NODES] = {
  9.     // 0  1  2  3  4  5  6  7  (移動先の頂点)
  10.     { 0, 1, 1, 0, 0, 0, 0, 0 }, // 頂点0から 1, 2 へ
  11.     { 0, 0, 0, 1, 0, 0, 0, 0 }, // 頂点1から 3 へ
  12.     { 0, 0, 0, 0, 1, 0, 0, 0 }, // 頂点2から 4 へ
  13.     { 0, 0, 0, 0, 0, 1, 0, 0 }, // 頂点3から 5 へ
  14.     { 0, 0, 0, 0, 0, 0, 1, 0 }, // 頂点4から 6 へ
  15.     { 0, 0, 0, 0, 0, 0, 0, 1 }, // 頂点5から 7 へ
  16.     { 1, 0, 0, 0, 0, 0, 0, 0 }, // 頂点6から 0 へ
  17.     { 0, 0, 1, 0, 0, 0, 0, 0 }  // 頂点7から 2 へ（巡回を生み出すための辺）
  18. };
  19.  
  20. int current_graph[NUM_NODES][NUM_NODES];
  21. int path[TOTAL_EDGES + 1]; // 通った頂点の履歴を保存する配列
  22. int route_count = 0;
  23.  
  24. // 深さ優先探索（DFS）による一筆書き探索関数
  25. void find_eulerian_paths(int current_node, int edge_count) {
  26.     // すべての辺（9本）を通りきったら一筆書き成功
  27.     if (edge_count == TOTAL_EDGES) {
  28.         route_count++;
  29.         printf("ルート %d: ", route_count);
  30.         for (int i = 0; i <= TOTAL_EDGES; i++) {
  31.             printf("%d", path[i]);
  32.             if (i < TOTAL_EDGES) printf(" -> ");
  33.         }
  34.         printf("\n");
  35.         return;
  36.     }
  37.  
  38.     // 次の移動先となる頂点を探索
  39.     for (int next_node = 0; next_node < NUM_NODES; next_node++) {
  40.         // 現在の頂点から次の頂点へ移動できる辺が残っているか
  41.         if (current_graph[current_node][next_node] > 0) {
  42.  
  43.             // 辺を消費（通過フラグ）
  44.             current_graph[current_node][next_node]--;
  45.             path[edge_count + 1] = next_node;
  46.  
  47.             // 再帰的に次のステップを探索
  48.             find_eulerian_paths(next_node, edge_count + 1);
  49.  
  50.             // 状態を元に戻す（バックトラッキング）
  51.             current_graph[current_node][next_node]++;
  52.         }
  53.     }
  54. }
  55.  
  56. int main(void) {
  57.     printf("グラフのサイズ: 頂点数 %d, 辺の総数 %d\n", NUM_NODES, TOTAL_EDGES);
  58.     printf("--- 一筆書きルートの探索開始 ---\n\n");
  59.  
  60.     // すべての頂点（0〜7）を始点として試す
  61.     for (int start_node = 0; start_node < NUM_NODES; start_node++) {
  62.  
  63.         // ワーク用のグラフ配列に初期データをコピー
  64.         for (int i = 0; i < NUM_NODES; i++) {
  65.             for (int j = 0; j < NUM_NODES; j++) {
  66.                 current_graph[i][j] = base_graph[i][j];
  67.             }
  68.         }
  69.  
  70.         // 始点をセットして探索開始
  71.         path[0] = start_node;
  72.         find_eulerian_paths(start_node, 0);
  73.     }
  74.  
  75.     printf("\n発見された一筆書きルートの総数: %d\n", route_count);
  76.  
  77.     return 0;
  78. }
  79.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
グラフのサイズ: 頂点数 8, 辺の総数 9
--- 一筆書きルートの探索開始 ---

ルート 1: 0 -> 1 -> 3 -> 5 -> 7 -> 2 -> 4 -> 6 -> 0 -> 2
ルート 2: 0 -> 2 -> 4 -> 6 -> 0 -> 1 -> 3 -> 5 -> 7 -> 2

発見された一筆書きルートの総数: 2
https://ideone.com/7AkfWp
language:
C (gcc 8.3)
created:
19 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!