图的深度优先遍历和广度优先遍历

代码是在上一篇博客的基础上实现的。传送门：图的邻接矩阵、邻接表的表示

增加的点：
1、结点中增加Tag，用于记录结点的是否已经遍历
2、邻接矩阵的DFS和BFS
3、邻接表的DFS和BFS

---

2.1号：补充，突然发现我的程序，边的权重只能为1位数，如果权重为多位数，只取个位数的值，因此需要进行下面的修改：(邻接矩阵、邻接表都一样)
1) weight初始化为0（以前没有初始化）
2）从控制台得到：weight = weight * 10 + int(c - ‘0’);(以前为：weight = int(c - ‘0’);)
这样weight就可以是int范围内的任意正整数值了。

GNode.h

#define MAXSIZE 10
//邻接矩阵
typedef struct AMGraph {
    char** vexs;
    int** arcs;
    int vexnum, arcnum;
    bool* tag;      //新增 标记
}AMGraph;


//邻接表

typedef struct OtherInfo {
    //权重等
    int weight;
}OtherInfo;

//边结点
typedef struct ArcNode {
    int index;
    struct ArcNode* next;
    OtherInfo info;
}ArcNode;


//表头结点
typedef struct VNode {
    char* data;
    struct ArcNode* first;
}VNode;

typedef struct ALGraph {
    VNode* vertices;
    int vexnum, arcnum;
    bool* tag;      //新增 标记
}ALGraph;

main,cpp

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

#include"GNode.h"

//邻接矩阵
void CreateAMGraph(AMGraph *g);     //创建邻接矩阵
void GetIndex(char** vex, int size, char* resource, int &result);   //根据输入顶点信息得到顶点的索引
bool Equal(char* s1, char* s2);             //判断两个字符串是否相等
void PrintAMGraphMatrix(AMGraph *g);        //输出邻接矩阵
void DFS_AM(AMGraph* g, int count);         //深度优先遍历 邻接矩阵
void BFS_AM(AMGraph* g);                    //广度优先遍历 邻接矩阵

                                            //邻接表
void CreateALGraph(ALGraph* g);             //创建邻接表
void GetIndex_s(ALGraph* g, int size, char* resource, int &result); //根据输入顶点信息得到顶点的索引
void PrintfALGraph(ALGraph* g);             //输出邻接表
void DFS_AL(ALGraph* g, int count);         //深度优先遍历    邻接表
void BFS_AL(ALGraph* g);                    //广度优先遍历    邻接表


int main() {

    //邻接矩阵
    printf("*******邻接矩阵******：\n");
    AMGraph* g;
    g = (AMGraph*)malloc(sizeof(AMGraph));
    CreateAMGraph(g);       //创建邻接矩阵
    PrintAMGraphMatrix(g);      //输出矩阵
    printf("\n** 邻接矩阵深度优先遍历:");
    DFS_AM(g, 0);       //深度优先遍历
    printf("\n** 邻接矩阵广度优先遍历:\n");
    BFS_AM(g);

    //邻接表
    printf("\n*******邻接表******：\n");
    ALGraph* ag;
    ag = (ALGraph *)malloc(sizeof(ALGraph));
    CreateALGraph(ag);      //创建邻接表
    PrintfALGraph(ag);      //输出矩阵
    printf("\n** 邻接表深度优先遍历:");
    DFS_AL(ag, 0);
    printf("\n** 邻接表广度优先遍历:\n");
    BFS_AL(ag);


    return 0;
}

void CreateAMGraph(AMGraph *g) {
    printf("输入顶点和边的个数(例: 8 10)： ");
    scanf_s("%d %d", &g->vexnum, &g->arcnum);
    getchar();      //吃掉回车
    char c = 'A';
    int i, j;
    //初始化
    g->vexs = (char **)malloc(sizeof(char *) * g->vexnum);
    g->arcs = (int **)malloc(sizeof(int *) * g->vexnum);
    for (i = 0; i < g->vexnum; i++)
        g->arcs[i] = (int *)malloc(sizeof(int) * g->vexnum);
    for (i = 0; i < g->vexnum; i++)
        for (j = 0; j < g->vexnum; j++)
            g->arcs[i][j] = 0;
    g->tag = (bool*)malloc(sizeof(bool) * g->vexnum);
    for (i = 0; i < g->vexnum; i++)
        g->tag[i] = false;


    printf("按顺序输入各个顶点的数据 (例: v1 v2 v3 v4)： ");
    for (i = 0; i < g->vexnum; i++) {
        g->vexs[i] = (char*)malloc(sizeof(char) * MAXSIZE);
        c = getchar();
        int j = 0;
        while ((c != ' ') && (c != '\n')) {
            g->vexs[i][j] = c;
            ++j;
            c = getchar();
        }
        g->vexs[i][j] = '\0';
    }

    /*
    for (int i = 0; i < g->vexnum; i++)
    printf("%s\n", g->vexs[i]);
    */

    printf("输入边信息(点1，点2，权重)，(例: (v1,v2,2) (v1,v3,5))：");
    while ((c = getchar()) != '\n') {
        char v1[MAXSIZE];
        char v2[MAXSIZE];
        int weight = 0;
        int count = 0;
        i = 0;
        if (c == '(') {
            while ((c = getchar()) != ')') {    //根据'，'的个数判断怎么赋值
                if (c == ',') {
                    ++i;
                    count = 0;
                    continue;
                }
                if (i == 0) {       //‘，’个数为0，赋值给v1
                    v1[count++] = c;
                    v1[count] = '\0';
                }
                else if (i == 1) {      //‘，’个数为1，赋值给v2
                    v2[count++] = c;
                    v2[count] = '\0';
                }
                else if (i == 2)        //‘，’个数为2，赋值给weight
                    weight = weight * 10 + int(c - '0');
            }
        }
        int index1, index2;
        index1 = index2 = 0;
        GetIndex(g->vexs, g->vexnum, v1, index1);   //得到与v1中存储信息相同的顶点索引
        GetIndex(g->vexs, g->vexnum, v2, index2);   //得到与v2中存储信息相同的顶点索引
        if (index1 < 0 || index2 < 0)
            printf("输入顶点不存在\n");
        else {
            //有向图
            //g->arcs[index1][index2] = weight;

            //无向图
            g->arcs[index1][index2] = g->arcs[index2][index1] = weight;
        }
    }
}

void GetIndex(char** vex, int size, char* resource, int &result) {
    int i;
    int temp = 0;
    for (i = 0; i < size; i++) {
        if (Equal(vex[i], resource)) {
            result = i;
            temp = 1;
            break;
        }
    }
    if (temp == 0)
        result = -1;
}

bool Equal(char* s1, char* s2) {
    int n1 = strlen(s1);
    int n2 = strlen(s2);
    if (n1 != n2)
        return false;
    int i;
    for (i = 0; i < n1; i++) {
        if (s1[i] != s2[i])
            return false;
    }
    if (i == n1)
        return true;
    return false;
}

void PrintAMGraphMatrix(AMGraph *g) {
    int** matrix = g->arcs;
    int row = g->vexnum;
    printf("\n** 图对应的邻接矩阵：\n");
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < row; j++)
            printf("%d\t", matrix[i][j]);
        printf("\n");
    }
}

void CreateALGraph(ALGraph* g) {
    char c;
    int i, j;

    printf("输入顶点个数和边个数(例:4 5)：");
    scanf_s("%d %d", &g->vexnum, &g->arcnum);
    getchar();
    g->vertices = (VNode*)malloc(sizeof(VNode) * g->vexnum);
    g->tag = (bool*)malloc(sizeof(bool) * g->vexnum);
    for (i = 0; i < g->vexnum; i++)
        g->tag[i] = false;

    printf("输入各个顶点的数据(例：v0 v1 v2 v3)：");
    for (i = 0; i < g->vexnum; i++) {
        j = 0;
        g->vertices[i].data = (char *)malloc(sizeof(char) * MAXSIZE);
        g->vertices[i].first = NULL;
        c = getchar();
        while (c != ' ' && c != '\n') {
            g->vertices[i].data[j++] = c;
            c = getchar();
        }
        g->vertices[i].data[j] = '\0';
    }

    /*for (i = 0; i < g->vexnum; i++)
    printf("%s\n", g->vertices[i].data);
    */
    printf("输入边数据 (例：(v0,v1,3)(v2,v3,5))：");
    char v1[MAXSIZE], v2[MAXSIZE];
    int weight = 0;
    while ((c = getchar()) != '\n') {
        i = j = 0;
        if (c == '(') {
            while ((c = getchar()) != ')') {
                if (c == ',') {
                    ++i;
                    j = 0;
                }
                else {
                    if (i == 0) {
                        v1[j++] = c;
                        v1[j] = '\0';
                    }
                    else if (i == 1) {
                        v2[j++] = c;
                        v2[j] = '\0';
                    }
                    else if (i == 2) {
                        weight = weight * 10 + int(c - '0');
                    }
                }
            }
        }
        //printf("%s %s %d\n", v1, v2, weight);
        int index1, index2;
        GetIndex_s(g, g->vexnum, v1, index1);
        GetIndex_s(g, g->vexnum, v2, index2);
        if (index1 < 0 || index2 < 0)
            printf("输入的顶点有误\n");
        else {
            //有向图 :第一个顶点为起点，第二个顶点为端点
            ArcNode* q = (ArcNode*)malloc(sizeof(ArcNode));
            q->index = index2;
            q->info.weight = weight;
            q->next = NULL;
            ArcNode *p = g->vertices[index1].first;
            if (p == NULL) {
                g->vertices[index1].first = q;
            }
            else {
                while (p->next) {
                    p = p->next;
                }
                p->next = q;
            }

            //无向图 在有向图的基础上加上下面的
            q = (ArcNode*)malloc(sizeof(ArcNode));
            q->index = index1;
            q->info.weight = weight;
            q->next = NULL;
            p = (g->vertices[index2].first);
            if (p == NULL) {
                g->vertices[index2].first = q;
            }
            else {
                while (p->next) {
                    p = p->next;
                }
                p->next = q;
            }
        }
    }
}

void GetIndex_s(ALGraph* g, int size, char* resource, int &result) {
    int temp = 0;
    for (int i = 0; i < size; i++) {
        if (Equal(g->vertices[i].data, resource)) {
            result = i;
            temp = 1;
            break;
        }
    }
    if (temp == 0)
        result = -1;
}

void PrintfALGraph(ALGraph* g) {
    printf("\n** 图对应的邻接表：\n");
    for (int i = 0; i< g->vexnum; i++) {
        ArcNode *p = g->vertices[i].first;
        printf("顶点结点%d链表: ", i);
        while (p) {
            printf("(索引:%d, 权重:%d) ", p->index, p->info.weight);
            p = p->next;
        }
        printf("\n");
    }
}

void DFS_AM(AMGraph* g, int count) {
    int i;
    printf("%s ", g->vexs[count]);
    g->tag[count] = true;
    for (i = 0; i < g->vexnum; i++) {
        if (g->arcs[count][i] != 0 && g->tag[i] == false) {
            DFS_AM(g, i);
        }
    }
}

void DFS_AL(ALGraph* g, int count) {
    printf("%s ", g->vertices[count].data);
    g->tag[count] = true;
    ArcNode* p = g->vertices[count].first;
    while (p) {
        if (g->tag[p->index] == false) {
            DFS_AL(g, p->index);
        }
        p = p->next;
    }
}

void BFS_AM(AMGraph* g) {
    if (g->vexnum <= 0) {
        printf("空图\n");
        return;
    }
    int *queue;
    int i;
    for (i = 0; i < g->vexnum; i++)
        g->tag[i] = false;
    queue = (int*)malloc(sizeof(int) * g->vexnum);
    queue[0] = 0;
    g->tag[0] = true;

    i = 0;
    int start = 0;
    int num = 1;
    int size = 0;
    int j = 0;
    printf("%s\n", g->vexs[queue[j]]);
    while (num > 0) {
        for (i = start; i < start + num; i++) {
            for (j = 0; j < g->vexnum; j++) {
                if (g->arcs[i][j] != 0 && g->tag[j] == false) {
                    queue[start + num + size] = j;
                    printf("%s ", g->vexs[queue[j]]);
                    g->tag[j] = true;
                    ++size;
                }
            }
        }
        start += num;
        num = size;
        size = 0;
        printf("\n");
    }
    free(queue);
}

void BFS_AL(ALGraph* g) {
    if (g->vexnum <= 0) {
        printf("空图\n");
        return;
    }
    int* queue;
    int i;
    queue = (int *)malloc(sizeof(int) * g->vexnum);
    for (i = 0; i < g->vexnum; i++)
        g->tag[i] = false;

    queue[0] = 0;
    printf("%s\n", g->vertices[queue[0]].data);
    g->tag[0] = true;
    int start = 0;
    int num = 1;
    int size = 0;

    while (num > 0) {
        for (i = start; i < start + num; i++) {
            ArcNode* p = g->vertices[queue[i]].first;
            while (p) {
                if (g->tag[p->index] == false) {
                    printf("%s ", g->vertices[p->index].data);
                    g->tag[p->index] = true;
                    queue[start + num + size] = p->index;
                    size++;
                }
                p = p->next;
            }
        }
        start += num;
        num = size;
        size = 0;
        printf("\n");
    }
    free(queue);
}

两个例子：

结果：