使用邻接表实现图的创建以及深度遍历、广度遍历、dijkstra算法（C语言）

main.c

#include"linkedGragh.h"


int main(int argc, char *argv[]) {

    Gragh *gragh = createGragh();
    printGragh(gragh);
    BFS(gragh);
    dijkstra(gragh, 3);
}
1
2
3
4
5
6
7
8
9
10

linkedGragh.h

#ifndef LINKEDGRAGH_H
#define LINKEDGRAGH_H

#define MAXVALUE (1<<30-1)

#include
#include
#include
#include

typedef struct ENode {
    int index;
    int power;
    struct ENode *next;
}ENode;

typedef struct VNode {
    char name[10];
    struct ENode *next;
}VNode;

typedef struct Gragh {
    int vNum;
    VNode vertex[0];
}Gragh;

Gragh* createGragh();
void printGragh(Gragh *gragh);
void preOrderTraverse(Gragh *gragh);
void preOrderTraverse1(Gragh *gragh, int index, bool visited[]);
void BFS(Gragh *gragh);
void dijkstra(Gragh *gragh, int index);

#endif

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

linkedGragh.c

#include"linkedGragh.h"


Gragh* createGragh() {
    int count;
    char name[10];
    char v1[10], v2[10];
    int power;

    puts("请输入顶点数量:");
    scanf("%d",&count);
    Gragh *gragh = (Gragh*)malloc(sizeof(Gragh)+count*sizeof(VNode));
    gragh->vNum = count;

    for(int i=0;i<gragh->vNum;i++) {
        printf("请输入第 %d 个顶点的名称: ",i+1);
        scanf("%s",gragh->vertex[i].name);
        gragh->vertex[i].next = NULL;
    }

    //puts("请输入边，用空格分隔两个顶点(\"0 0\"结束):");
    puts("请输入边，用空格分隔(\"0 0 0\"结束):");
    scanf("%s",v1);
    scanf("%s",v2);
    scanf("%d",&power);

    while(strcmp(v1, "0") != 0) {
        int i1, i2;
        bool getI1 = false, getI2 = false;
        //找到输入的第一个顶点和第二个顶点的下标
        for(int i=0;i<gragh->vNum;i++) {
            if(getI1 == false && strcmp(v1, gragh->vertex[i].name) == 0) {
                i1 = i;
                getI1 = true;
            }
            if(getI2 == false && strcmp(v2, gragh->vertex[i].name) == 0) {
                i2 = i;
                getI2 = true;
            }
            if(getI1 && getI2) break;
        }
        if(getI1 == false || getI2 == false) {
            printf("未找到对应顶点\n");
            //puts("请重新输入边，用空格分隔两个顶点(\"0 0\"结束):");
            puts("请输入边，用空格分隔(\"0 0 0\"结束):");
            scanf("%s",v1);
            scanf("%s",v2);
            scanf("%d",&power);
            continue;
        }

        ENode *enode = (ENode*)malloc(sizeof(ENode));
        enode->index = i2;
        enode->power = power;
        enode->next = NULL;
        
        if(gragh->vertex[i1].next == NULL) {
            gragh->vertex[i1].next = enode;
        }
        else {
            ENode *tmp = gragh->vertex[i1].next;
            bool alreadyExist = false;

            while(tmp->next != NULL) {
                //说明要添加的边已经存在了，则无需重复添加了
                if(tmp->index == enode->index) {
                    puts("要添加的边已经存在了");
                    alreadyExist = true;
                    break;
                }
                tmp = tmp->next;
            }
            //说明要添加的边已经存在了，则无需重复添加了
            if(tmp->index == enode->index) {
                puts("要添加的边已经存在了");
                alreadyExist = true;
            }
            if(alreadyExist == true) {
                //puts("原来的边已经存在了，请重新输入边，用空格分隔两个顶点(\"0 0\"结束):");
                puts("原来的边已经存在了，请重新输入边，用空格分隔(\"0 0 0\"结束):");
                scanf("%s",v1);
                scanf("%s",v2);
                scanf("%d",&power);
                continue;
            }
            tmp->next = enode;
        }
        
        //puts("请输入边，用空格分隔两个顶点(\"0 0\"结束):");
        puts("请输入边，用空格分隔(\"0 0 0\"结束):");
        scanf("%s",v1);
        scanf("%s",v2);
        scanf("%d",&power);
    }
    return gragh;
}

void printGragh(Gragh *gragh) {
    for(int i=0;i<gragh->vNum;i++) {
        printf("%s -> ",gragh->vertex[i].name);
        if(gragh->vertex[i].next == NULL) {
            printf("NULL\n");
        }
        else {
            ENode *tmp = gragh->vertex[i].next;

            while(tmp->next != NULL) {
                printf("%s -> ",gragh->vertex[tmp->index].name);
                tmp = tmp->next;
            }
            printf("%s -> ",gragh->vertex[tmp->index].name);
            printf("NULL\n");
        }
    }
}

void preOrderTraverse(Gragh *gragh) {
    puts("图的前序遍历为：");
    bool visited[gragh->vNum];
    //将所有的值设为false
    memset(visited, false, gragh->vNum);
    for(int i=0;i<gragh->vNum;i++) {
        if(visited[i] == false) {
            puts("下面是一个连通分量");
            preOrderTraverse1(gragh, i, visited);
        }
    }
}

void preOrderTraverse1(Gragh *gragh, int index, bool visited[]) {
    printf("%s\n",gragh->vertex[index].name);
    visited[index] = true;

    ENode *tmp = gragh->vertex[index].next;
    while(tmp != NULL) {
        if(visited[tmp->index] == false) {
            preOrderTraverse1(gragh, tmp->index, visited);
        }
        tmp = tmp->next;
    }
}

void BFS(Gragh *gragh) {
    //创建一个队列，然后添加一个顶点到队列中
    //随后进行循环，当队列不为空时，取一个队列元素进行处理，然后将该元素的所有未遍历的邻接点添加至队列
    VNode *queue[1000];
    bool visited[gragh->vNum];
    for(int i=0;i<gragh->vNum;i++) {
        visited[i] = false;
    }
    int head = -1, tail = -1;

    queue[++tail] = &gragh->vertex[0];
    visited[0] = true;

    while(head != tail) {
        VNode *tmp = queue[++head];
        printf("%s\n",tmp->name);

        ENode *edge = tmp->next;
        while(edge != NULL) {
            if(visited[edge->index] == false) {
                queue[++tail] = &(gragh->vertex[edge->index]);
                visited[edge->index] = true;
            }
            edge = edge->next;
        }
    }
}


void dijkstra(Gragh *gragh, int index) {
    bool s[gragh->vNum];//记录一个结点是否已经找到最短路劲了
    int dist[gragh->vNum];

    //初始化数组
    for(int i=0;i<gragh->vNum;i++) {
        s[i] = false;
    }
    s[index] = true;
    //给index到 i 的距离赋初值
    for(int i=0;i<gragh->vNum;i++) {
        dist[i] = MAXVALUE;
    }
    if(gragh->vertex[index].next == NULL) {
        puts("该结点无法到达任何结点");
        return;
    }
    ENode *tmp = gragh->vertex[index].next;
    while(tmp != NULL) {
        dist[tmp->index] = tmp->power;
        tmp = tmp->next;
    }
    dist[index] = 0;


    //接下来就是不断地取dist中的最小值并将对应s置为true
    //然后更新与对应dist相关的点的dist值
    //需要考虑是否需要固定循环的次数，如果不固定的话怎样确定循环次数
    //按理来说每次循环找到一个顶点，那么有多少个需要添加的顶点就需要进行多少次循环，但是可能存在一个图中某些顶点
    //与任何其他顶点都没有联系，所以写一个非固定循环次数的程序适应性更强。
    //用一个flag来标志是否还有可以取的点
    bool flag = true;
    while(flag) {
        flag = false;
        //找到dist最小的值
        int minValue = MAXVALUE;
        int minIndex;
        for(int i=0;i<gragh->vNum;i++) {
            if(s[i] == false && dist[i] != MAXVALUE && dist[i]<minValue) {
                minValue = dist[i];
                minIndex = i;
                flag = true;
            }
        }
        if(flag == false) {
            break;
        }
        //找到了点，将其置为已添加状态
        s[minIndex] = true;
        //更新与该点相关的其他点的dist值
        ENode *tmp = gragh->vertex[minIndex].next;
        while(tmp != NULL) {
            //如果 index->minIndex + minIndex->tmp < index -> tmp 就替换
            if(dist[minIndex] + tmp->power < dist[tmp->index]) {
                dist[tmp->index] = dist[minIndex] + tmp->power;
            }
            tmp = tmp->next;
        }
    }

    //打印结果数组
    puts("结果数组为:");
    for(int i=0;i<gragh->vNum;i++) {
        printf("%d ",dist[i]);
    }
    puts("");
}

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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239