读书笔记: 图（深度遍历和广度遍历） Graph(bfs and Dfs)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#include <stdio.h>

//邻接表
#define MAX_VERTICES 50
typedef struct node *node_pointer;
typedef struct node{
    int vertex;
    struct node *link;
}node;
node_pointer graph[MAX_VERTICES];
int n=0;

#define FALSE 0
#define TRUE 1
short int visited[MAX_VERTICES];

深度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12

void dfs(int v)
{
    //depth first search of a graph beginning with vertex 
    node_pointer w;
    visited[v] = TRUE;
    printf("%5d",v);
    for(w=graph[v];w;w=w->link){
        if(!visited[w->vertex]){
            dfs(w->vertex);
        }
    }
}

广度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

typedef struct queue *queue_pointer;
typedef struct queue{
    int vertex;
    queue_pointer link;
}queue;
void addq(queue_pointer *,queue_pointer *,int);
int deleteq(queue_pointer *);

void bfs(int v){
    node_pointer w;
    queue_pointer front,rear;
    front=rear=NULL;
    printf("%5d",v);
    visited[v] = TRUE;
    addq(&front, &rear, v);
    while(front){
        v= deleteq(&front);
        for(w=graph[v];w;w=w->link){
            if(!visited[w->vertex]){
                printf("%5d",w->vertex);
                addq(&front, &rear, w->vertex);
                visited[w->vertex]=TRUE;
            }
        }
    }
}