2、实现图的深度优先遍历和广度优先遍历 /*用邻接矩阵法创建有向网的算法如下:*/ //#include "adjmatrix.h" #include<stdio.h> *最多顶点个数*/ #define MAX VERTEX NUM20 *表示极大值，即∞*/ #define INFINITY 32768 #defne True 1 #define False 0 #define Error -1 16896 #define Ok 1

深度优先遍历（DFS）：

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

#define MAX_VERTEX_NUM 20

typedef char VertexType;
typedef int EdgeType;

typedef struct {
    VertexType vexs[MAX_VERTEX_NUM];
    EdgeType arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
    int vexnum, arcnum;
} MGraph;

bool visited[MAX_VERTEX_NUM];

void CreateGraph(MGraph* G) {
    printf("请输入顶点数和边数：");
    scanf("%d %d", &(G->vexnum), &(G->arcnum));

    printf("请输入顶点：");
    for (int i = 0; i < G->vexnum; i++) {
        scanf(" %c", &(G->vexs[i]));
    }

    for (int i = 0; i < G->vexnum; i++) {
        for (int j = 0; j < G->vexnum; j++) {
            if (i == j) {
                G->arcs[i][j] = 0;
            } else {
                G->arcs[i][j] = INFINITY;
            }
        }
    }

    printf("请输入每条边的起点、终点、权值：\n");
    for (int k = 0; k < G->arcnum; k++) {
        int i, j, w;
        scanf("%d %d %d", &i, &j, &w);
        G->arcs[i][j] = w;
    }
}

void DFS(MGraph* G, int v) {
    visited[v] = true;
    printf("%c ", G->vexs[v]);

    for (int j = 0; j < G->vexnum; j++) {
        if (G->arcs[v][j] != INFINITY && !visited[j]) {
            DFS(G, j);
        }
    }
}

void DFSTraverse(MGraph* G) {
    for (int i = 0; i < G->vexnum; i++) {
        visited[i] = false;
    }

    for (int i = 0; i < G->vexnum; i++) {
        if (!visited[i]) {
            DFS(G, i);
        }
    }
}

int main() {
    MGraph G;
    CreateGraph(&G);
    printf("深度优先遍历结果：");
    DFSTraverse(&G);
    return 0;
}

广度优先遍历（BFS）：

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

#define MAX_VERTEX_NUM 20

typedef char VertexType;
typedef int EdgeType;

typedef struct {
    VertexType vexs[MAX_VERTEX_NUM];
    EdgeType arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
    int vexnum, arcnum;
} MGraph;

bool visited[MAX_VERTEX_NUM];

void CreateGraph(MGraph* G) {
    printf("请输入顶点数和边数：");
    scanf("%d %d", &(G->vexnum), &(G->arcnum));

    printf("请输入顶点：");
    for (int i = 0; i < G->vexnum; i++) {
        scanf(" %c", &(G->vexs[i]));
    }

    for (int i = 0; i < G->vexnum; i++) {
        for (int j = 0; j < G->vexnum; j++) {
            if (i == j) {
                G->arcs[i][j] = 0;
            } else {
                G->arcs[i][j] = INFINITY;
            }
        }
    }

    printf("请输入每条边的起点、终点、权值：\n");
    for (int k = 0; k < G->arcnum; k++) {
        int i, j, w;
        scanf("%d %d %d", &i, &j, &w);
        G->arcs[i][j] = w;
    }
}

void BFS(MGraph* G, int v) {
    int queue[MAX_VERTEX_NUM], front = 0, rear = 0;
    printf("%c ", G->vexs[v]);
    visited[v] = true;
    queue[rear++] = v;

    while (front != rear) {
        int i = queue[front++];
        for (int j = 0; j < G->vexnum; j++) {
            if (G->arcs[i][j] != INFINITY && !visited[j]) {
                printf("%c ", G->vexs[j]);
                visited[j] = true;
                queue[rear++] = j;
            }
        }
    }
}

void BFSTraverse(MGraph* G) {
    for (int i = 0; i < G->vexnum; i++) {
        visited[i] = false;
    }

    for (int i = 0; i < G->vexnum; i++) {
        if (!visited[i]) {
            BFS(G, i);
        }
    }
}

int main() {
    MGraph G;
    CreateGraph(&G);
    printf("广度优先遍历结果：");
    BFSTraverse(&G);
    return 0;
}