DFS（深さ優先探索）の行きがけ順と帰りがけ順の順序を示すコードをc++からPythonにうまく翻訳できません

Question

前提・実現したいこと

この記事で紹介されている，グラフをDFSで走査し，行きがけ順と帰りがけ順の順序を出力するc++のコードをPythonに翻訳しようとしています．

理想

記事では，次のようなコードで，

#include <iostream>
#include <vector>
using namespace std;
using Graph = vector<vector<int>>;

vector<bool> seen;
vector<int> first_order; // 行きがけ順
vector<int> last_order; // 帰りがけ順

void dfs(const Graph &G, int v, int& first_ptr, int& last_ptr) {
    // 行きがけ順をインクリメントしながらメモ
    first_order[v] = first_ptr++;

    seen[v] = true; 
    for (auto next_v : G[v]) { 
        if (seen[next_v]) continue;
        dfs(G, next_v, first_ptr, last_ptr);
    }

    // 帰りがけ順をインクリメントしながらメモ
    last_order[v] = last_ptr++;
}

int main() {
    // 頂点数と辺数
    int N, M; cin >> N >> M;

    // グラフ入力受取 (ここでは無向グラフを想定)
    Graph G(N);
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    // 頂点 0 をスタートとした探索
    seen.assign(N, false); // 全頂点を「未訪問」に初期化
    first_order.resize(N);
    last_order.resize(N);
    int first_ptr = 0, last_ptr = 0;
    dfs(G, 0, first_ptr, last_ptr);

    // 各頂点 v の行きがけ順、帰りがけ順を出力
    for (int v = 0; v < N; ++v)
        cout << v << ": " << first_order[v] << ", " << last_order[v] << endl;
}

次のような出力が返るようになっています．

0: 0, 14
1: 1, 2
2: 2, 0
3: 3, 1
4: 4, 9
5: 5, 5
6: 6, 3
7: 7, 4
8: 8, 8
9: 9, 6
10: 10, 7
11: 11, 13
12: 12, 10
13: 13, 12
14: 14, 11

これをそのままPythonに翻訳することが理想です．

発生している問題

翻訳するつもりで，次のように書きました．

N, M = map(int, input().split())  # 頂点数，辺数
G = [[] for _ in range(N)]

for i in range(M):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)

seen = [False]*N
first_order = [0]*N
last_order = [0]*N
first_ptr = 0
last_ptr = 0


def dfs(G, v, first_ptr, last_ptr):

    first_ptr += 1
    first_order[v] = first_ptr

    seen[v] = True

    for next_v in G[v]:
        if seen[next_v]:
            continue
        dfs(G, next_v, first_ptr, last_ptr)

    last_ptr += 1
    last_order[v] = last_ptr


dfs(G, 0, first_ptr, last_ptr)

for v in range(N):
    print('{}: {}, {}'.format(v, first_order[v], last_order[v]))

しかしその結果返ってくる出力は次のもので，想定と異なっています．

0: 1, 1
1: 2, 1
2: 3, 1
3: 3, 1
4: 2, 1
5: 3, 1
6: 4, 1
7: 4, 1
8: 3, 1
9: 4, 1
10: 4, 1
11: 2, 1
12: 3, 1
13: 3, 1
14: 4, 1

どのように変更すれば想定通りの出力が得られるのでしょうか？

インクリメントがうまくいっていないことは明らかなのですが，なぜそうなのかの見当がつきませんでした．初歩的な質問で恐縮ですが，ご検討いただけると大変助かります．

Answer 1

おそらくここですね

Python
def dfs(G, v, first_ptr, last_ptr):

C++
void dfs(const Graph &G, int v, int& first_ptr, int& last_ptr) { // A
void dfs(const Graph &G, int v, int first_ptr, int last_ptr) {   // B

Aがオリジナル、BがPythonのコードの解釈になります。
どう違うのかはC++の本を読み直して下さい。

Pythonでは、C++のint &という書式はありません
代わりとしてはこんな感じでしょうか

outlist = [0, 0]

def dfs(G, v, outlist):
   //first_ptr += 1
   outlist[0] += 1

Comments

[trader65]

ご回答ありがとうございます．参照渡しであるべきところが値渡しになってしまっていたのですね．大変勉強になりました！

Answer 2

動かすだけであれば、以下のように書き換えてfirst_ptr, last_ptrをポインタ経由でアクセスしているっぽくするのが簡単かと思います。
なお、元のC++プログラムでは後置インクリメントなので代入した後に値をインクリメントしています。
pythonプログラムもそれに合わせて代入とインクリメントの順番を変える必要があります。

N, M = map(int, input().split())  # 頂点数，辺数
G = [[] for _ in range(N)]

for i in range(M):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)

seen = [False]*N
first_order = [0]*N
last_order = [0]*N
first_ptr = [0]
last_ptr = [0]


def dfs(G, v, first_ptr, last_ptr):
    first_order[v] = first_ptr[0]
    first_ptr[0] += 1
    seen[v] = True

    for next_v in G[v]:
        if seen[next_v]:
            continue
        dfs(G, next_v, first_ptr, last_ptr)

    last_order[v] = last_ptr[0]
    last_ptr[0] += 1


dfs(G, 0, first_ptr, last_ptr)

for v in range(N):
    print('{}: {}, {}'.format(v, first_order[v], last_order[v]))

Comments

[trader65]

ご丁寧にありがとうございます！　インクリの前置/後置の違いを恥ずかしながら意識したことがなく，大変勉強になりました！