Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen   (Übersicht)

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung
Nächste Überarbeitung		Vorherige Überarbeitung
Letzte ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:aud:loesungws15 [07.04.2019 13:28] – Nico Hambauerpruefungen:bachelor:aud:loesungws15 [24.07.2019 16:12] – dom
Zeile 185: Zeile 185:
 </code> </code>
 ==== Aufgabe 7 Graphen ==== ==== Aufgabe 7 Graphen ====
 +
 +**a)**
 <code java> <code java>
-public class GraphWS15 {+void sammle(boolean[][] am, int k, Set<Integer> verb, Set<Integer> bes) { 
 +  if (!bes.contains(k)) { 
 +    verb.add(k); 
 +    bes.add(k); 
 +    for (int i = 0; i < am[k].length; i++) { 
 +        if (am[k][i]) { 
 +            sammle(am, i, verb, bes); 
 +        } 
 +    }
  
- void sammle(boolean[][] am, int k, Set<Integer> verb, Set<Integer> bes) { +    for (int i = 0; i < am.length; i++) { 
- if (!bes.contains(k)) { +        if (am[i][k]) { 
- verb.add(k); +            sammle(am, i, verb, bes); 
- bes.add(k); +        } 
- for (int i = 0; i < am[k].length; i++) { +    } 
- if (am[k][i]){ +  } 
- sammle(am, i, verb, bes); +} 
- } +</code>
- }+
  
- for (int i = 0; i < am.length; i++) { +**b)**
- if (am[i][k]){ +
- sammle(am, i, verb, bes); +
- } +
- } +
- } +
- }+
  
- List<Set<Integer>> mszt(boolean[][] am) {+<code=java> 
 +List<Set<Integer>> mszt(boolean[][] am) {
  // Ergebnisliste:  // Ergebnisliste:
  List<Set<Integer>> ergebnis = new LinkedList<>();  List<Set<Integer>> ergebnis = new LinkedList<>();
 +
  // Menge besuchter Knoten:  // Menge besuchter Knoten:
  Set<Integer> bk = new HashSet<>();  Set<Integer> bk = new HashSet<>();
 +
  // Ermittle alle Teilgraphen mittels Hilfsmethode sammle:  // Ermittle alle Teilgraphen mittels Hilfsmethode sammle:
  for (int k = 0; k < am.length; k++) {  for (int k = 0; k < am.length; k++) {
- if (!bk.contains(k)){+ if (!bk.contains(k)) { 
  // falls k noch nicht besucht => sammle mit k verbundene Knoten  // falls k noch nicht besucht => sammle mit k verbundene Knoten
  Set<Integer> verb = new HashSet();  Set<Integer> verb = new HashSet();
- sammle(am,k,verb, bk);+ sammle(am, k, verb, bk);
  ergebnis.add(verb);  ergebnis.add(verb);
 +
                                 //einfacher waere hier statt den letzten drei zeilen folgendes:                                 //einfacher waere hier statt den letzten drei zeilen folgendes:
-                                //sammle(am,k,ergebnis.get(k), bk); //!!+                                //sammle(am, k, ergebnis.get(k), bk); 
  }  }
   
  }  }
- 
  return ergebnis;  return ergebnis;
  }  }
 +</code>
 +
 +**c)**
  
- void itg(boolean[][] am, Set<Integer> vs) { +<code=java> 
- for (int i=0;i<am.length;i++){ +void itg(boolean[][] am, Set<Integer> vs) { 
- for (int j=0;j<am[i].length;j++){ +    for (int i = 0; i < am.length; i++) { 
- if (am[i][j]){ +        for (int j = 0; j < am.length; j++) { 
- if (!(vs.contains(i) && vs.contains(j))){+            if (am[i][j]) { 
 +                if (!vs.contains(i) || !vs.contains(j)) {  // es muss sowohl x als auch y in vs enthalten sein 
 +                    am[i][j] = false; // der Graph ist gerichtet, daher reicht die Betrachtung an einer Stelle 
 + } 
 +     } 
 + }  
 +    } 
 +} 
 + 
 +// alte Loesung: 
 +void itg(boolean[][] am, Set<Integer> vs) { 
 + for (int i = 0; i < am.length; i++) { 
 + for (int j = 0; j < am.length; j++) { 
 + if (am[i][j]) { 
 + if (!(vs.contains(i) && vs.contains(j))) {
                                  am[i][j] = false;                                  am[i][j] = false;
                                                 am[j][i] = false;                                                 am[j][i] = false;
  }  }
  }  }
- } + }
- +
  }  }
- } +} 
-  +</code> 
- public static void main(String[] args){+ 
 +Code zum selber testen: 
 +<code=java>  
 +public static void main(String[] args){
                 //Beispielaufruf mit aus 3 Subgraphen bestehendem Graph                 //Beispielaufruf mit aus 3 Subgraphen bestehendem Graph
  GraphWS15 g = new GraphWS15();  GraphWS15 g = new GraphWS15();