C++でプロセスを強制終了する方法：BFSを使った実装解説

n個のプロセスがあると仮定します。各プロセスには、PID（プロセスID）と呼ばれる一意の識別子が割り当てられており、さらにPPID（親プロセスID）も持っています。

各プロセスが持てる親プロセスは1つだけですが、子プロセスは1つでも複数でも構いません。これはまさに木構造と同じ形です。PPIDが0になるプロセスは1つだけであり、それはそのプロセスに親が存在しないことを意味します。また、すべてのPIDは一意な正の整数です。

問題の概要

ここでは、2つの整数リストを使ってプロセスの一覧を表現します。1つ目のリストには各プロセスのPIDが含まれ、2つ目のリストにはそれに対応するPPIDが含まれます。このとき、強制終了したいプロセスを表すPIDが与えられたら、最終的に終了されるすべてのプロセスのPIDリストを求める必要があります。ただし、あるプロセスが終了すると、その子プロセスもすべて連鎖的に終了されるものと仮定します。

例として、入力が pid = [1, 3, 10, 5]、ppid = [3, 0, 5, 3]、kill = 5 の場合を考えてみましょう。このとき出力は [5, 10] となります。

これは、プロセス5を終了すると、その子プロセスである10も一緒に終了されるためです。

解決のためのアプローチ

この問題は、親から子への関係をマップで管理し、幅優先探索（BFS）で終了対象を収集することで効率的に解けます。具体的な手順は以下の通りです。

• 親プロセスIDをキー、子プロセスIDのリストを値とするマップ「child」を定義します。
• n := pid のサイズとします。
• 結果を格納する配列 ret を定義します。
• i := 0 から開始し、i < n の間、i を1ずつ増やしながら以下を繰り返します。
  • u := ppid[i]
  • v := pid[i]
  • child[u] の末尾に v を追加します。
• キュー q を定義し、kill を挿入します。
• q が空でない間、以下を繰り返します。
  • curr := q の先頭要素
  • q から先頭要素を取り出します。
  • ret の末尾に curr を追加します。
  • i := 0 から開始し、i < child[curr] のサイズの間、i を1ずつ増やしながら child[curr][i] を q に挿入します。
• ret を返します。

C++での実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
      map<int, vector<int> > child;
      int n = pid.size();
      vector<int> ret;
      for (int i = 0; i < n; i++) {
         int u = ppid[i];
         int v = pid[i];
         child[u].push_back(v);
      }
      queue<int> q;
      q.push(kill);
      while (!q.empty()) {
         int curr = q.front();
         q.pop();
         ret.push_back(curr);
         for (int i = 0; i < child[curr].size(); i++) {
            q.push(child[curr][i]);
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,3,10,5}, v1 = {3,0,5,3};
   print_vector(ob.killProcess(v, v1, 5));
}

入力

{1,3,10,5},{3,0,5,3},5

出力

[5, 10]

計算量について

まず、すべてのプロセスを走査して親子関係のマップを構築する処理にO(n)の時間がかかります。その後のBFSでは、各プロセスは最大1回ずつキューに追加・取り出しされるため、こちらもO(n)です。したがって、全体の時間計算量はO(n)、マップやキューの分だけ余分なメモリが必要なため、空間計算量もO(n)となります。

このように、BFSを活用すれば、プロセスツリー上で特定のプロセスとその子孫をすべて効率よく特定できます。実際のOSにおけるプロセス管理でも、同様の考え方が応用されています。