Dfs
#include <stdio.h>
 
int array[10] = {1,2,3,4,5,6,7,8,9,10};
int map[10][10] = {0};
int visit[10] = {0};
 
void DFS(int n)
{
    int i;
    printf("%d ", array[n]);                    // visit Node and set visit[n] to true
    visit[n] = 1;
 
    for (i = 0; i < 10; i++) {
        if (map[n][i] && !visit[i])              // don't forget to check both visit[i] && map[n][i]
            DFS(i);
    }
}
 
int main()
{
    int i, a, b;
 
    printf("input edge\n");
    for (i = 0; i < 100 && scanf("%d  %d", &a, &b); i++) {
        map[a][b] = 1;
        printf("next\n");
    }
 
    printf("DFS: ");
    DFS(0);
    printf("\n");
}

Time Complexity

Adjacency Matrix:
O(n2) — for each node, we should check it connection between every other nodes -> n*n
Adjacency List:
O(n + e) — we visit n node, that is n, and check all their edges, that is e -> n + e

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License