[C] implementare un grafo

[-Ivan-]

Scusate ma se io devo implementare un grafo in c che struttura dati posso usare?
Me lo chiedo da tempo e non riesco proprio a rispondermi, cioè se io ho n nodi ed ogni nodo è connesso tramite un arco ad ogni altro nodo il quale arco ha un suo peso io questo peso dove lo scrivo?
E poi se io ho 1 milione di nodi ognuno di questi deve avere 999 mila puntatori?
Com'è che vengono implementate solitamente queste strutture?

[Dun]

Matrice di adiacenza?

[-Ivan-]

Originariamente inviato da Dun

Matrice di adiacenza?

Matrice di adiacenza questa sconosciuta .
Grazie mille, non so cosa sono ma so che le ho sul libro di algoritmi, mi documenterò.

[Ziosilvio]

Dato un grafo G con insieme dei nodi V e insieme degli archi E, la matrice di adiacenza richiede sempre spazio O(|V|^2), dove |X| è il numero di elementi dell'insieme X; in compenso, la domanda se esista un arco da v a w ottiene sempre risposta in tempo O(1).

In alternativa, puoi usare le liste di adiacenza: ossia, ogni nodo v ha una lista di tutti i nodi w tali che (v,w) è un arco.
In questo modo, la rappresentazione richiede spazio O(|E|), che però a priori è ancora O(|V|^2); inoltre, la domanda se esista un arco da v a w richiede in genere tempo O(|V|).
Tuttavia, se ogni nodo ha al più k vicini con k<<|V|, allora all'atto pratico la rappresentazione del grafo con liste di adiacenza richiede spazio O(|V|), e alla domanda "esiste un arco da v a w?" si risponde in tempo O(1).