DFS

인접 행렬

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 50
#define TRUE 1
#define FALSE 0

typedef struct GraphType{
    int n;
    int adj_mat[MAX_VERTICES][MAX_VERTICES];
} GraphType;

typedef struct Stack{
    int items[MAX_VERTICES];
    int top;
} Stack;

int visited[MAX_VERTICES];

void init(GraphType *g, Stack *s){
    g->n = 0;
    s->top = -1;
    int r, c;
    for(r = 0; r<MAX_VERTICES; r++){
        s->items[r] = 0;
        for(c = 0; c<MAX_VERTICES; c++){
            g->adj_mat[r][c] = 0;
        }
    }

}

int is_Empty(Stack *s){
    return s->top == -1;
}

void push(Stack *s, int value){
    s->items[++s->top] = value;
}

int pop(Stack *s){
    if(is_Empty(s)){
        fprintf(stderr, "underflow");
        return 0;
    }
    return s->items[s->top--];
}

void insert_vertex(GraphType *g, int v){
    if(((g->n)+1) > MAX_VERTICES){
        fprintf(stderr, "vertex overflow");
        return;
    }
    g->n++;
}

void insert_edge(GraphType *g, int start, int end){
    if(start >= g->n || end >= g->n){
        fprintf(stderr, "edge error");
        return;
    }
    g->adj_mat[start][end] = 1;
    g->adj_mat[end][start] = 1;
}

void dfs(GraphType *g, int start){
    visited[start] = TRUE;
    printf("%d ->" ,start);
    for(int i=1; i<=g->n; i++){
        if(g->adj_mat[start][i] && !visited[i]){
            dfs(g, i);
        }
    }
}

void init_Visited(){
    for(int i=0; i<MAX_VERTICES; i++){
        visited[i] = FALSE;
    }
}

int main(){
    GraphType *g;
    Stack stack;
    g = (GraphType*)malloc(sizeof(GraphType));
    init(g, &stack);
    int vertex, edge, start;
    int e1, e2;
    scanf("%d %d", &vertex, &edge);
    for(int i=1; i<=vertex; i++){
        insert_vertex(g, i);
    }
    for(int i=0; i<edge; i++){
        scanf("%d %d", &e1, &e2);
        insert_edge(g, e1, e2);
        insert_edge(g, e2, e1);
    }
    int count;
    printf("vertex input : ");
    scanf("%d", &count);
    for(int i=0; i<count; i++){
        scanf("%d", &start);
        push(&stack, start);
    }
    while(!is_Empty(&stack)){
        int v = pop(&stack);
        init_Visited();
        printf("vertex %d dfs\n", v);
        dfs(g, v);
        printf("\n");
    }

}

인접 리스트

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 50
#define TRUE 1
#define FALSE 0

typedef struct Stack{
    int items[MAX_VERTICES];
    int top;
} Stack;

typedef struct GraphNode{
    int vertex;
    struct GraphNode *link;
} GraphNode;

typedef struct GraphType{
    int n;
    GraphNode *adj_list[MAX_VERTICES];
} GraphType;

int visited[MAX_VERTICES];

void init(GraphType *g, Stack *s){
    g->n = 0;
    s->top = -1;
    for(int i=0; i<MAX_VERTICES; i++){
        g->adj_list[i] = NULL;
        s->items[i] = 0;
    }
}

int is_Empty(Stack *s){
    return s->top == -1;
}

void push(Stack *s, int vertex){
    s->items[++s->top] = vertex;
}

int pop(Stack *s){
    if(is_Empty(s)){
        fprintf(stderr, "stack underflow");
        return 0;
    }
    return s->items[s->top--];
}

void insert_vertex(GraphType *g, int v){
    if(((g->n)+1) > MAX_VERTICES){
        fprintf(stderr, "vertex overflow");
        return;
    }
    g->n++;
}

void insert_edge(GraphType *g, int u, int v){
    GraphNode *node;
    if(u>=g->n || v>=g->n){
        fprintf(stderr, "edge error");
        return;
    }
    node = (GraphNode*)malloc(sizeof(GraphNode));
    node->vertex = v;
    node->link = g->adj_list[u];
    g->adj_list[u] = node;
}

void dfs(GraphType *g, int start){
    GraphNode *node;
    visited[start] = TRUE;
    printf("%d -> ", start);
    node = g->adj_list[start];
    for(node; node != NULL; node = node->link){
        if(!visited[node->vertex]){
            dfs(g, node->vertex);
        }
    }
}

void init_Visited(){
    for(int i=0; i<MAX_VERTICES; i++){
        visited[i] = 0;
    }
}

int main(){
    GraphType *g;
    Stack stack;
    g = (GraphType*)malloc(sizeof(GraphType));
    init(g, &stack);
    int vertex, edge, num, start;
    scanf("%d %d", &vertex, &edge);
    int e1, e2;

    for(int i=1; i<=vertex; i++){
        insert_vertex(g, i);
    }
    for(int i=0; i<edge; i++){
        scanf("%d %d", &e1, &e2);
        insert_edge(g, e1, e2);
        insert_edge(g, e2, e1);
    }

    printf("vertex count : ");
    scanf("%d ", &num);
    for(int i=0; i<num; i++){
        scanf("%d", &start);
        push(&stack, start);
    }

    while(!is_Empty(&stack)){
        init_Visited();
        int v = pop(&stack);
        printf("vertex : %d\n", v);
        dfs(g, v);
        printf("\n");
    }
    free(g);
    return 0;


}