Эта программа для обхода графа dfs одна функция является итеративным методом, а другая функция является рекурсивным методом, но обе дают разные ответы
из итеративного я получаю 01234
из рекурсивного я получаю 02341 может кто-нибудь объяснить мне, почему?
ПРИМЕЧАНИЕ. -> Здесь пользователь вводит веса, но они бесполезны в этой реализации dfs, я реализовывал dijkstra, поэтому я рассмотрел веса там, я говорю вам об этом, чтобы вы не путали
программа абсолютно правильная, вы можете вставить ее в свой компилятор
// C program for array implementation of stack
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
// A structure to represent a stack
struct Stack
{
int top;
unsigned capacity;
int* array;
};
int visited[100];
// function to create a stack of given capacity. It initializes size of
// stack as 0
struct Stack* createStack(unsigned capacity)
{
struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
stack->capacity = capacity;
stack->top = -1;
stack->array = (int*)malloc(stack->capacity * sizeof(int));
return stack;
}
// Stack is full when top is equal to the last index
int isFull(struct Stack* stack)
{
return stack->top == stack->capacity - 1;
}
// Stack is empty when top is equal to -1
int isEmpty(struct Stack* stack)
{
return stack->top == -1;
}
// Function to add an item to stack. It increases top by 1
void push(struct Stack* stack, int item)
{
if (isFull(stack))
return;
stack->array[++stack->top] = item;
//printf("%d pushed to stack\n", item);
}
// Function to remove an item from stack. It decreases top by 1
int pop(struct Stack* stack)
{
if (isEmpty(stack))
return INT_MIN;
return stack->array[stack->top--];
}
struct adjlistnode {
int data;
struct adjlistnode* next;
};
struct adjlist {
struct adjlistnode* head;
};
struct graph {
int v;
struct adjlist* array;
};
struct graph* creategraph(int v) {
struct graph* G = (struct graph*) malloc(sizeof(struct graph));
G->v = v;
int i;
G->array = (struct adjlist*)malloc(sizeof(struct adjlist)*v);
for (i = 0; i < v; i++) {
G->array[i].head = NULL;
}
return G;
}
int weight[100][100], Distance[50], path[50];
struct adjlistnode* getnewnode(int ver) {
struct adjlistnode* newnode = (struct adjlistnode*)malloc(sizeof(struct adjlistnode));
newnode->data = ver;
newnode->next = NULL;
return newnode;
}
void addedge(struct graph* G, int src, int dest) {
struct adjlistnode* temp;
temp = getnewnode(dest);
temp->next = G->array[src].head;
G->array[src].head = temp;
//temp = getnewnode(src);
///*temp->next = G->array[dest].head;
//G->array[dest].head = temp;*/
printf(" Enter the weight : ");
int w;
scanf("%d", &w);
weight[src][dest] = w;
weight[dest][src] = w;
}
void printgraph(struct graph* G) {
for (int i = 0; i < G->v; i++) {
struct adjlistnode* temp = G->array[i].head;
printf("%d-> ", i);
while (temp) {
printf(" %d", temp->data);
temp = temp->next;
}
printf("\n");
}
}
// Driver program to test above functions
void dfsiterative(struct graph* G, struct Stack* stack, int s) {
int v, w;
push(stack, s);
visited[s] = 1;
while (!isEmpty(stack)) {
v = pop(stack);
printf("%d", v); ///process v
struct adjlistnode* temp = G->array[v].head;
while (temp) {
w = temp->data;
if (visited[w] == 0) {
push(stack, w);
visited[w] = 1;
}
temp = temp->next;
}
}
}
void dfsrecursive(struct graph* G, int s) {
visited[s] = 1;
printf("%d", s);
struct adjlistnode* temp = G->array[s].head;
while (temp) {
int w = temp->data;
if (visited[w] == 0) {
dfsrecursive(G, w);
temp = temp->next;
}
}
}
int main()
{
// Create a Priority Queue
// 7->4->5->6
struct Stack* stack = createStack(100);
struct graph* G = creategraph(5);
addedge(G, 0, 1);
addedge(G, 1, 2);
addedge(G, 2, 3);
addedge(G, 3, 4);
addedge(G, 0, 2);
for (int i = 0; i < 30; i++) {
visited[i] = 0;
}
printgraph(G);
printf("\n");
//dfsiterative(G,stack,0);
dfsrecursive(G, 0);
return 0;
}