:掌握图的邻接矩阵和邻接表两个存储结构及表示。 掌握图的dfs和bfs两种遍历算

图是由顶点和边组成的一种数据结构，用于表示元素之间的关系。在计算机中，我们可以使用邻接矩阵和邻接表来存储和表示图。

邻接矩阵是一个二维数组，大小为n*n，其中n是图中顶点的个数。对于图中的每条边(u, v)，在邻接矩阵的(u, v)位置上标记1，表示顶点u和顶点v相邻。若图是无向图，则邻接矩阵是对称的；若图是有向图，则邻接矩阵不一定对称。

邻接表是一种链表的数组，数组的大小为n，每个索引位置对应一个顶点，链表中存储与该顶点相邻的所有顶点。对于每个顶点u，我们可以使用一个链表来存储与其相邻的顶点v。

图的深度优先搜索（DFS）是一种遍历算法，从一个起始顶点出发，沿着一条路径尽可能深入，直到无法继续为止，然后回溯到前一个顶点，从另一条路径继续。DFS使用栈来保存需要访问的顶点。

图的广度优先搜索（BFS）是一种遍历算法，从一个起始顶点出发，首先访问其所有的邻接顶点，然后再依次访问和这些邻接顶点相邻的未访问顶点。BFS使用队列来保存需要访问的顶点。

总结起来，邻接矩阵和邻接表是图的两种常见存储结构，分别适用于不同类型的图。DFS和BFS是常用的遍历算法，用于访问图中的所有顶点。

相关问题

使用邻接矩阵和邻接表存储结构存储图，并分别对这两种存储结构存储的图进行DFS和BFS

邻接矩阵存储图：

邻接矩阵是用一个二维数组表示的图，数组中每个元素表示两个顶点之间是否存在一条边。如果两个顶点之间存在边，则该元素的值为1，否则为0。在无向图中，邻接矩阵是对称的，即A[i][j]=A[j][i]。

下面是使用邻接矩阵存储图的DFS和BFS算法实现：

// DFS算法实现
void DFS(int v, int visited[], int n, int A[][n]) {
    visited[v] = 1;  // 标记当前节点已被访问
    printf("%d ", v);

    for (int i = 0; i < n; i++) {  // 遍历当前节点的所有邻居
        if (A[v][i] == 1 && visited[i] == 0) {
            DFS(i, visited, n, A);  // 递归访问邻居节点
        }
    }
}

// BFS算法实现
void BFS(int s, int n, int A[][n]) {
    int visited[n];
    memset(visited, 0, sizeof(visited));  // 初始化visited数组

    queue<int> q;
    visited[s] = 1;
    q.push(s);

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        printf("%d ", v);

        for (int i = 0; i < n; i++) {
            if (A[v][i] == 1 && visited[i] == 0) {
                visited[i] = 1;
                q.push(i);
            }
        }
    }
}

邻接表存储图：

邻接表是由一个数组和若干个链表组成的数据结构，数组中每个元素对应一个顶点，链表中存储该顶点的所有邻居。在链表中，每个节点表示一个邻居，包含两个字段：邻居节点的编号和指向下一个邻居节点的指针。

下面是使用邻接表存储图的DFS和BFS算法实现：

// DFS算法实现
void DFS(int v, int visited[], vector<int> adj[]) {
    visited[v] = 1;  // 标记当前节点已被访问
    printf("%d ", v);

    for (auto u : adj[v]) {  // 遍历当前节点的所有邻居
        if (visited[u] == 0) {
            DFS(u, visited, adj);  // 递归访问邻居节点
        }
    }
}

// BFS算法实现
void BFS(int s, vector<int> adj[]) {
    int visited[adj.size()];
    memset(visited, 0, sizeof(visited));  // 初始化visited数组

    queue<int> q;
    visited[s] = 1;
    q.push(s);

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        printf("%d ", v);

        for (auto u : adj[v]) {
            if (visited[u] == 0) {
                visited[u] = 1;
                q.push(u);
            }
        }
    }
}

使用C语言编程实现一个有菜单的图的邻接矩阵和邻接表两种存储结构；

以下是使用C语言编程实现的有菜单的图的邻接矩阵和邻接表两种存储结构的代码，包括创建图、添加边、打印图等基本操作：

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

#define MAX_VERTEX_NUM 20

/* 存储结构 */
typedef struct {
    int vertex[MAX_VERTEX_NUM]; // 存储顶点
    int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储边
    int vertex_num; // 顶点数
    int edge_num; // 边数
} MatrixGraph;

typedef struct EdgeNode {
    int adjvex; // 邻接点下标
    struct EdgeNode *next; // 指向下一个邻接点
} EdgeNode;

typedef struct VertexNode {
    int data; // 顶点数据
    EdgeNode *first_edge; // 指向第一个邻接点
} VertexNode;

typedef struct {
    VertexNode vertex[MAX_VERTEX_NUM]; // 存储顶点和边
    int vertex_num; // 顶点数
    int edge_num; // 边数
} ListGraph;

/* 函数声明 */
void create_matrix_graph(MatrixGraph *g);
void create_list_graph(ListGraph *g);
void add_edge_matrix(MatrixGraph *g, int v1, int v2);
void add_edge_list(ListGraph *g, int v1, int v2);
void print_matrix_graph(MatrixGraph g);
void print_list_graph(ListGraph g);

int main() {
    int choice;
    MatrixGraph m_graph;
    ListGraph l_graph;

    while (1) {
        printf("1. 创建邻接矩阵图\n");
        printf("2. 创建邻接表图\n");
        printf("3. 退出\n");
        printf("请选择操作：");

        scanf("%d", &choice);
        switch (choice) {
            case 1:
                create_matrix_graph(&m_graph);
                print_matrix_graph(m_graph);
                break;
            case 2:
                create_list_graph(&l_graph);
                print_list_graph(l_graph);
                break;
            case 3:
                exit(0);
            default:
                printf("输入有误，请重新选择！\n");
                break;
        }
    }
}

/* 创建邻接矩阵图 */
void create_matrix_graph(MatrixGraph *g) {
    int i, j, v1, v2;

    printf("请输入顶点数和边数：");
    scanf("%d%d", &(g->vertex_num), &(g->edge_num));

    printf("请输入顶点信息：");
    for (i = 0; i < g->vertex_num; i++) {
        scanf("%d", &(g->vertex[i]));
    }

    /* 初始化邻接矩阵 */
    for (i = 0; i < g->vertex_num; i++) {
        for (j = 0; j < g->vertex_num; j++) {
            g->edge[i][j] = 0;
        }
    }

    printf("请输入边的信息：\n");
    for (i = 0; i < g->edge_num; i++) {
        printf("请输入第 %d 条边的两个顶点下标：", i + 1);
        scanf("%d%d", &v1, &v2);
        add_edge_matrix(g, v1, v2);
    }
}

/* 创建邻接表图 */
void create_list_graph(ListGraph *g) {
    int i, j, v1, v2;
    EdgeNode *e;

    printf("请输入顶点数和边数：");
    scanf("%d%d", &(g->vertex_num), &(g->edge_num));

    printf("请输入顶点信息：");
    for (i = 0; i < g->vertex_num; i++) {
        scanf("%d", &(g->vertex[i].data));
        g->vertex[i].first_edge = NULL;
    }

    printf("请输入边的信息：\n");
    for (i = 0; i < g->edge_num; i++) {
        printf("请输入第 %d 条边的两个顶点下标：", i + 1);
        scanf("%d%d", &v1, &v2);
        add_edge_list(g, v1, v2);
    }
}

/* 添加边到邻接矩阵 */
void add_edge_matrix(MatrixGraph *g, int v1, int v2) {
    g->edge[v1][v2] = 1;
    g->edge[v2][v1] = 1;
}

/* 添加边到邻接表 */
void add_edge_list(ListGraph *g, int v1, int v2) {
    EdgeNode *e;

    /* 添加 v2 到 v1 的边 */
    e = (EdgeNode *)malloc(sizeof(EdgeNode));
    e->adjvex = v2;
    e->next = g->vertex[v1].first_edge;
    g->vertex[v1].first_edge = e;

    /* 添加 v1 到 v2 的边 */
    e = (EdgeNode *)malloc(sizeof(EdgeNode));
    e->adjvex = v1;
    e->next = g->vertex[v2].first_edge;
    g->vertex[v2].first_edge = e;
}

/* 打印邻接矩阵图 */
void print_matrix_graph(MatrixGraph g) {
    int i, j;

    printf("图的邻接矩阵表示如下：\n");
    for (i = 0; i < g.vertex_num; i++) {
        for (j = 0; j < g.vertex_num; j++) {
            printf("%d ", g.edge[i][j]);
        }
        printf("\n");
    }
}

/* 打印邻接表图 */
void print_list_graph(ListGraph g) {
    int i;
    EdgeNode *e;

    printf("图的邻接表表示如下：\n");
    for (i = 0; i < g.vertex_num; i++) {
        printf("%d: ", g.vertex[i].data);
        e = g.vertex[i].first_edge;
        while (e != NULL) {
            printf("%d ", g.vertex[e->adjvex].data);
            e = e->next;
        }
        printf("\n");
    }
}

以上代码中，`create_matrix_graph()` 和 `create_list_graph()` 用来创建图，分别对应邻接矩阵和邻接表两种存储结构。`add_edge_matrix()` 和 `add_edge_list()` 用来添加边，分别对应邻接矩阵和邻接表两种存储结构。`print_matrix_graph()` 和 `print_list_graph()` 用来打印图，分别对应邻接矩阵和邻接表两种存储结构。在 `main()` 函数中，通过菜单实现了图的创建、添加边和打印等基本操作。