数据结构系列21 - 图的创建与遍历 - C语言实现

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 5

typedef struct Graph {
    char* vexs;
    int** arcs;
    int vexNum;
    int arcNum;
}Graph;

typedef struct Queue {
    int front;
    int rear;
    int data[MAXSIZE];
}Queue;

Queue* initQueue() {
    Queue* Q = (Queue*)malloc(sizeof(Queue));
    Q->front = Q->rear = 0;
    return Q;
}

int isFull(Queue* Q) {
    if ((Q->rear + 1) % MAXSIZE == Q->front) {
        return 1;
    }
    else {
        return 0;
    }
}

int isEmpty(Queue* Q) {
    if (Q->front == Q->rear) {
        return 1;
    }
    else {
        return 0;
    }
}

int enQueue(Queue* Q, int data) {
    if (isFull(Q)) {
        return 0;
    }
    else {
        Q->data[Q->rear] = data;
        Q->rear = (Q->rear + 1) % MAXSIZE;
        return 1;
    }
}

int deQueue(Queue* Q) {
    if(isEmpty(Q)) {
        return -1;
    }
    else {
        int data = Q->data[Q->front];
        Q->front = (Q->front + 1) % MAXSIZE;
        return data;
    }
}
Graph* initGraph(int vexNum) {
    Graph* G = (Graph*)malloc(sizeof(Graph));
    G -> vexs = (char*)malloc(sizeof(char) * vexNum);
    G -> arcs = (int**)malloc(sizeof(int*) * vexNum);
    for (int i = 0 ; i < vexNum; i++) {
        G -> arcs[i] = (int*)malloc(sizeof(int) * vexNum);
    }
    G -> vexNum = vexNum;
    G -> arcNum = 0;
    return G;
}

void createGraph(Graph* G, char* vexs, int* arcs) {
    for (int i = 0 ; i < G -> vexNum; i++) {
        G -> vexs[i] = vexs[i];
        for (int j = 0; j < G -> vexNum; j++) {
            G -> arcs[i][j] = *(arcs + i * G -> vexNum + j);
            if (G -> arcs[i][j] != 0)
                G -> arcNum ++;
        }
    }
    G -> arcNum /= 2;
}

void DFS(Graph* G, int* visited, int index) {
    printf("%c\t", G -> vexs[index]);
    visited[index] = 1;
    for (int i = 0; i < G ->vexNum; i++) {
        if (G -> arcs[index][i] == 1 && !visited[i]) {
            DFS(G, visited, i);
        }
    }
}

void BFS(Graph* G, int* visited, int index) {
    Queue* Q = initQueue();
    printf("%c\t", G -> vexs[index]);
    visited[index] = 1;
    enQueue(Q, index);
    while (!isEmpty(Q)) {
        int i = deQueue(Q);
        for (int j = 0; j < G -> vexNum; j++) {
            if (G -> arcs[i][j] == 1 && !visited[j]) {
                printf("%c\t", G -> vexs[j]);
                visited[j] = 1;
                enQueue(Q, j);
            }
        }
    }
}

int main() {
    Graph* G = initGraph(5);
    int* visited = (int*)malloc(sizeof(int) * G -> vexNum);
    for (int i = 0; i < G -> vexNum; i++)
        visited[i] = 0;
    int arcs[5][5] = {
        0,1,1,1,0,
        1,0,1,1,1,
        1,1,0,0,0,
        1,1,0,0,1,
        0,1,0,1,0
    };
    createGraph(G, "ABCDE", (int*)arcs);
    DFS(G, visited, 0);
    printf("\n");
    for (int i = 0; i < G -> vexNum; i++)
        visited[i] = 0;
    BFS(G, visited, 0);
    printf("\n");
    return 0;
}