algoritmo grafico che rileva se il grafico è connesso, bipartito, ha un ciclo ed è un albero

Question

Sono arrivato a un problema quando stavo cercando di lavorare con i grafici e scrivere un codice per questo ma senza fortuna:/!!

volevo qualcosa di creato che avrà i dati del grafico e verificare se si tratta di: 1- collegato 2- 3- bipartito ha ciclo 4- è un albero

quindi mi chiedevo per esempio se questo può essere scritto per leggere i dati di un grafico da un file .txt che farà i test di cui sopra ??

utilizzando il semplice formato della lista bordo è l'approccio corretto per questo?

il vostro aiuto è apprezzato se potete darmi un collegamento per leggere su come eseguire questa attività o un calcio d'inizio per un codice !!

grazie: D

Answer 1

controllo se è:

1. contatto

Per questo, si tenta di attraversare l'intero grafico da un punto, e vedere se ci riesci. Qui sia l'attraversamento in profondità che l'attraversamento in ampiezza sono accettabili. Questo algoritmo dividere il nodo in componenti:

• marchio tutti i nodi come unvisited
• per ogni nodo c, se questo nodo è unvisited
  • creare un nuovo insieme vuoto di nodi, il componente corrente
  • Enqueue il nodo di attraversamento
  • mentre non v'è alcun nodo t accodato
    • eliminare questa cenno e dalla coda
    • marchio ogni prossimo non visitato il più aperto e accodare per l'attraversamento
    • segno questo nodo come attraversato
    • aggiungere questo nodo al componente corrente
  • chiudere il componente corrente, e aggiungerlo all'insieme di componenti

Se c'è un solo componente, il grafico è collegato.

Se si utilizza una coda, l'algoritmo è una ricerca in ampiezza. Se viene utilizzata una pila, l'algoritmo è una ricerca in profondità. Qualsiasi altra raccolta con push e pop-qualsiasi operazione farà. Di particolare interesse è il call stack:

Per grafici tracciati, ci sono due concetti correlati: Un grafo orientato è debolmente connesso se è connesso trascurando tutte le direzioni di bordo. Un grafo orientato è fortemente connesso se ogni nodo è raggiungibile da ogni nodo.Per verificare la presenza di una connessione forte, è sufficiente verificare che ogni nodo sia raggiungibile dal primo nodo utilizzando solo i fronti avanzati e che ogni nodo sia raggiungibile dal primo nodo utilizzando solo i fronti all'indietro (il primo nodo è raggiungibile da ogni nodo).

1. bipartito

Un grafo è bipartito sse è bicolorable. Prova ad assegnare un bicolore e, se fallisci, il grafico non è bipartito. Questo può essere incorporato nell'algoritmo precedente: Ogni volta che contrassegni un nodo come aperto, assegna un colore ad esso, opposto al colore assegnato al suo vicino t. Quando un vicino di casa t è già aperto, controlla il suo colore. Se il suo colore è uguale a quello di t, non c'è il bicolore.

1. ha ciclo

Questo non è facile: Se si osserva qualsiasi nodo che è già aperto, c'è un ciclo. Nota che ogni grafico che non ha ciclo è bipartito.

Nei grafici diretti, questo rileva la presenza di un ciclo non orientato. Per rilevare la presenza di cicli diretti, utilizzare la seguente (topologica sort) algoritmo:

• mentre v'è un nodo con l'indegree zero
  • aggiungere il nodo alla sorta topologico (irrilevante per rilevare cicli)
  • rimuovere il nodo dal grafico
• se c'è ancora qualsiasi nodo del grafo
  • grafico contiene un cycl diretto e. N ordinamento topologico esiste tale grafico
• altro
  • il grafico non contiene un ciclo diretto (è aciclico). L'ordinamento topologico generato è valido.

1. albero

Un grafo è un albero sse è collegato e non contiene ciclo.

Un grafico orientato è un albero con radice se non ha cicli non orientati e c'è solo un vertice con un grado di zero (solo una radice). Inoltre, un grafo orientato è un albero radicato se è connesso, non ha cicli non orientati e ogni nodo con un angolo di zero ha un indegree di massimo uno (ogni sink è una foglia).