Finden einer berühmten Person auf einer Veranstaltung (Celebrity problem)

Published: 05.06.2020 | 539 Words | 3 minutes
Tags: [ datenstrukturen algorithmen stack ]

Zu einer Feier sind eine feste Anzahl n Personen eingeladen. Eine dieser Personen ist ein Prominenter. Der Prominente hat die Eigenschaft, dass ihn jede anwesende Person kennt. Er selbst kennt aber keine der anwesenden Personen. Es gibt also 1nen Prominenten und n-1 "normale" Personen. Die Aufgabe ist es nun den Prominenten möglichst schnell (O(n)) zu finden.

Als erstes benötigen wir eine ordentliche Repräsentation der "kennt"-Beziehung zweier Personen. Diese kann man z.B. mit einer zweidimensionalen Matrix darstellen. Jeder Person wird ein Index i $$ 1 \leq i \leq n $$ zugewiesen. Wir sagen die Person p1 "kennt" die Person p2 genau dann wenn in der Zeile von p1 und in der Spalte von p2 der Wert 1 steht. 1 ist frei gewählt genauso könnte man auch "kennt" oder "true" in die Matrix schreiben, dies ist einfach mehr Schreibaufwand ;).

Die Matrix hat dann Folgende Form:

$$ \begin{bmatrix} x_{11} & x_{12} & x_{13} & \dots & x_{1n} \\ x_{21} & x_{22} & x_{23} & \dots & x_{2n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ x_{d1} & x_{d2} & x_{d3} & \dots & x_{dn} \\ \end{bmatrix} $$

Ein Beispiel dazu:

Wir nehmen an es sind 4 Personen (p1, p2, p3, p4) zur Veranstaltung eingeladen:

Die entsprechende Matrix sieht dann folgendermaßen aus:

$$ \begin{bmatrix} 1_{11} & 1_{12} & 1_{13} & 0_{14} \\ 0_{21} & 1_{22} & 0_{23} & 0_{24} \\ 1_{31} & 1_{32} & 0_{33} & 0_{34} \\ 0_{41} & 1_{42} & 0_{43} & 0_{44} \\ \end{bmatrix} $$

Wie können wir nun möglichst effizient den Prominenten in der Matrix ausfindig machen?

Eine mögliche Lösung verwendet die Datenstruktur Stack. Dabei wird einmal ein Stack von 0 bis n erzeugt, also der Index jeder Person wird auf den Stack gelegt. Nun wird immer geprüft ob die oberste Person (a) die Person untendrunter (b) kennt.

  • Kennt Person a Person b nicht kann Person b nicht der Prominente sein, da sonst die Eigenschaften des Prominenten verletzte werden (Jeder kennt den Prominenten).
  • Wenn Person a Person b kennt kann Person a nicht der Prominente sein, da sonst ebenfalls die Eigenschaften des Prominenten verletzte werden (Der Prominente kennt niemanden).

Als Java-code sieht das ganze dann folgendermaßen aus:

public static int findeProminenten(boolean[][] arr) {
  int n = arr.length;
  Stack<Integer> stack = new Stack<Integer>();

  for(int i = 0; i < n; i++) {
    stack.push(i);
  }

  while(stack.size() >1) {
    // Die beiden oberen Elemente vom Stack nehmen
    int a = stack.pop();
    int b = stack.pop();

    // Wenn Person a Person b kennt
    if(arr[a][b]) {
      // Der Prominente kennt niemanden deshalb
      // kann a nicht der Prominente sein.
      stack.push(b);
    } else {
      stack.push(a);
    }
  }

  // letztes Element vom Stack ist die einzige Möglichkeit
  // für einen Prominenten, vorausgesetzt es gibt maximal einen

  int c = stack.pop();

  // Kontrolle
  for(int i = 0; i < arr.length; i++) {
    if( i != c && (    // c darf sich selbst kennen
        !arr[i][c] ||  // Wenn Person i person c nicht kennt ist es nicht der Prominente
        arr[c][i] )    // Wenn der Person c person i kennt ist es auch nicht der Prominente
    ){
       return -1;
     }
  }

  return c;
}
That's all ;)
Back to the top