[C++]come iniziare con i grafi

[Mira91]

Ciao a tutti! Come da titolo vorrei dei suggerimenti su come iniziare a costruire programmi che utilizzano i grafi. Primo ostacolo, come meglio rappresentarli. Non voglio codice, ma solo idee, perché ho già cercato sulla rete e vorrei partire dalle basi. Ho rappresentato qualche albero, ma nulla di sensazionale, ma faccio terza superiore... Pensavo di usare qualche struct come inizio. Se avete libri sulle strutture di dati o link sono ben accetti. Ah il linguaggio è c++. Grazie a tutti coloro che risponderanno.

[mondobimbi]

ma hai uno scopo in testa ?
Per cosa pensi di usare i grafi ?
Perchè se, per ora, è solo curiosità basta che su un motore di ricerca scrivi "grafi c++"

ciao
sergio

[Mira91]

ciao, scusa secondo te non l'ho già fatto? comunque mi interessa anche perché il mio prof di info vuole farmi fare le olimpiadi di informatica l'anno prossimo, e ho dato un occhiata ai problemi delle vecchie edizioni e ci sono grafi ecc.. E poi non mi dispiacerebbe una facoltà di info fra due anni. (poi sono una persona a cui piace portarsi avanti con le cose che mi piacciono...)

[mondobimbi]

in effetti immaginavo che lo avessi già fatto ma non capisco cosa puoi ottenere di più dal forum.
Penso che ti possiamo essere di più aiuto su un progetto specifico.

ciao

[Mira91]

io ho implementatoun albero con una struttura, magari qualche suggerimento da che parte iniziare a rappresentarlo. Leggevo anche di rappresentarlo come matrice di adiacenza. Qual è la soluzione migliore (se esiste). Oppure se avete qualche titolo di libro (magari dal prezzo non troppo elevato ihih). Il fatto è che ho cercato tutto il possibile su internet, volevo solo uno spunto per capire da dove partire.. Almeno come rappresentazione di un grafo.

[Mira91]

allora ho preso un problema da fare, per ora non mi interessa la parte di algoritmica. Devo leggere da un file .txt dei valori scritti in questo modo:

1 2 -2
3 -2
3 -2
4 5 -2
...
...
-1

La prima riga rappresenta il nodo 0, che è collegato ai nodi 1 e 2 (-2 è un terminatore), la seconda il nodo 1, che è collegato solo al nodo 3, ecc... l'ultima riga rappresenta l'ultimo nodo che non è collegato a nessun altro (per questo c'è -1).

Questo è il mio codice


#include "stdafx.h"
#include <iostream>

using namespace std;

#define MAX_PUNTI 50
#define MAX_FRECCE 100

struct nodo
{
int dato;
nodo* v[MAX_FRECCE];

}NODO;

typedef struct nodo* vertice;

vertice NewVertex(int dato)
{
vertice Vertex;
Vertex = (nodo*)malloc(sizeof(NODO));
Vertex->dato = dato;
return (Vertex);
}
void AddVertex(vertice Origine,vertice Nuovo)
{
int i;
for (i=0;i<=MAX_FRECCE;i++)
{
if (Origine->v[i]==NULL)
{
Origine->v[i] = Nuovo;
break;
}
}
}
vertice TotNodi[MAX_PUNTI];

int main(array<System::String ^> ^args)
{
FILE *f;
int n,i;
f = fopen("...percorso\\INPUT.TXT","r");
i = 0;
while(!feof(f))
{
TotNodi[i] = NewVertex(i);
fscanf(f,"%d",&n);
if(n != -2 && n!=-1 )
AddVertex (TotNodi[i],NewVertex(n));
else
i++;
}
fclose(f);
system("PAUSE");


Al momento di aggiungere un vertice non aggiunge nulla, e con il debug ho visto che la condizione
if (Origine->v[i]==NULL)
è sempre falsa.

(so che in quel punto lì è meglio un while, o simili ma ho scombinato un pò per vedere dov'era il problema)

[Mira91]

ho cambiato la NewVertex in:
vertice NewVertex(int dato)
{
vertice Vertex;
Vertex = (nodo*)malloc(sizeof(NODO));
Vertex->dato = dato;
for (int i=0;i<=MAX_FRECCE;i++)
Vertex->v[i]=NULL;
return (Vertex);
}
così in questo modo inizializzo tutti i possibili nodi null. Quella condizione adesso è sempre vera, ma mi perde i valori che aggiungo.

[Mira91]

ok ho risolto. sbagliavo nel leggere. ecco il codice relativo alla lettura

while(!feof(f))
{
TotNodi[i] = NewVertex(i);
fscanf(f,"%d",&n);
while(n != -2 && n!=-1 )
{
AddVertex (TotNodi[i],NewVertex(n));
fscanf(f,"%d",&n);
}
i++;
}

solo che comunque avendo un file con nove nodi ad esempio, non alloco nove nodi, ma + di nove perché tratto i singoli nodi come se fossero staccati.

[mondobimbi]

ciao mira,

ti darei volentieri una mano ma ci sono alcuni problemi

1 - dovresti postare del codice compilabile, il più completo possibile

2 - questo codice dovresti racchiuderlo tra i tag code o php , in maniera che venga conservata l'indentazione

3 - dovresti utilizzare c++ il più standard possibile e non specifico di una piattaforma in modo che lo si possa compilare, io er esempio utilizzo g++. Mia lacuna ma non so cosa sia int main(array<System::String ^> ^args).

ciao
sergio

[menphisx]

Originariamente inviato da mondobimbi
possa compilare, io er esempio utilizzo g++. Mia lacuna ma non so cosa sia int main(array<System::String ^> ^args).

ciao
sergio

Sembra una storpiatura del metodo main di Java :berto: