İlk Derinlik Arama (DFS) Algoritması

İçindekiler

Derinlik İlk Arama Algoritması
Derinlik İlk Arama Örneği
DFS Sözde Kodu (özyinelemeli uygulama)
Python, Java ve C / C ++ 'da DFS Uygulaması
Derinlik İlk Aramanın Karmaşıklığı
DFS Algoritmasının Uygulanması

Bu eğitimde, örnekler ve sözde kod ile derinlemesine ilk arama algoritması hakkında bilgi edineceksiniz. Ayrıca, DFS'yi C, Java, Python ve C ++ dillerinde uygulamayı öğreneceksiniz.

Önce Derinlik Arama veya Derinlik ilk geçiş, bir grafiğin veya ağaç veri yapısının tüm köşelerini aramak için özyinelemeli bir algoritmadır. Geçiş, bir grafiğin tüm düğümlerini ziyaret etmek anlamına gelir.

Derinlik İlk Arama Algoritması

Standart bir DFS uygulaması, grafiğin her köşesini iki kategoriden birine yerleştirir:

Ziyaret
Ziyaret Edilmedi

Algoritmanın amacı, döngülerden kaçınırken her bir tepe noktasını ziyaret edilmiş olarak işaretlemektir.

DFS algoritması şu şekilde çalışır:

Grafiğin köşelerinden herhangi birini bir yığının üstüne koyarak başlayın.
Yığının en üst öğesini alın ve ziyaret edilenler listesine ekleyin.
Bu tepe noktasının bitişik düğümlerinin bir listesini oluşturun. Ziyaret edilenler listesinde olmayanları yığının en üstüne ekleyin.
Yığın boşalana kadar 2. ve 3. adımları tekrarlamaya devam edin.

Derinlik İlk Arama Örneği

Önce Derinlik Arama algoritmasının nasıl çalıştığını bir örnekle görelim. 5 köşeli yönsüz bir grafik kullanıyoruz.

5 köşeli yönlendirilmemiş grafik

Köşe 0'dan başlıyoruz, DFS algoritması onu Ziyaret Edilenler listesine koyarak ve tüm bitişik köşelerini yığına koyarak başlıyor.

Öğeyi ziyaret edin ve ziyaret edilenler listesine ekleyin

Daha sonra, yığının en üstündeki öğeyi, yani 1'i ziyaret ediyoruz ve bitişiğindeki düğümlere gidiyoruz. 0 zaten ziyaret edildiğinden, bunun yerine 2'yi ziyaret ediyoruz.

Yığının en üstündeki öğeyi ziyaret edin

Vertex 2, 4'te ziyaret edilmemiş bir bitişik köşeye sahiptir, bu yüzden onu yığının en üstüne ekleriz ve onu ziyaret ederiz.

Son eleman 3'ü ziyaret ettikten sonra, ziyaret edilmemiş bitişik düğümleri yok, bu yüzden grafiğin İlk Derinlik Geçişini tamamladık.

DFS Sözde Kodu (özyinelemeli uygulama)

DFS için sözde kod aşağıda gösterilmiştir. İnit () işlevinde, her düğümde DFS işlevini çalıştırdığımıza dikkat edin. Bunun nedeni, grafiğin iki farklı bağlantısı kesilmiş parçası olabileceğinden, her köşeyi kapsadığımızdan emin olmak için DFS algoritmasını her düğümde çalıştırabiliriz.

 DFS (G, u) u.visited = her v ∈ G.Adj (u) için doğru v.visited == false DFS (G, v) init () (Her u ∈ G u.visited = false Her biri için u ∈ G DFS (G, u))

Python, Java ve C / C ++ 'da DFS Uygulaması

Bir örnekle İlk Derinlik Arama Algoritmasının kodu aşağıda gösterilmiştir. Kod, diğer detaylar yerine algoritmaya odaklanabilmemiz için basitleştirildi.

Python Java C C +

 # DFS algorithm in Python # DFS algorithm def dfs(graph, start, visited=None): if visited is None: visited = set() visited.add(start) print(start) for next in graph(start) - visited: dfs(graph, next, visited) return visited graph = ('0': set(('1', '2')), '1': set(('0', '3', '4')), '2': set(('0')), '3': set(('1')), '4': set(('2', '3'))) dfs(graph, '0')

 // DFS algorithm in Java import java.util.*; class Graph ( private LinkedList adjLists(); private boolean visited(); // Graph creation Graph(int vertices) ( adjLists = new LinkedList(vertices); visited = new boolean(vertices); for (int i = 0; i < vertices; i++) adjLists(i) = new LinkedList(); ) // Add edges void addEdge(int src, int dest) ( adjLists(src).add(dest); ) // DFS algorithm void DFS(int vertex) ( visited(vertex) = true; System.out.print(vertex + " "); Iterator ite = adjLists(vertex).listIterator(); while (ite.hasNext()) ( int adj = ite.next(); if (!visited(adj)) DFS(adj); ) ) public static void main(String args()) ( Graph g = new Graph(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 3); System.out.println("Following is Depth First Traversal"); g.DFS(2); ) )

 // DFS algorithm in C #include #include struct node ( int vertex; struct node* next; ); struct node* createNode(int v); struct Graph ( int numVertices; int* visited; // We need int** to store a two dimensional array. // Similary, we need struct node** to store an array of Linked lists struct node** adjLists; ); // DFS algo void DFS(struct Graph* graph, int vertex) ( struct node* adjList = graph->adjLists(vertex); struct node* temp = adjList; graph->visited(vertex) = 1; printf("Visited %d ", vertex); while (temp != NULL) ( int connectedVertex = temp->vertex; if (graph->visited(connectedVertex) == 0) ( DFS(graph, connectedVertex); ) temp = temp->next; ) ) // Create a node struct node* createNode(int v) ( struct node* newNode = malloc(sizeof(struct node)); newNode->vertex = v; newNode->next = NULL; return newNode; ) // Create graph struct Graph* createGraph(int vertices) ( struct Graph* graph = malloc(sizeof(struct Graph)); graph->numVertices = vertices; graph->adjLists = malloc(vertices * sizeof(struct node*)); graph->visited = malloc(vertices * sizeof(int)); int i; for (i = 0; i adjLists(i) = NULL; graph->visited(i) = 0; ) return graph; ) // Add edge void addEdge(struct Graph* graph, int src, int dest) ( // Add edge from src to dest struct node* newNode = createNode(dest); newNode->next = graph->adjLists(src); graph->adjLists(src) = newNode; // Add edge from dest to src newNode = createNode(src); newNode->next = graph->adjLists(dest); graph->adjLists(dest) = newNode; ) // Print the graph void printGraph(struct Graph* graph) ( int v; for (v = 0; v numVertices; v++) ( struct node* temp = graph->adjLists(v); printf(" Adjacency list of vertex %d ", v); while (temp) ( printf("%d -> ", temp->vertex); temp = temp->next; ) printf(""); ) ) int main() ( struct Graph* graph = createGraph(4); addEdge(graph, 0, 1); addEdge(graph, 0, 2); addEdge(graph, 1, 2); addEdge(graph, 2, 3); printGraph(graph); DFS(graph, 2); return 0; )

 // DFS algorithm in C++ #include #include using namespace std; class Graph ( int numVertices; list *adjLists; bool *visited; public: Graph(int V); void addEdge(int src, int dest); void DFS(int vertex); ); // Initialize graph Graph::Graph(int vertices) ( numVertices = vertices; adjLists = new list(vertices); visited = new bool(vertices); ) // Add edges void Graph::addEdge(int src, int dest) ( adjLists(src).push_front(dest); ) // DFS algorithm void Graph::DFS(int vertex) ( visited(vertex) = true; list adjList = adjLists(vertex); cout << vertex << " "; list::iterator i; for (i = adjList.begin(); i != adjList.end(); ++i) if (!visited(*i)) DFS(*i); ) int main() ( Graph g(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 3); g.DFS(2); return 0; )