Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- pruefungen:bachelor:aud:loesungss17 [22.10.2017 13:10] – Aufgabe 4, 5 hinzugefügt jonpost
+++ pruefungen:bachelor:aud:loesungss17 [22.10.2017 18:26] – jonpost
@@ Zeile 216: / Zeile 216: @@
 as2afh(si, Add(ns, as), af) = Add(si, as2afh(si+length(ns), as, af))
+====Aufgabe 6 Graphen====
+**a)**
+<code java>
+boolean isSafe(boolean g[][], int cs[], int v, int c) {
+    for(int n = 0; n < g.length; n++) {
+        if(g[v][n] && c == cs[n]) {
+            return false;
+        }
+    }
+    return true;
+}
+</code>
+**b)**
+<code java>
+boolean helper(boolean g[][], int cs[], int m, int v) {
+    //base case
+    if(v >= g.length) {
+        return true;
+    }
+    //try different colors for vertex v
+    for(int c = 1; c <= m; c++) {
+        if(isSafe(g, cs, v, c)) {
+            //try and recurse
+            cs[v] = c;
+            if(helper(g, cs, m, v+1)) {
+                return true;
+            }
+            //backtrack
+            cs[v] = 0;
+        }
+    }
+    //finally give up
+    return false;
+}
+</code>
+**c)**
+<code java>
+int[] color(boolean g[][], int m) {
+    int[] cs = new int[g.length];
+    if(!helper(g, cs, m, 0)) {
+        return null;
+    }
+    return cs;
+}
+</code>