Algorytm Kruskala
Algorytm polega na łączeniu wielu poddrzew w jedno za pomocą krawędzi o najmniejszej wadze. W rezultacie powstałe drzewo będzie minimalne. Na początek należy posortować wszystkie krawędzie w porządku niemalejącym. Po tej czynności można przystąpić do tworzenia drzewa. Proces ten nazywa się rozrastaniem lasu drzew. Wybieramy krawędzie o najmniejszej wadze i jeśli wybrana krawędź należy do dwóch różnych drzew należy je scalić (dodać do lasu). Krawędzie wybieramy tak długo, aż wszystkie wierzchołki nie będą należały do jednego drzewa.
Algorytm Prima
Budowę minimalnego drzewa rozpinającego zaczynamy od dowolnego wierzchołka, np. od pierwszego. Dodajemy wierzchołek do drzewa a wszystkie krawędzie incydentne umieszczamy na posortowanej wg. wag liście. Następnie zdejmujemy z listy pierwszą krawędź (o najmniejszej wadze). Sprawdzamy, czy drugi wierzchołek tej krawędzi nalerzy do tworzonego drzewa. Jeżeli tak, to nie ma sensu dodawać takiej krawędzi (bo oba jej wierzchołki znajdują sięw drzewie), porzucamy krawędź i pobieramy z listy następną. Jeżeli jednak wierzchołka nie ma w drzewie, to nalerzy dodać krawędź do drzewa, by wierzchołek ten znalazł się w drzewie rozpinającym. Następnie dodajemy do posortowanej listy wszystkie krawędzie incydentne z dodanym wierzchołkiem i pobieramy z niej kolejny element.
Jednym zdaniem: zawsze dodajemy do drzewa krawędź o najmniejszej wadze, osiągalną (w przeciwieństwie do Kruskala) z jakiegoś wierzchołka tego drzewa.
Przeszukiwanie grafu wszerz (BFS) i w głąb (DFS)
Procedury przeglądania grafu w głąb (DFS) i wszerz (BFS) są bardzo często wykorzystywane w innych, bardziej złożonych algorytmach (np. badania spójności).
W strategii DFS wybrany wierzchołek należy umieścić na stosie, zaznaczyć jako odwiedzony a następnie przejść do jego następnika. Następnik również umieszczamy na stosie, zaznaczamy jako odwiedzony przechodzimy do jego następnika. Jak widać procedurę można wywoływać rekurencyjnie. Jeśli dojdziemy do takiego wierzchołka, że nie ma on krawędzi incydentych z nieodwiedzonymi wierzchołkami, należy usunąć go ze stosu i pobrać ze stosu kolejny wierzchołek do przeszukania. W praktyce stosuje się zasadę, że jeśli przeszukiwany wierzchołek jest połączony krawędziami z wieloma wierzchołkami, wybiera się do przeszukania wierzchołek o najmniejszej liczbie porządkowej. Dlatego szukając kolejny nieodwiedzony następnik należy rozpoczynać od końca macierzy. Przeszukiwanie DFS wykorzystuje się do badania spójności grafu. Jeśli procedura wywołana dla pierwszego wierzchołka "dotrze" do wszystkich wierzchołków grafu to graf jest spójny.
Aby przeszukać graf wszerz (BFS) należy zamiast stosu wykorzystać kolejkę do przechowywania wierzchołków a kolejnych nieodwiedzonych następników szukać od początku macierzy.
Przeszukanie grafu wszerz (BFS) pozwala wyznaczyć najkrótsze z możliwych ścieżek od ustalonego wierzchołka grafu s do wszystkich pozostałych wierzchołków grafu - w wyniku dla każdego wierzchołka u otrzymujemy jedną ze wszystkich ścieżek s-...-u o najkrótszej długości. Jeśli pomiędzy wierzchołkami s oraz u istnieje kilka takich ścieżek, to o wyborze ścieżki decyduje kolejność przetwarzania następników poszczególnych wierzchołków ścieżki.
Dodatkowo dla każdego wierzchołka grafu u algorytm wyznacza jego głębokość g[u] w stosunku do wierzchołka początkowego s, czyli długość znalezione najkrótszej ścieżki s-...-u.
Przeszukanie wszerz wykonuje się przy pomocy kolejki, w której na początku umieszczamy wierzchołek startowy s. Każdemu składnikowi kolejki towarzyszy jego głębokość względem wierzchołka startowego s zapisana w tablicy głębokości g - ten pierwszy składnik kolejki, którym jest wierzchołek s zapisujemy z głębokością 0.
Algotytm musi mieć możliwość sprawdzania, dla których wierzchołków grafu wyznaczona została już najkrótsza ścieżka i jej długość.
Przeszukanie grafu w głąb (DFS) polega na takim przejściu przez graf, aby każdy wierzchołek został odwiedzony dokładnie jeden raz - odwiedzane są wszystkie wierzchołki grafu, czyli odmiennie niż w przeszukiwaniu wszerz, gdzie odwiedzone zostaną tylko wierzchołki osiągalne z wierzchołka źródłowego. W odróżnieniu od algorytmu BFS przeszukiwanie w głąb jest algorytmem rekurencyjnym, pozwalającym zebrać sporo informacji o strukturze grafu.