graph

graph.array.c

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

int *queue_new(int size)
{
    int *queue = (int *)malloc(sizeof(int) * size);
    int i;

    for(i = 0; i < size; ++i)
    {
        queue[i] = EOF;
    }

    return queue;
}

int queue_pop(int *queue, int size)
{
    int i, pop;

    pop = queue[0];

    if(pop == EOF) return EOF;

    for(i = 0; i < size && queue[i] != EOF; ++i)
    {
        if(i == size - 1)
        {
            queue[i] = EOF;
        }
        else
        {
            queue[i] = queue[i + 1];
        }
    }

    return pop;
}

int queue_push(int *queue, int size, int value)
{
    int i;

    for(i = 0; i < size; ++i)
    {
        if(queue[i] == EOF)
        {
            queue[i] = value;
            return 1;
        }
    }
    return 0;
}

int queue_empty(int *queue)
{
    return queue[0] == EOF;
}

void BFS(int **graphic, int n, int node)
{
    int *walked = (int *)calloc(n, sizeof(int));
    int *queue = queue_new(n);
    int i;

    printf("%d", node);
    walked[node - 1] = 1;

    queue_push(queue, n, node);

    while(!queue_empty(queue))
    {
        node = queue_pop(queue, n);
        for(i = 0; i < n; ++i)
        {
            if(graphic[node - 1 + i * n] && !walked[i])
            {
                printf(", %d", i + 1);
                walked[i] = 1;
                queue_push(queue, n, i + 1);
            }
        }
    }
}

void DFS_walk(int **graphic, int n, int node, int *walked)
{
    int i;
    for(i = 0; i < n; ++i)
    {
        if(graphic[node - 1 + i * n] && !walked[i])
        {
            printf(", %d", i + 1);
            walked[i] = 1;
            DFS_walk(graphic, n, i + 1, walked);
        }
    }
}

void DFS(int **graphic, int n, int node)
{
    int *walked = (int *)calloc(n, sizeof(int));
    printf("%d", node);
    walked[node - 1] = 1;
    DFS_walk(graphic, n, node, walked);
}

int main()
{/*
    int graphic[8][8] =
      {
          {1, 1, 0, 1, 0, 1, 0, 0},
          {1, 1, 1, 0, 0, 0, 0, 0},
          {0, 1, 1, 0, 1, 0, 0, 1},
          {1, 0, 0, 1, 1, 1, 0, 0},
          {0, 0, 1, 1, 1, 0, 1, 0},
          {1, 0, 0, 1, 0, 1, 1, 0},
          {0, 0, 0, 0, 1, 1, 1, 1},
          {0, 0, 1, 0, 0, 0, 1, 1}
      }
    ; // map
    int n = 8; // number of nodes
*/
    int graphic[5][5] =
      {
          {1, 0, 0, 0, 1},
          {0, 1, 0, 0, 1},
          {0, 0, 1, 0, 0},
          {1, 0, 1, 1, 1},
          {0, 0, 0, 0, 1}
      }
    ; // map
    int n = 5; // number of nodes

    printf("DFS: ");
    DFS((int **)graphic, n, 5);

    printf("\n");

    printf("BFS: ");
    BFS((int **)graphic, n, 5);

    printf("\n");

    return 0;
}

graph.link.c

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

struct map_path
{
    int value;
    struct map_path *next;
};

struct map_node
{
    int value;
    struct map_path *path;
    struct map_node *next;
};

struct map
{
    struct map_node *node_head;
};

struct map *map_new()
{
    struct map *map = (struct map *)malloc(sizeof(struct map));
    map->node_head = NULL;
    return map;
}

struct map_node *map_node_alloc(struct map_node **next_of_prev_node, int value)
{
    struct map_node *newnode = (struct map_node *)malloc(sizeof(struct map_node));
    newnode->value = value;
    newnode->path = NULL;
    newnode->next = *next_of_prev_node;
    *next_of_prev_node = newnode;
    return newnode;
}

int map_node_insert(struct map *map, int node_value)
{
    struct map_node *node = map->node_head;

    while(1)
    {
        if(node == NULL)
        {
            map_node_alloc(&(map->node_head), node_value);
            return 1;
        }
        else if(node->value < node_value)
        {
            if(node->next == NULL || node->next->value > node_value)
            {
                map_node_alloc(&(node->next), node_value);
                return 1;
            }
            else
            {
                node = node->next;
            }
        }
        else
        {
            return 0;
        }
    }
}

struct map_node *map_node_get(struct map *map, int node_value)
{
    struct map_node *node = map->node_head;

    while(1)
    {
        if(node == NULL)
        {
            return NULL;
        }
        else if(node->value < node_value)
        {
            if(node->next == NULL || node->next->value > node_value)
            {
                return NULL;
            }
            else
            {
                node = node->next;
            }
        }
        else if(node->value == node_value)
        {
            return node;
        }
        else
        {
            return NULL;
        }
    }
}

struct map_path *map_path_alloc(struct map_path **next_of_prev_path, int value)
{
    struct map_path *newpath = (struct map_path *)malloc(sizeof(struct map_path));
    newpath->value = value;
    newpath->next = *next_of_prev_path;
    *next_of_prev_path = newpath;
    return newpath;
}

int map_path_insert(struct map_node *node, int path_value)
{
    struct map_path *path = node->path;

    while(1)
    {
        if(path == NULL)
        {
            map_path_alloc(&(node->path), path_value);
            return 1;
        }
        else if(path->value < path_value)
        {
            if(path->next == NULL || path->next->value > path_value)
            {
                map_path_alloc(&(path->next), path_value);
                return 1;
            }
            else
            {
                path = path->next;
            }
        }
        else
        {
            return 0;
        }
    }
}

int *queue_new(int size)
{
    int *queue = (int *)malloc(sizeof(int) * size);
    int i;

    for(i = 0; i < size; ++i)
    {
        queue[i] = EOF;
    }

    return queue;
}

int queue_pop(int *queue, int size)
{
    int i, pop;

    pop = queue[0];

    if(pop == EOF) return EOF;

    for(i = 0; i < size && queue[i] != EOF; ++i)
    {
        if(i == size - 1)
        {
            queue[i] = EOF;
        }
        else
        {
            queue[i] = queue[i + 1];
        }
    }

    return pop;
}

int queue_push(int *queue, int size, int value)
{
    int i;

    for(i = 0; i < size; ++i)
    {
        if(queue[i] == EOF)
        {
            queue[i] = value;
            return 1;
        }
    }
    return 0;
}

int queue_empty(int *queue)
{
    return queue[0] == EOF;
}

void BFS(struct map *map, int n, int node)
{
    int *walked = (int *)calloc(n, sizeof(int));
    int *queue = queue_new(n);
    struct map_path *path;

    printf("%d", node);
    walked[node - 1] = 1;

    queue_push(queue, n, node);

    while(!queue_empty(queue))
    {
        node = queue_pop(queue, n);
        path = map_node_get(map, node)->path;
        while(path != NULL)
        {
            if(!walked[path->value - 1])
            {
                printf(", %d", path->value);
                walked[path->value - 1] = 1;
                queue_push(queue, n, path->value);
            }
            path = path->next;
        }
    }
}

void DFS_walk(struct map *map, int n, int node, int *walked)
{
    struct map_path *path = map_node_get(map, node)->path;

    while(path != NULL)
    {
        if(!walked[path->value - 1])
        {
            printf(", %d", path->value);
            walked[path->value - 1] = 1;
            DFS_walk(map, n, path->value, walked);
        }
        path = path->next;
    }
}

void DFS(struct map *map, int n, int node)
{
    int *walked = (int *)calloc(n, sizeof(int));
    printf("%d", node);
    walked[node - 1] = 1;
    DFS_walk(map, n, node, walked);
}

int main()
{
    int graphic[8][8] =
      {
          {0, 1, 0, 1, 0, 1, 0, 0},
          {1, 0, 1, 0, 0, 0, 0, 0},
          {0, 1, 0, 0, 1, 0, 0, 1},
          {1, 0, 0, 0, 1, 1, 0, 0},
          {0, 0, 1, 1, 0, 0, 1, 0},
          {1, 0, 0, 1, 0, 0, 1, 0},
          {0, 0, 0, 0, 1, 1, 0, 1},
          {0, 0, 1, 0, 0, 0, 1, 0}
      }
    ; // map
    int n = 8; // number of nodes
/*
    int graphic[5][5] =
      {
          {0, 0, 0, 0, 1},
          {0, 0, 0, 0, 1},
          {0, 0, 0, 0, 0},
          {1, 0, 1, 0, 1},
          {0, 0, 0, 0, 0}
      }
    ; // map
    int n = 5; // number of nodes
*/
    int i, j;
    struct map *map = map_new();

    for(i = 0; i < n; ++i)
    {
        map_node_insert(map, i + 1);
        for(j = 0; j < n; ++j)
        {
            if(((int **)graphic)[i + j * n])
            {
                map_path_insert(map_node_get(map, i + 1), j + 1);
            }
        }
    }

    printf("DFS: ");
    DFS(map, n, 7);

    printf("\n");

    printf("BFS: ");
    BFS(map, n, 7);

    printf("\n");

    return 0;
}