Oppgave 1

Oppgave 2

  String url = "https://www.cs.hioa.no/~ulfu/appolonius/kap11/1/graf7.txt";
  Graf graf = new Graf(url);

  Deque<String> stakk = new ArrayDeque<>();

  graf.dybdeFørstPosttraversering("C", stakk::push);
  graf.dybdeFørstPosttraversering("B", stakk::push);
  graf.dybdeFørstPosttraversering("A", stakk::push);

  System.out.println(stakk);  // Utskrift: [A, B, C, E, D, F, H, G, I]

  stakk.clear();
  graf.nullstill();

  // Starter med F:
  graf.dybdeFørstPosttraversering("F", stakk::push);
  graf.dybdeFørstPosttraversering("A", stakk::push);
  graf.dybdeFørstPosttraversering("B", stakk::push);
  graf.dybdeFørstPosttraversering("C", stakk::push);

  System.out.println(stakk);  // Utskrift: [C, B, E, A, D, F, H, G, I]

Oppgave 3

Oppgave 4

Oppgave 5

Oppgave 6

  public String[] topologiskSortering()  // returnerer en topologisk sortert tabell
  {
    Deque<Node> stakk = new ArrayDeque<>();            // til å lagre noder
    String[] sortert = new String[antallNoder()];      // sortering
    byte[] antallInnkanter = new byte[antallNoder()];  // antall innkanter i nodene

    int i = 0;
    for (Node p : noder.values())           // alle nodene i grafen   
    {
      antallInnkanter[i++] = p.innkanter;   // tar vare på verdiene
      if (p.innkanter == 0) stakk.push(p);  // de som er uten innkanter
    }

    int j = 0;
    while (!stakk.isEmpty())
    {
      Node p = stakk.pop();    // en node uten innkanter
      sortert[j++] = p.navn;   // legger navnet i tabellen

      for (Node q : p.kanter)  // kant fra p til q
      {
        if (--q.innkanter == 0) stakk.push(q);
      }
    }

    int k = 0;
    for (Node p : noder.values())
    {
      p.innkanter = antallInnkanter[k++];  // legger verdiene tilbake
    }

    return sortert;
  }

Testprogram:

  String url = "https://www.cs.hioa.no/~ulfu/appolonius/kap11/1/graf7.txt";
  Graf graf = new Graf(url);

  String[] sortert = graf.topologiskSortering();
  System.out.println(Arrays.toString(sortert));
  // Utskrift: [C, B, E, A, D, F, H, G, I]

  for (String node : graf)
  {
    System.out.print("(" + node + "," + graf.antallInnkanter(node) + ") ");
  }
  // Utskrift: (A,0) (B,0) (C,0) (D,2) (E,2) (F,3) (G,2) (H,2) (I,3) 

Oppgave 7

La dette være siste setning:

  return j < antallNoder() ? null : sortert;

Oppgave 10

  public String[] topologiskSortering()
  {
    Deque<Integer> stakk = new ArrayDeque<>();  // lagring av noder
    String[] sortert = new String[antall];      // noder sortert

    byte[] antallInnkanter = new byte[antall];  // hjelpetabell

    for (int j = 0; j < antall; j++)     // horisontalt
    {
      for (int i = 0; i < antall; i++)   // vertikalt
      {
        if (graf[i][j]) antallInnkanter[j]++;
      }
    }

    for (int i = 0; i < antall; i++)  // finner de som er uten innkanter
    {
      if (antallInnkanter[i] == 0) stakk.push(i);
    }

    int k = 0;
    while (!stakk.isEmpty())
    {
      int i = stakk.pop();
      sortert[k++] = navn[i];

      for (int j = 0; j < antall; j++)  // går gjennom rad i
      {
        if (graf[i][j])     // kant fra i til j
        {
          if (--antallInnkanter[j] == 0) stakk.push(j);
        }
      }
    }

    return sortert;  // nodene topplogisk sortert
  }