Hab endlich eine Lösung gefunden. Absolut unelegant, aber das Programm läuft.:D
Danke nochmal für eure Hilfe!!
Beiträge von lilly1
-
-
Erstmal danke für eure Antworten
!!
Hatte bis jetzt keine Zeit mich mit dem Programm weiter zu beschäftigen.
Das mit der zweidimensionalen Liste klingt ganz gut. Ist damit die doppelt verkettete Liste gemeint.
Ich weiss aber nicht wie ich das machen soll.
Hier mein Programm bis jetzt:Code
Alles anzeigen[size=10][COLOR=#0000ff]#include[/COLOR][/SIZE][size=10][COLOR=#800000]<stdio.h>[/COLOR][/SIZE] [size=10][COLOR=#0000ff]#include[/COLOR][/SIZE][size=10][COLOR=#800000]<stdlib.h>[/COLOR][/SIZE] [size=10][COLOR=#0000ff]#include[/COLOR][/SIZE][size=10][COLOR=#800000]<conio.h>[/COLOR][/SIZE] [size=10][COLOR=#0000ff]float[/COLOR][/SIZE][size=10] **weight;[/SIZE] [size=10][COLOR=#0000ff]struct[/COLOR][/SIZE][size=10] result {[/SIZE] [size=10][COLOR=#0000ff]int[/COLOR][/SIZE][size=10] actmincut;[/SIZE] [size=10][COLOR=#0000ff]float[/COLOR][/SIZE][size=10] cut_weight;[/SIZE] [size=10]}[/SIZE] [size=10]main(){ [/SIZE] [size=10][COLOR=#0000ff]int[/COLOR][/SIZE][size=10] number_of_nodes, number_of_kanten;[/SIZE] [size=10][COLOR=#0000ff]int[/COLOR][/SIZE][size=10] u, l, i, j, h, node1, node2;[/SIZE] [size=10][COLOR=#0000ff]float[/COLOR][/SIZE][size=10] gew;[/SIZE] [size=10][COLOR=#0000ff]int[/COLOR][/SIZE][size=10] mincut;[/SIZE] [size=10][COLOR=#0000ff]float[/COLOR][/SIZE][size=10] mincut_weight;[/SIZE] [size=10][COLOR=#0000ff]struct[/COLOR][/SIZE][size=10] result ergebnis;[/SIZE] [size=10][COLOR=#0000ff]struct[/COLOR][/SIZE][size=10] result acmincut();[/SIZE] [size=10]FILE *daten;[/SIZE] [size=10]daten = fopen([/SIZE][size=10][COLOR=#800000]"Daten.txt"[/COLOR][/SIZE][size=10], [/SIZE][size=10][COLOR=#800000]"r"[/COLOR][/SIZE][size=10]);[/SIZE] [size=10][COLOR=#0000ff]if[/COLOR][/SIZE][size=10] (daten == NULL)[/SIZE] [size=10]fprintf(stderr, [/SIZE][size=10][COLOR=#800000]"Kann Datei nicht oeffnen\n"[/COLOR][/SIZE][size=10]);[/SIZE] [size=10][COLOR=#0000ff]else[/COLOR][/SIZE] [size=10]fscanf(daten, [/SIZE][size=10][COLOR=#800000]"%i %i"[/COLOR][/SIZE][size=10],&number_of_nodes, &number_of_kanten);[/SIZE] [size=10][COLOR=#008000]/*mincut = (int*)malloc(number_of_nodes*sizeof(int));*/[/COLOR][/SIZE] [size=10]weight = ([/SIZE][size=10][COLOR=#0000ff]float[/COLOR][/SIZE][size=10]**)malloc(number_of_nodes*[/SIZE][size=10][COLOR=#0000ff]sizeof[/COLOR][/SIZE][size=10]([/SIZE][size=10][COLOR=#0000ff]float[/COLOR][/SIZE][size=10]*));[/SIZE] [size=10][COLOR=#0000ff]for[/COLOR][/SIZE][size=10] (l = 0; l < number_of_nodes; l++){[/SIZE] [size=10]weight[l] = ([/SIZE][size=10][COLOR=#0000ff]float[/COLOR][/SIZE][size=10]*)malloc(number_of_nodes*[/SIZE][size=10][COLOR=#0000ff]sizeof[/COLOR][/SIZE][size=10]([/SIZE][size=10][COLOR=#0000ff]float[/COLOR][/SIZE][size=10]));[/SIZE] [size=10]}[/SIZE] [size=10][COLOR=#0000ff]for[/COLOR][/SIZE][size=10] (i = 0; i < number_of_nodes; i++){ [/SIZE][size=10][COLOR=#008000]/*setze Gewichtsmatrix auf null*/[/COLOR][/SIZE] [size=10][COLOR=#0000ff]for[/COLOR][/SIZE][size=10] (j = 0; j < number_of_nodes; j++){[/SIZE] [size=10]weight[i][j] = 0.0;[/SIZE] [size=10]}[/SIZE] [size=10]}[/SIZE] [size=10][COLOR=#0000ff]for[/COLOR][/SIZE][size=10] (h = 0; h < number_of_kanten; h++){ [/SIZE][size=10][COLOR=#008000]/*Gewicht einlesen*/[/COLOR][/SIZE] [size=10]fscanf(daten, [/SIZE][size=10][COLOR=#800000]"%d %d %f"[/COLOR][/SIZE][size=10], &node1, &node2, &gew);[/SIZE] [size=10]weight[node2][node1] = weight[node1][node2] = gew;[/SIZE] [size=10]}[/SIZE] [size=10][COLOR=#008000]/*for (u = 0; u < number_of_nodes; ++u){[/COLOR][/SIZE] [size=10][COLOR=#008000]for (h = 0; h < number_of_nodes; ++h){[/COLOR][/SIZE] [size=10][COLOR=#008000]printf("%f",weight[u][h]);[/COLOR][/SIZE] [size=10][COLOR=#008000]getch();[/COLOR][/SIZE] [size=10][COLOR=#008000]}[/COLOR][/SIZE] [size=10][COLOR=#008000]}*/[/COLOR][/SIZE] [size=10]ergebnis = acmincut (number_of_nodes);[/SIZE] [size=10]mincut_weight = ergebnis.cut_weight;[/SIZE] [size=10]mincut = ergebnis.actmincut;[/SIZE] [size=10][COLOR=#008000]/*printf ("erster: %f\n",mincut_weight);[/COLOR][/SIZE] [size=10][COLOR=#008000]getch();[/COLOR][/SIZE] [size=10][COLOR=#008000]ergebnis = acmincut (number_of_nodes - 1);[/COLOR][/SIZE] [size=10][COLOR=#008000]mincut_weight = ergebnis.cut_weight;[/COLOR][/SIZE] [size=10][COLOR=#008000]mincut = ergebnis.actmincut;[/COLOR][/SIZE] [size=10][COLOR=#008000]printf ("zweiter: %f\n",mincut_weight);[/COLOR][/SIZE] [size=10][COLOR=#008000]getch();[/COLOR][/SIZE] [size=10][COLOR=#008000]ergebnis = acmincut (number_of_nodes - 2);[/COLOR][/SIZE] [size=10][COLOR=#008000]mincut_weight = ergebnis.cut_weight;[/COLOR][/SIZE] [size=10][COLOR=#008000]mincut = ergebnis.actmincut;[/COLOR][/SIZE] [size=10][COLOR=#008000]printf ("dritter: %f\n",mincut_weight);[/COLOR][/SIZE] [size=10][COLOR=#008000]getch();*/[/COLOR][/SIZE] [size=10]number_of_nodes = number_of_nodes - 1;[/SIZE] [size=10][COLOR=#0000ff]while[/COLOR][/SIZE][size=10] (number_of_nodes > 1){[/SIZE] [size=10]ergebnis = acmincut (number_of_nodes);[/SIZE] [size=10][COLOR=#0000ff]if[/COLOR][/SIZE][size=10] (ergebnis.cut_weight < mincut_weight){ [/SIZE] [size=10]mincut_weight = ergebnis.cut_weight; [/SIZE] [size=10]mincut = ergebnis.actmincut;[/SIZE] [size=10]}[/SIZE] [size=10]printf([/SIZE][size=10][COLOR=#800000]"schn: %f\n"[/COLOR][/SIZE][size=10],mincut_weight);[/SIZE] [size=10]getch();[/SIZE] [size=10]number_of_nodes = number_of_nodes - 1; [/SIZE] [size=10]}[/SIZE] [size=10]printf([/SIZE][size=10][COLOR=#800000]"Schnitt: %d\n Gewicht: %f\n"[/COLOR][/SIZE][size=10], mincut, mincut_weight);[/SIZE] [size=10]getch();[/SIZE] [size=10]}[/SIZE] [size=10][COLOR=#0000ff]struct[/COLOR][/SIZE][size=10] result acmincut([/SIZE][size=10][COLOR=#0000ff]int[/COLOR][/SIZE][size=10] nodes){ [/SIZE] [size=10][COLOR=#0000ff]int[/COLOR][/SIZE][size=10] x, y, l, i, j, k, u, h;[/SIZE] [size=10][COLOR=#0000ff]int[/COLOR][/SIZE][size=10] v, counter;[/SIZE] [size=10][COLOR=#0000ff]int[/COLOR][/SIZE][size=10] *visited;[/SIZE] [size=10][COLOR=#0000ff]float[/COLOR][/SIZE][size=10] *V;[/SIZE] [size=10][COLOR=#0000ff]struct[/COLOR][/SIZE][size=10] result ergeb;[/SIZE] [size=10][COLOR=#008000]/*actmincut = (int*)malloc(nodes*sizeof(int));*/[/COLOR][/SIZE] [size=10]visited = ([/SIZE][size=10][COLOR=#0000ff]int[/COLOR][/SIZE][size=10]*)malloc(nodes*[/SIZE][size=10][COLOR=#0000ff]sizeof[/COLOR][/SIZE][size=10]([/SIZE][size=10][COLOR=#0000ff]int[/COLOR][/SIZE][size=10]));[/SIZE] [size=10]V = ([/SIZE][size=10][COLOR=#0000ff]float[/COLOR][/SIZE][size=10]*)malloc(nodes*[/SIZE][size=10][COLOR=#0000ff]sizeof[/COLOR][/SIZE][size=10]([/SIZE][size=10][COLOR=#0000ff]float[/COLOR][/SIZE][size=10]));[/SIZE] [size=10][COLOR=#0000ff]for[/COLOR][/SIZE][size=10] (v = 0; v < nodes; ++v){[/SIZE] [size=10]V[v] = 0.0;[/SIZE] [size=10]visited[v] = -1;[/SIZE] [size=10]}[/SIZE] [size=10]ergeb.cut_weight = 0.0;[/SIZE] [size=10]k = 0;[/SIZE] [size=10]counter = 0;[/SIZE] [size=10]visited[0] = 0;[/SIZE] [size=10][COLOR=#0000ff]while[/COLOR][/SIZE][size=10] (counter < (nodes-1) ) {[/SIZE] [size=10]ergeb.cut_weight = 0.0;[/SIZE] [size=10][COLOR=#0000ff]for[/COLOR][/SIZE][size=10] (i = 0; i < nodes; ++i) {[/SIZE] [size=10]V[i] = V[i] + weight[k][i];[/SIZE] [size=10]}[/SIZE] [size=10][COLOR=#0000ff]for[/COLOR][/SIZE][size=10] (j = 0; j <= counter; ++j) {[/SIZE] [size=10][COLOR=#0000ff]if[/COLOR][/SIZE][size=10] (visited[j] != -1) [/SIZE] [size=10]V[visited[j]] = 0.0; [/SIZE] [size=10]}[/SIZE] [size=10][COLOR=#0000ff]for[/COLOR][/SIZE][size=10] (l = 0; l < nodes; ++l) {[/SIZE] [size=10][COLOR=#0000ff]if[/COLOR][/SIZE][size=10] (V[l] > ergeb.cut_weight) {[/SIZE] [size=10]ergeb.cut_weight = V[l];[/SIZE] [size=10]k = l;[/SIZE] [size=10]}[/SIZE] [size=10]}[/SIZE] [size=10]visited[counter+1] = k; [/SIZE] [size=10]counter = counter + 1;[/SIZE] [size=10]}[/SIZE] [size=10]x = visited[nodes - 2]; [/SIZE] [size=10]y = visited[nodes - 1]; [/SIZE][size=10][COLOR=#008000]/* = k , letztes besuchtes Element*/[/COLOR][/SIZE] [size=10][COLOR=#0000ff]if[/COLOR][/SIZE][size=10] (x < y){[/SIZE] [size=10][COLOR=#0000ff]for[/COLOR][/SIZE][size=10] (i = 0; i < nodes; ++i){[/SIZE] [size=10]weight[x][i] = weight[x][i] + weight[y][i]; [/SIZE][size=10][COLOR=#008000]/* addiere in Gewichtsmatrix Zeile x und y und Spalte x und y*/[/COLOR][/SIZE] [size=10]weight[i][x] = weight[i][x] + weight[i][y];[/SIZE] [size=10]}[/SIZE] [size=10][COLOR=#0000ff]for[/COLOR][/SIZE][size=10] (i = 0; i < nodes; ++i){[/SIZE] [size=10]weight[y][i] = weight[nodes - 1][i]; [/SIZE][size=10][COLOR=#008000]/* überschreibe Spalte und Zeile y mit letzte Zeile*/[/COLOR][/SIZE] [size=10]weight[i][y] = weight[i][nodes - 1]; [/SIZE] [size=10]weight[x][x] = 0.0; [/SIZE][size=10][COLOR=#008000]/* Gewicht zwischen den Knoten x und y und falls Schleifen bei x oder y 0 setzen*/[/COLOR][/SIZE] [size=10]}[/SIZE] [size=10]}[/SIZE] [size=10][COLOR=#0000ff]if[/COLOR][/SIZE][size=10] (y < x){[/SIZE] [size=10][COLOR=#0000ff]for[/COLOR][/SIZE][size=10] (i = 0; i < nodes; ++i){[/SIZE] [size=10]weight[y][i] = weight[y][i] + weight[x][i]; [/SIZE][size=10][COLOR=#008000]/* addiere in Gewichtsmatrix Zeile x und y und Spalte x und y*/[/COLOR][/SIZE] [size=10]weight[i][y] = weight[i][y] + weight[i][x];[/SIZE] [size=10]}[/SIZE] [size=10][COLOR=#0000ff]for[/COLOR][/SIZE][size=10] (i = 0; i < nodes; ++i){[/SIZE] [size=10]weight[x][i] = weight[nodes - 1][i]; [/SIZE][size=10][COLOR=#008000]/* überschreibe Spalte und Zeile y mit letzte Zeile*/[/COLOR][/SIZE] [size=10]weight[i][x] = weight[i][nodes - 1]; [/SIZE] [size=10]weight[y][y] = 0.0; [/SIZE][size=10][COLOR=#008000]/* Gewicht zwischen den Knoten x und y und falls Schleifen bei x oder y 0 setzen*/[/COLOR][/SIZE] [size=10]}[/SIZE] [size=10]}[/SIZE] [size=10][COLOR=red]ergeb.actmincut = k;[/COLOR][/SIZE] [size=10][COLOR=#0000ff]return[/COLOR][/SIZE][size=10] (ergeb);[/SIZE] [size=10]}[/SIZE]
Das programm soll mir den minimalen Schnitt in einem Graphen berechnen.
Hab dazu einen link mit einer guten Erklärung gefunden:
http://www.informatik.uni-frankfurt.de/~erps/seminar/theoseminar.pdf
mein Programm arbeitet (ungefähr) nach dem Algorithmus MINIMUMCUT.
Ich erhalte den richtigen Wert für das Schnittgewicht. Mein Problem ist der Schnitt.
Im ersten Durchlauf stimmt er ja noch, weil nur ein Knoten übrig bleibt. Danach nicht mehr.
Bin dankbar für jede Hilfe.
Ich weiss, das Programm ist sehr dilletantisch, aber ich hab ja erst begonnen :o.
Danke!!!!!!!!!! -
Hallo Paulchen,
danke für deine schnelle Antwort.
Ich will die Zeichenkette nicht auf dem Bildschirm ausgeben, sondern an die main Fumktion übergeben.
Mein Vektor visited besteht aus n Zeichen. Ich durchlaufe eine Schleife. zu Beginn der Schleife sind die Werte für visited noch
visited[0] = 0;
visited[1] = 1;
.
.
.
visited[n] = n;
Beim nächsten Durchlauf erhalte ich für visited[h] = x; und für visited[k] = y;
Ich will jetzt den Vektor so verändern, dass auf visited[h] vor dem nächsten Schleifendurchlauf visited[h] = x,y steht.
Das ganze brauche ich unter anderem zur Berechnung eines minimalen Schnittes.
Nach n maligem Durchlauf der Schleife übergebe ich den Wert visited[h] an die main Funktion.
Hab auch schon alles bis auf diese "Zusammenlegung".
Daaanke! -
Hallo,
hab gerade begonnen C zu lernen und auch schon das erste Problem:Ich habe zwei Integers x und y
x = visited[number_of_nodes - 2];
y = visited[number_of_nodes - 1];
Bei visited[number_of_nodes - 2] kommt zum Beispiel 2 heraus und bei visited[number_of_nodes - 1] der Integer 5.
Als Ergebnis will ich die Verbindung 2, 5 haben.
Hab strncat() gefunden. Weiss aber nicht, wie ich das hier anwenden soll.
Ich hoffe ihr versteht meine Frage. Weiss nicht genau wie ich mein Problem beschreiben. Bin dankbar für jeden Hinweis.:)
lg
lilly