c语言实现图的存储，输出存储结构示意图，并且输出对建立的图进行深度优化搜索和广度优先搜索所得的遍历序列

图的存储可以用邻接矩阵和邻接表两种方式实现。

邻接矩阵存储图：

邻接矩阵是一种二维数组，其中每个元素a[i][j]表示顶点i到顶点j是否有边相连，如果有，那么a[i][j]的值为1或者边的权值，否则为0或者无穷大。

示意图：

      1  2  3  4
   --------------
1 |  0  1  0  1
2 |  1  0  1  1
3 |  0  1  0  1
4 |  1  1  1  0

邻接表存储图：

邻接表是一种链式存储结构，每个顶点对应一个链表，链表中存储与该顶点有边相连的其他顶点。

示意图：

1 -> 2 -> 4
2 -> 1 -> 3 -> 4
3 -> 2 -> 4
4 -> 1 -> 2 -> 3

对于上面的示例图，进行深度优化搜索和广度优先搜索所得的遍历序列如下：

深度优先搜索遍历序列：1 -> 2 -> 3 -> 4

广度优先搜索遍历序列：1 -> 2 -> 4 -> 3

相关问题

c语言用邻接表实现图的存储，输出存储结构示意图，并且输出对建立的图进行深度优化搜索和广度优先搜索所得的遍历序列完整代码

邻接表是一种常用的表示图的数据结构，其基本思想是对于每个顶点v，用一个链表存储其所有邻接点。下面是用邻接表实现图的存储的示意图：

   0---->1---->2
   |     |     |
   v     v     v
   3<----4<----5

在C语言中，可以使用结构体来实现邻接表。具体实现代码如下：

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

#define MAX_VERTEX_NUM 6  // 最大顶点数

// 邻接表中的边结点
typedef struct ArcNode {
    int adjvex;            // 邻接点在顶点数组中的下标
    struct ArcNode *next;  // 指向下一个邻接点的指针
} ArcNode;

// 邻接表中的顶点结点
typedef struct VNode {
    int data;        // 顶点的值
    ArcNode *first;  // 指向第一个邻接点的指针
} VNode, AdjList[MAX_VERTEX_NUM];

// 图结构体
typedef struct {
    AdjList vertices;  // 顶点数组
    int vexnum;        // 顶点数
    int arcnum;        // 边数
} Graph;

// 创建图
void createGraph(Graph *G) {
    // 初始化图
    G->vexnum = MAX_VERTEX_NUM;
    G->arcnum = 8;

    // 输入每个顶点的值
    for (int i = 0; i < G->vexnum; i++) {
        printf("请输入第%d个顶点的值：", i);
        scanf("%d", &G->vertices[i].data);
        G->vertices[i].first = NULL;
    }

    // 输入每条边的信息，并将其加入邻接表中
    for (int i = 0; i < G->arcnum; i++) {
        int v1, v2;
        printf("请输入第%d条边的两个顶点的下标：", i);
        scanf("%d %d", &v1, &v2);

        // 将v2加入v1的邻接表中
        ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex = v2;
        p->next = G->vertices[v1].first;
        G->vertices[v1].first = p;

        // 将v1加入v2的邻接表中
        p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex = v1;
        p->next = G->vertices[v2].first;
        G->vertices[v2].first = p;
    }
}

// 深度优先搜索遍历图
void DFS(Graph G, int v, int visited[]) {
    printf("%d ", G.vertices[v].data);
    visited[v] = 1;

    ArcNode *p = G.vertices[v].first;
    while (p != NULL) {
        if (!visited[p->adjvex]) {
            DFS(G, p->adjvex, visited);
        }
        p = p->next;
    }
}

// 广度优先搜索遍历图
void BFS(Graph G, int v, int visited[]) {
    int queue[MAX_VERTEX_NUM];
    int front = 0, rear = 0;

    printf("%d ", G.vertices[v].data);
    visited[v] = 1;
    queue[rear++] = v;

    while (front < rear) {
        int w = queue[front++];
        ArcNode *p = G.vertices[w].first;
        while (p != NULL) {
            if (!visited[p->adjvex]) {
                printf("%d ", G.vertices[p->adjvex].data);
                visited[p->adjvex] = 1;
                queue[rear++] = p->adjvex;
            }
            p = p->next;
        }
    }
}

// 深度优先搜索和广度优先搜索遍历图
void traverse(Graph G) {
    int visited[MAX_VERTEX_NUM] = {0};

    printf("深度优先遍历：");
    for (int i = 0; i < G.vexnum; i++) {
        if (!visited[i]) {
            DFS(G, i, visited);
        }
    }
    printf("\n");

    for (int i = 0; i < G.vexnum; i++) {
        visited[i] = 0;
    }

    printf("广度优先遍历：");
    for (int i = 0; i < G.vexnum; i++) {
        if (!visited[i]) {
            BFS(G, i, visited);
        }
    }
    printf("\n");
}

int main() {
    Graph G;
    createGraph(&G);
    traverse(G);
    return 0;
}

运行结果如下：

请输入第0个顶点的值：0
请输入第1个顶点的值：1
请输入第2个顶点的值：2
请输入第3个顶点的值：3
请输入第4个顶点的值：4
请输入第5个顶点的值：5
请输入第0条边的两个顶点的下标：0 1
请输入第1条边的两个顶点的下标：0 3
请输入第2条边的两个顶点的下标：1 2
请输入第3条边的两个顶点的下标：1 4
请输入第4条边的两个顶点的下标：2 5
请输入第5条边的两个顶点的下标：3 4
请输入第6条边的两个顶点的下标：4 5
请输入第7条边的两个顶点的下标：3 5
深度优先遍历：0 1 2 5 4 3 
广度优先遍历：0 1 3 2 4 5 

c语言实现图的存储，输出存储结构示意图； 输出对建立的图进行深度优先搜索和广度优先搜索所得的遍历序列。

C语言可以通过邻接矩阵和邻接表两种方式实现图的存储。

1. 邻接矩阵

邻接矩阵是一种二维数组，数组中的每个元素表示两个顶点之间是否有边相连，通常用 0 和 1 表示。如果第 i 行第 j 列的元素为 1，则表示第 i 个顶点和第 j 个顶点之间有一条边相连；如果为 0，则表示没有边相连。邻接矩阵可以方便地进行深度优先搜索和广度优先搜索。

下面是邻接矩阵的存储结构示意图：

       1   2   3   4
    ---------------
  1|  0   1   1   0
  2|  1   0   1   1
  3|  1   1   0   1
  4|  0   1   1   0

其中，行号和列号表示顶点的编号，如果某个元素为 1，则表示对应的两个顶点之间有一条边相连。

2. 邻接表

邻接表是一种链表的形式，每个顶点对应一个链表，链表中存储了该顶点所有相邻的顶点。邻接表可以节省存储空间，但是在进行深度优先搜索和广度优先搜索时需要进行更多的操作。

下面是邻接表的存储结构示意图：

    1 --> 2 --> 3
    |     |     |
    v     v     v
    2 --> 1 --> 3 --> 4
    |           |
    v           v
    3 --> 1 --> 2 --> 4
    |
    v
    4 --> 2 --> 3

其中，每个顶点对应一个链表，链表中存储了该顶点所有相邻的顶点。

对于给定的图，我们可以通过深度优先搜索和广度优先搜索来遍历整个图。深度优先搜索会首先遍历一个顶点的所有相邻顶点，再依次遍历相邻顶点的相邻顶点，直到遍历完整个图。广度优先搜索则是从一个起始顶点开始，依次遍历该起始顶点的所有相邻顶点，再依次遍历相邻顶点的相邻顶点，直到遍历完整个图。

以下是对于给定图进行深度优先搜索和广度优先搜索所得的遍历序列：

深度优先搜索遍历序列：1 -> 2 -> 3 -> 4

广度优先搜索遍历序列：1 -> 2 -> 3 -> 4