logo

TechCodeview

Diagramdatastruktur och algoritmer

Grafisk datastruktur är en samling av knutpunkter ansluten av kanter . Det används för att representera relationer mellan olika enheter. Grafalgoritmer är metoder som används för att manipulera och analysera grafer, lösa olika problem som t.ex hitta den kortaste vägen eller upptäcka cykler.

namn



Innehållsförteckning

Komponenter i en graf:

  • Vertices: Vertices är de grundläggande enheterna i grafen. Ibland är hörn också kända som vertex eller noder. Varje nod/vertex kan vara märkt eller omärkt.
  • Kanter: Kanter ritas eller används för att koppla samman två noder i grafen. Det kan beställas par av noder i en riktad graf. Edges kan ansluta två valfria noder på vilket sätt som helst. Det finns inga regler. Ibland är kanter också kända som bågar. Varje kant kan märkas/omärkas.

Grundläggande funktioner för grafer:

Nedan är de grundläggande operationerna på grafen:



  • Infoga noder/kanter i grafen – Infoga en nod i grafen.
  • Borttagning av noder/kanter i grafen – Ta bort en nod från grafen.
  • Söka på grafer – Sök efter en enhet i grafen.
  • Traversering av grafer – Genomför alla noder i grafen.

Tillämpningar av graf:

Följande är de verkliga applikationerna:

  • Diagramdatastrukturer kan användas för att representera interaktionerna mellan spelare i ett lag, såsom passningar, skott och tacklingar. Att analysera dessa interaktioner kan ge insikter om teamdynamik och områden för förbättringar.
  • Används vanligtvis för att representera sociala nätverk, till exempel nätverk av vänner på sociala medier.
  • Grafer kan användas för att representera topologin för datornätverk, såsom kopplingarna mellan routrar och switchar.
  • Grafer används för att representera kopplingarna mellan olika platser i ett transportnätverk, såsom vägar och flygplatser.
  • Grafer används i neurala nätverk där hörn representerar neuroner och kanter representerar synapserna mellan dem. Neurala nätverk används för att förstå hur vår hjärna fungerar och hur kopplingar förändras när vi lär oss. Den mänskliga hjärnan har cirka 10^11 neuroner och nära 10^15 synapser.

Grunderna i grafen:

BFS och DFS i graf:

  • Bredth First Traversal för en graf
  • Depth First Traversal för en graf
  • Tillämpningar av Depth First Search
  • Tillämpningar av Breadth First Traversal
  • Iterativt djup första sökning
  • BFS för Disconnected Graph
  • Transitiv stängning av en graf med DFS
  • Skillnaden mellan BFS och DFS

Cykler i diagram:

  • Detektera cykel i en riktad graf
  • Detektera cykel i en oriktad graf
  • Upptäck cykel i en direkt graf med hjälp av färger
  • Upptäck en negativ cykel i en graf | (Bellman Ford)
  • Cykler med längden n i en oriktad och sammankopplad graf
  • Upptäcker negativ cykel med Floyd Warshall
  • Klona en riktad acyklisk graf
  • Union efter rang- och sökvägskomprimering i Union-Find Algorithm
  • Kortaste vägen i diagrammet:
    • Dijkstras kortaste vägsalgoritm
    • Bellman–Ford Algoritm
    • Floyd Warshall-algoritm
    • Johnsons algoritm för alla pars kortaste vägar
    • Kortaste vägen i riktad acyklisk graf
    • Urtavlans algoritm
    • Flerstegsdiagram (kortaste vägen)
    • Kortaste vägen i en oviktad graf
    • Karps lägsta medelvärde (eller genomsnittlig) viktcykelalgoritm
    • 0-1 BFS (kortaste vägen i en binär viktgraf)
    • Hitta minimiviktscykeln i en oriktad graf

    Minsta spännvidd:

    • Prims minimum spannning träd (MST)
    • Kruskals Minimum Spanning Tree Algorithm
    • Skillnad mellan Prims och Kruskals algoritm för MST
    • Tillämpningar av problem med minsta spännande träd
    • Minsta kostnad för att ansluta alla städer
    • Totalt antal spännande träd i en graf
    • Minsta produktspannande träd
    • Omvänd raderingsalgoritm för minsta spannande träd
    • Boruvkas algoritm för Minimum Spanning Tree

    Topologisk sortering:

    • Topologisk sortering
    • Alla topologiska sorters av en riktad acyklisk graf
    • Kahns algoritm för topologisk sortering
    • Maximalt antal kanter som kan läggas till DAG så det förblir DAG
    • Längsta vägen i en riktad acyklisk graf
    • Topologisk sorts graf med avgångstid för vertex

    Anslutning i graf:

    • Artikulationspunkter (eller Cut Vertices) i en graf
    • Bikopplade komponenter
    • Broar i en graf
    • Eulerisk väg och krets
    • Fleurys algoritm för att skriva ut Eulerian Path eller Circuit
    • Starkt anslutna komponenter
    • Räkna alla möjliga promenader från en källa till en destination med exakt k kanter
    • Euler-krets i en riktad graf
    • Längden på den kortaste kedjan för att nå målordet
    • Ta reda på om en rad strängar kan kedjas ihop för att bilda en cirkel
    • Tarjans algoritm för att hitta starkt anslutna komponenter
    • Vägar för att resa varje nod med varje kant (Königsbergs sju broar)
    • Dynamisk anslutning | Uppsättning 1 (inkrementell)

    Maximalt flöde i diagram:

    • Max Flow Problem Introduktion
    • Ford-Fulkerson-algoritm för problem med maximalt flöde
    • Hitta det maximala antalet kantavskiljande banor mellan två hörn
    • Hitta minsta s-t-snitt i ett flödesnätverk
    • Maximal tvådelad matchning
    • Kanaltilldelningsproblem
    • Introduktion till Push Relabel Algorithm
    • Kargers algoritm - Set 1 - Introduktion och implementering
    • Dinics algoritm för maximalt flöde

    Vissa måste göra Problem on Graph:

    • Hitta längden på den största regionen i Boolean Matrix
    • Räkna antalet träd i en skog
    • Ett Peterson-grafproblem
    • Klona en oriktad graf
    • Graffärgning (introduktion och tillämpningar)
    • Implementering av Traveling Salesman Problem (TSP).
    • Vertex Cover Problem | Set 1 (introduktion och ungefärlig algoritm)
    • K Centers Problem | Set 1 (Girig ungefärlig algoritm)
    • Erdos Renyl-modell (för generering av slumpmässiga grafer)
    • Kinesisk postman eller ruttinspektion | Set 1 (introduktion)
    • Hierholzers algoritm för riktad graf
    • Kontrollera om en given graf är tvådelad eller inte
    • Problem med orm och stege
    • Boggle (Hitta alla möjliga ord i en tavla med tecken)
    • Hopcroft Karp-algoritm för maximal matchning-introduktion
    • Minsta tid för att ruttna alla apelsiner
    • Konstruera en graf från givna grader av alla hörn
    • Bestäm om det finns en universell sänka i en riktad graf
    • Antal sjunknoder i en graf
    • Två klickproblem (Kontrollera om grafen kan delas upp i två klick)

    Några frågesporter:

    • Frågesporter om Graph Traversal
    • Frågesporter om Graph Shortest Path
    • Frågesporter om Graph Minimum Spanning Tree
    • Frågesport om grafer

    Snabblänkar :

    • Topp 10 intervjufrågor om Depth First Search (DFS)
    • Några intressanta frågor om kortaste vägen
    • Videor på grafer

    Rekommenderad:

    • Lär dig datastruktur och algoritmer | Handledning för DSA