Ранее мы видели, как построить простой граф, используя список смежности, и как пройти его, используя обход в ширину, используя приведенный ниже граф.
Опираясь на это, мы увидим, как перемещаться по графу, используя другой популярный подход, известный как «обход в глубину» (DFT). Это видео является дополнением к этой статье.
В конце этого сообщения я представил код, написанный на C, чтобы показать вам, как можно реализовать DFS. В конце концов, мы должны уметь писать код, а не просто говорить о подходе.
Популярным применением обхода в глубину является топологическая сортировка или упорядочение.
Понимание DFT
В ДПФ мы выбираем вершину для начала. В нашем примере граф дружбы мы начинаем с Анкура. Мы посещаем это и отмечаем его как посещенное.
Далее мы исследуем смежные с этой вершиной вершины, как у Рины. Но мы не исследуем следующую смежную с Анкуром вершину, т.е. Дикшит, вместо этого мы исследуем дальше и посетим Нидхи, который связан с Риной. Итак, что мы делаем, так это пересекаем глубины, пока не достигнем листа или узла, который был посещен. Затем мы возвращаемся назад и начинаем исследовать следующий соседний узел, то есть Дикшит.
Разве это не звучит рекурсивно? Это так, и, как вы увидите, наш код использует рекурсию для выполнения DFT.
Давайте посмотрим код для реализации этого. Он доступен на Github. Здесь интерес представляет метод DFS(), который выполняет работу по обходу нашего графа дружбы.
#include<stdio.h>
#include<stdlib.h>
/*
Author: @ankur
Date: March 25, 2018
Version: 0.1
This Program illustrates Depth First Traversal.
*/
#define MAXV 6 /* maximum number of vertices */
#define VISITED 1
/*Structure for Vertex*/
struct node{
int label; /*data*/
char *name; /*data*/
int status;
struct node *next; /*Pointer to next node*/
};
struct node vertices[MAXV];
char *names[MAXV];
void addToList(struct node *x, int data);
void traverseGraph();
void initNames();
void displayNames();
void DFS(struct node *t);
int main(){
/*Initialize Names*/
initNames();
displayNames();
/*Initialize the Array*/
for(int i=0;i<MAXV;i++){
vertices[i].label = i;
vertices[i].name = names[i];
vertices[i].next = NULL;
}
/*
Say we have the following Edges {(0,1), (0,2), (1,2)}
Let's build the Adjacency List.
*/
addToList(&vertices[0], 1);
addToList(&vertices[0], 3);
addToList(&vertices[1], 2);
addToList(&vertices[1], 0);
addToList(&vertices[1], 4);
addToList(&vertices[2], 1);
addToList(&vertices[3], 0);
addToList(&vertices[3], 5);
addToList(&vertices[4], 1);
/*Traverse the Adjacency List*/
traverseGraph();
/*Depth First Traversal*/
printf("\n\n---------------DFS Traversal---------------\n\n");
DFS(&vertices[0]);
printf("\n");
return 0;
}
/*Here we are trying to add an edge x->y*/
void addToList(struct node *x, int data){
printf("Going to Add %d to the Vertex %d \n", data, x->label);
struct node *y = (struct node *)(malloc(sizeof(struct node)));
if(y!=NULL){
y->label = data;
y->name = names[data];
if(x->next != NULL)
y->next = x->next;
else
y->next = NULL;
x->next = y;
}
}
void traverseGraph(){
printf("\nLet's see who all are Friends \n\n");
for(int i=0;i<MAXV;i++){
struct node *temp = &vertices[i];
printf("%s is friend to --> ", temp->name);
if(temp->next != NULL){
temp = temp->next;
while(temp != NULL){
printf("%s", temp->name);
if(temp->next != NULL)
printf(", ");
temp = temp->next;
}
}
printf("\n\n---------------------------------------------\n\n");
}
}
void initNames(){
names[0] = "Ankur";
names[1] = "Dikshit";
names[2] = "Mohan";
names[3] = "Nidhi";
names[4] = "Reena";
names[5] = "Suresh";
}
void displayNames(){
printf("\nWe have the following folks staying in a small town \n\n");
for(int i=0;i<MAXV;i++){
printf("%s ", names[i]);
}
printf("\n\n---------------------------------------------\n\n");
}
void DFS(struct node *qn){
if(qn && qn->status != VISITED){
qn->status = VISITED;
printf("Visited %s\n", qn->name);
if(qn->next != NULL){
/*for each vetrex adjacent to v do BFS*/
qn = qn->next;
while(qn != NULL){
DFS(&vertices[qn->label]);
qn = qn->next;
}
}
}else{
return;
}
}
Когда вы запускаете эту программу, ожидаемый результат
