logo

TechCodeview

Struttura dei dati del grafico e algoritmi

Struttura dei dati del grafico è una raccolta di nodi collegato da bordi . È usato per rappresentare le relazioni tra diverse entità. Algoritmi grafici sono metodi utilizzati per manipolare e analizzare i grafici, risolvendo vari problemi come trovare la strada più breve O rilevamento dei cicli.

array Java di stringhe



Tabella dei contenuti

Componenti di un grafico:

  • Vertici: I vertici sono le unità fondamentali del grafico. A volte, i vertici sono anche conosciuti come vertici o nodi. Ogni nodo/vertice può essere etichettato o non etichettato.
  • Bordi: Gli spigoli vengono disegnati o utilizzati per collegare due nodi del grafico. Può essere ordinata una coppia di nodi in un grafo diretto. Gli Edge possono connettere due nodi qualsiasi in qualsiasi modo possibile. Non ci sono regole. A volte, i bordi sono noti anche come archi. Ogni bordo può essere etichettato/non etichettato.

Operazioni di base sui grafici:

Di seguito sono riportate le operazioni di base sul grafico:



  • Inserimento di Nodi/Bordi nel grafico – Inserisci un nodo nel grafico.
  • Eliminazione di nodi/spigoli nel grafico – Elimina un nodo dal grafico.
  • Ricerca sui grafici: cerca un'entità nel grafico.
  • Attraversamento dei grafici: attraversamento di tutti i nodi del grafico.

Applicazioni del grafico:

Di seguito sono riportate le applicazioni nella vita reale:

  • Le strutture dei dati grafici possono essere utilizzate per rappresentare le interazioni tra i giocatori di una squadra, come passaggi, tiri e contrasti. L’analisi di queste interazioni può fornire approfondimenti sulle dinamiche del team e sulle aree di miglioramento.
  • Comunemente utilizzato per rappresentare i social network, come le reti di amici sui social media.
  • I grafici possono essere utilizzati per rappresentare la topologia delle reti di computer, come le connessioni tra router e switch.
  • I grafici vengono utilizzati per rappresentare le connessioni tra diversi luoghi in una rete di trasporti, come strade e aeroporti.
  • I grafici vengono utilizzati nelle reti neurali dove i vertici rappresentano i neuroni e i bordi rappresentano le sinapsi tra di loro. Le reti neurali vengono utilizzate per capire come funziona il nostro cervello e come cambiano le connessioni quando impariamo. Il cervello umano ha circa 10^11 neuroni e quasi 10^15 sinapsi.

Nozioni di base sul grafico:

BFS e DFS nel grafico:

  • Prima traversata in ampiezza per un grafico
  • Prima traversata della profondità per un grafico
  • Applicazioni della ricerca in profondità
  • Applicazioni dell'attraversamento di prima ampiezza
  • Prima ricerca iterativa della profondità
  • BFS per grafico disconnesso
  • Chiusura transitiva di un grafico utilizzando DFS
  • Differenza tra BFS e DFS

Cicli nel grafico:

  • Rileva il ciclo in un grafico diretto
  • Rilevare il ciclo in un grafo non orientato
  • Rileva il ciclo in un grafico diretto utilizzando i colori
  • Rileva un ciclo negativo in un grafico | (Bellmann Ford)
  • Cicli di lunghezza n in un grafo non orientato e connesso
  • Rilevamento del ciclo negativo utilizzando Floyd Warshall
  • Clonare un grafico aciclico diretto
  • Unione per rango e compressione del percorso nell'algoritmo di ricerca unione
  • Percorso più breve nel grafico:
    • Algoritmo del percorso più breve di Dijkstra
    • Algoritmo di Bellman-Ford
    • Algoritmo di Floyd Warshall
    • Algoritmo di Johnson per i cammini minimi di tutte le coppie
    • Cammino minimo in un grafo aciclico diretto
    • Algoritmo di Dial
    • Grafico multistadio (percorso più breve)
    • Percorso più breve in un grafico non ponderato
    • Algoritmo del ciclo del peso medio minimo (o medio) di Karp
    • 0-1 BFS (percorso più breve in un grafico a pesi binari)
    • Trovare il ciclo di peso minimo in un grafico non orientato

    Albero di copertura minimo:

    • Albero di copertura minimo di Prim (MST)
    • Algoritmo dell’albero di copertura minimo di Kruskal
    • Differenza tra l'algoritmo di Prim e quello di Kruskal per MST
    • Applicazioni del problema dell'albero di copertura minimo
    • Costo minimo per collegare tutte le città
    • Numero totale di Spanning Tree in un grafico
    • Albero di copertura minimo del prodotto
    • Algoritmo di eliminazione inversa per lo spanning tree minimo
    • Algoritmo di Boruvka per il Minimum Spanning Tree

    Ordinamento topologico:

    • Ordinamento topologico
    • Tutti i tipi topologici di un grafo aciclico diretto
    • Algoritmo di Kahn per l'ordinamento topologico
    • Edge massimi che possono essere aggiunti al DAG in modo che rimanga DAG
    • Cammino più lungo in un grafo aciclico diretto
    • Ordinamento topologico di un grafico che utilizza l'ora di partenza del vertice

    Connettività nel grafico:

    • Punti di articolazione (o vertici tagliati) in un grafico
    • Componenti biconnessi
    • Ponti in un grafico
    • Cammino e circuito Euleriano
    • Algoritmo di Fleury per la stampa del percorso o circuito euleriano
    • Componenti fortemente connessi
    • Contare tutti i possibili percorsi da una sorgente a una destinazione con esattamente k spigoli
    • Circuito di Eulero in un grafico diretto
    • Lunghezza della catena più corta per raggiungere la parola di destinazione
    • Scopri se è possibile concatenare una serie di stringhe per formare un cerchio
    • Algoritmo di Tarjan per trovare componenti fortemente connessi
    • Percorsi da percorrere in ciascun nodo utilizzando ciascun bordo (I Sette Ponti di Königsberg)
    • Connettività dinamica | Imposta 1 (incrementale)

    Portata massima nel grafico:

    • Introduzione al problema del flusso massimo
    • Algoritmo di Ford-Fulkerson per il problema del flusso massimo
    • Trova il numero massimo di percorsi disgiunti tra due vertici
    • Trovare il taglio s-t minimo in una rete di flusso
    • Corrispondenza bipartita massima
    • Problema di assegnazione dei canali
    • Introduzione all'algoritmo Push Relabel
    • Algoritmo di Karger - Set 1 - Introduzione e implementazione
    • Algoritmo di Dinic per il flusso massimo

    Alcuni devono risolvere problemi sul grafico:

    • Trova la lunghezza della regione più grande nella matrice booleana
    • Contare il numero di alberi in una foresta
    • Un problema del grafico di Peterson
    • Clonare un grafico non orientato
    • Colorazione dei grafici (introduzione e applicazioni)
    • Implementazione del problema del commesso viaggiatore (TSP).
    • Problema di copertura del vertice | Set 1 (Introduzione e algoritmo approssimativo)
    • Problema dei centri K | Set 1 (algoritmo approssimativo goloso)
    • Modello Erdos Renyl (per generare grafici casuali)
    • Postino cinese o ispezione del percorso | Set 1 (introduzione)
    • Algoritmo di Hierholzer per grafi diretti
    • Controlla se un dato grafico è bipartito o meno
    • Problema del serpente e della scala
    • Boggle (Trova tutte le parole possibili in una tavola di personaggi)
    • Algoritmo di Hopcroft Karp per la massima introduzione all'abbinamento
    • Tempo minimo per far marcire tutte le arance
    • Costruisci un grafico partendo dai gradi dati di tutti i vertici
    • Determina se esiste un sink universale in un grafo diretto
    • Numero di nodi sink in un grafico
    • Problema delle due cricche (controlla se il grafico può essere diviso in due cricche)

    Alcuni quiz:

    • Quiz sull'attraversamento del grafico
    • Quiz sul percorso più breve del grafico
    • Quiz sull'albero di copertura minimo del grafico
    • Quiz sui grafici

    Link veloci :

    • Le 10 principali domande dell'intervista sulla ricerca approfondita (DFS)
    • Alcune domande interessanti sul percorso più breve
    • Video sui grafici

    Consigliato:

    • Impara la struttura dei dati e gli algoritmi | Tutorial DSA