Das Template Method Pattern ist ein Design Pattern. Es kann verwendet werden, wenn eine Familie von Algorithmen sich nur in Details der Implementierung unterscheidet. Ein Beispiel dafür sind die Tiefen- und die Breitensuche. Diese unterscheiden sich nur in der Reihenfolge der Untersuchung von Knoten.

Die Gemeinsamkeiten der Algorithmen werden in einer Basisklasse codiert. Dabei werden abstrakte Methoden verwendet - diese repräsentieren die Unterschiede. Von der Basisklasse leitet man mehrere Subklassen ab, in denen die abstrakten Methoden jeweils verschieden implementiert werden.

Für das Beispiel der Tiefen- und Breitensuche implementiert die Basisklasse das Gerüst des Algorithmus:

  abstract class Search<N>
  {
    protected final LinkedList<N> agenda;
    private N startNode;
    //
    protected Search(N startNode)
    {
      agenda = new LinkedList<N>();
      //
      this.startNode = startNode;
    }
    //
    protected abstract boolean isGoal(N node);
    //
    protected abstract List<N> getSuccessors(N node);
    //
    protected abstract void addToAgenda(List<N> nodes);
    //
    public final N find()
    {
      agenda.addFirst(startNode);
      //
      while (!agenda.isEmpty())
      {
        N node = agenda.removeFirst();
        //
        if (isGoal(node)) return node;
        //
        addToAgenda(getSuccessors(node));
      }
      //
      return null;
    }
  }

Für die Tiefensuche werden neue Knoten an den Anfang der Agenda gestellt:

  abstract class DepthFirstSearch<N> extends Search<N>
  {
    protected DepthFirstSearch(N startNode)
    {
      super(startNode);
    }
    //
    protected final void addToAgenda(List<N> nodes)
    {
      for (N node : nodes)
      {
        agenda.addFirst(node);
      }
    }
  }

Und bei der Breitensuche werden neue Knoten an das Ende der Agenda angefügt:

  abstract class BreadthFirstSearch<N> extends Search<N>
  {
    protected BreadthFirstSearch(N startNode)
    {
      super(startNode);
    }
    //
    protected final void addToAgenda(List<N> nodes)
    {
      for (N node : nodes)
      {
        agenda.addLast(node);
      }
    }
  }

Wenn sich die Implementierungen in einer Familie von Algorithmen stark unterscheiden, kommt zumindest noch das Strategy Pattern in Frage.