Estructura de dades del gràfic és una col·lecció de nodes connectat per vores . S'utilitza per representar relacions entre diferents entitats. Algorismes gràfics són mètodes utilitzats per manipular i analitzar gràfics, resolent diversos problemes com trobar el camí més curt o detecció de cicles.

tokenitzador de cadena java

Taula de contingut

• Components d'un gràfic
• Operacions bàsiques sobre gràfics
• Aplicacions del Gràfic
• Conceptes bàsics de gràfic
• BFS i DFS al gràfic
• Cicles en gràfic
• El camí més curt del gràfic
• Spanning Tree mínim
• Ordenació topològica
• Connectivitat a Graph
• Flux màxim al gràfic
• Alguns han de fer problemes al gràfic
• Alguns qüestionaris

Components d'un gràfic:

• Vèrtexs: Els vèrtexs són les unitats fonamentals de la gràfica. De vegades, els vèrtexs també es coneixen com a vèrtex o nodes. Cada node/vèrtex es pot etiquetar o no.
• Vores: Les arestes es dibuixen o s'utilitzen per connectar dos nodes del gràfic. Es pot ordenar un parell de nodes en un gràfic dirigit. Les vores poden connectar dos nodes de qualsevol manera possible. No hi ha regles. De vegades, les vores també es coneixen com arcs. Cada vora es pot etiquetar/no etiquetar.

Operacions bàsiques sobre gràfics:

A continuació es mostren les operacions bàsiques del gràfic:

• Inserció de nodes/arestes al gràfic: inseriu un node al gràfic.
• Supressió de nodes/vores del gràfic: suprimeix un node del gràfic.
• Cerca en gràfics: cerca una entitat al gràfic.
• Travessia de gràfics: travessant tots els nodes del gràfic.

Aplicacions del gràfic:

A continuació es mostren les aplicacions de la vida real:

• Les estructures de dades de gràfics es poden utilitzar per representar les interaccions entre jugadors d'un equip, com ara passades, tirs i entrades. L'anàlisi d'aquestes interaccions pot proporcionar informació sobre la dinàmica d'equip i les àrees de millora.
• S'utilitza habitualment per representar xarxes socials, com ara xarxes d'amics a les xarxes socials.
• Els gràfics es poden utilitzar per representar la topologia de les xarxes d'ordinadors, com ara les connexions entre encaminadors i commutadors.
• Els gràfics s'utilitzen per representar les connexions entre diferents llocs d'una xarxa de transport, com ara carreteres i aeroports.
• Els gràfics s'utilitzen a les xarxes neuronals on els vèrtexs representen les neurones i les arestes representen les sinapsis entre elles. Les xarxes neuronals s'utilitzen per entendre com funciona el nostre cervell i com canvien les connexions quan aprenem. El cervell humà té unes 10^11 neurones i prop de 10^15 sinapsis.

Conceptes bàsics del gràfic:

• Introducció als gràfics
• Gràfic i les seves representacions
• Tipus de gràfics amb exemples
• Propietats bàsiques d'un gràfic
• Aplicacions, avantatges i inconvenients de Graph
• Transposició del gràfic
• Diferència entre gràfic i arbre

BFS i DFS al gràfic:

• Primer recorregut d'amplada per a un gràfic
• Primer recorregut de profunditat per a un gràfic
• Aplicacions de Depth First Search
• Aplicacions de Breadth First Traversal
• Primera cerca iterativa de profunditat
• BFS per a gràfic desconnectat
• Tancament transitiu d'un gràfic mitjançant DFS
• Diferència entre BFS i DFS

Cicles en gràfic:

• Detectar el cicle en un gràfic dirigit
• Detectar cicle en un gràfic no dirigit
• Detecta el cicle en un gràfic directe mitjançant colors
• Detectar un cicle negatiu en un gràfic | (Bellman Ford)
• Cicles de longitud n en un gràfic no dirigit i connectat
• Detecció de cicle negatiu amb Floyd Warshall
• Clonar un gràfic acíclic dirigit
• Unió per rang i compressió de camí a l'algoritme Union-Find
• Camí més curt del gràfic:
  • Algorisme del camí més curt de Dijkstra
  • Algoritme Bellman-Ford
  • Algoritme de Floyd Warshall
  • L'algorisme de Johnson per als camins més curts de tots els parells
  • Camí més curt en el gràfic acíclic dirigit
  • Algoritme de marcatge
  • Gràfic multietapa (camí més curt)
  • El camí més curt d'un gràfic no ponderat
  • Algorisme de cicle de pes mitjà mínim (o mitjà) de Karp
  • 0-1 BFS (camí més curt en un gràfic de pes binari)
  • Trobeu el cicle de pes mínim en un gràfic no dirigit

  Arbre spanning mínim:

  • Arbre d'abast mínim de Prim (MST)
  • Algoritme de l'arbre d'abast mínim de Kruskal
  • Diferència entre l'algorisme de Prim i Kruskal per a MST
  • Aplicacions del problema del Minimum Spanning Tree
  • Cost mínim per connectar totes les ciutats
  • Nombre total d'arbres allargats en un gràfic
  • Arbre d'abast mínim de producte
  • Algorisme d'eliminació inversa per a l'arbre d'abast mínim
  • L'algorisme de Boruvka per a l'arbre d'abast mínim

  Ordenació topològica:

  • Ordenació topològica
  • Tots els tipus topològics d'un gràfic acíclic dirigit
  • Algoritme de Kahn per a l'ordenació topològica
  • Les vores màximes que es poden afegir a DAG de manera que es mantingui DAG
  • Camí més llarg en un gràfic acíclic dirigit
  • Classificació topològica d'un gràfic utilitzant el temps de sortida del vèrtex

  Connectivitat al gràfic:

  • Punts d'articulació (o vèrtexs tallats) en un gràfic
  • Components biconnectats
  • Ponts en un gràfic
  • Sender i circuit eulerià
  • Algoritme de Fleury per imprimir el camí o circuit eulerià
  • Components fortament connectats
  • Compteu totes les caminades possibles des d'una font fins a una destinació amb exactament k vores
  • Circuit d'Euler en un gràfic dirigit
  • Longitud de la cadena més curta per arribar a la paraula objectiu
  • Busca si es pot encadenar una matriu de cadenes per formar un cercle
  • Algoritme de Tarjan per trobar components fortament connectats
  • Camins per recórrer cada node utilitzant cada vora (Set Ponts de Königsberg)
  • Connectivitat dinàmica | Conjunt 1 (incremental)

  Flux màxim al gràfic:

  • Introducció al problema de flux màxim
  • Algoritme Ford-Fulkerson per al problema de cabal màxim
  • Trobeu el nombre màxim de camins disjunts d'arestes entre dos vèrtexs
  • Trobeu el tall s-t mínim en una xarxa de flux
  • Coincidència bipartida màxima
  • Problema d'assignació de canals
  • Introducció a l'algoritme Push Relabel
  • Algoritme de Karger- Conjunt 1- Introducció i implementació
  • Algorisme de Dinic per al flux màxim

  Alguns han de fer problemes al gràfic:

  • Trobeu la longitud de la regió més gran de la matriu booleana
  • Comptar el nombre d'arbres d'un bosc
  • Un problema de gràfics de Peterson
  • Clonar un gràfic no dirigit
  • Coloració de gràfics (Introducció i aplicacions)
  • Implementació del problema del venedor ambulant (TSP).
  • Problema de la coberta del vèrtex | Conjunt 1 (Introducció i algorisme aproximat)
  • Problema dels centres K | Conjunt 1 (algoritme aproximat de Greedy)
  • Model Erdos Renyl (per generar gràfics aleatoris)
  • Carter xinès o inspecció de ruta | Set 1 (introducció)
  • Algoritme de Hierholzer per a gràfics dirigits
  • Comproveu si un gràfic donat és bipartit o no
  • Problema de la serp i l'escala
  • Boggle (Troba totes les paraules possibles en un tauler de caràcters)
  • Algoritme Hopcroft Karp per a la màxima concordança-Introducció
  • Temps mínim per podrir totes les taronges
  • Construeix un gràfic a partir de graus donats de tots els vèrtexs
  • Determineu si hi ha una pica universal en un gràfic dirigit
  • Nombre de nodes sumidors en un gràfic
  • Problema de dues cliques (comproveu si el gràfic es pot dividir en dos cliques)

  Alguns qüestionaris:

  • Tests sobre el recorregut de gràfics
  • Tests sobre el camí més curt del gràfic
  • Qüestionaris sobre l'arbre d'abast mínim del gràfic
  • Tests sobre gràfics

  Links ràpids :

  • Les 10 preguntes principals d'entrevistes sobre la primera cerca profunda (DFS)
  • Algunes preguntes interessants del camí més curt
  • Vídeos sobre gràfics

  Recomanat:

  • Apreneu l'estructura de dades i els algorismes | Tutorial DSA