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

图的存储可以采用邻接矩阵或邻接表两种方式。

1. 邻接矩阵

邻接矩阵是一个二维数组，其中第 i 行第 j 列的元素表示第 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

2. 邻接表

邻接表是一个数组，每个元素是一个链表，链表中存储该顶点连向的其他顶点。

示意图：

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

深度优先搜索（DFS）和广度优先搜索（BFS）都是用来遍历图的算法。

1. 深度优先搜索

深度优先搜索从起点开始，尽可能深地访问每个顶点，直到无法继续深入，然后回溯到上一个顶点，继续访问其他顶点，直到所有顶点都被访问。

遍历序列：1 2 3 4

2. 广度优先搜索

广度优先搜索从起点开始，依次访问起点的所有邻居顶点，然后访问邻居的邻居，以此类推，直到所有顶点都被访问。

遍历序列：1 2 3 4

注：由于此处的图是无向图，因此深度优先搜索和广度优先搜索的遍历序列是相同的。如果是有向图，则可能不同。

相关问题

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

实现图的存储可以采用邻接矩阵或邻接表的方式，下面分别介绍。

1. 邻接矩阵存储

邻接矩阵是一个二维矩阵，其中每个元素表示两个顶点之间是否有边相连。如果顶点 i 和 j 之间有边相连，则邻接矩阵中的第 i 行第 j 列元素为 1，否则为 0。如果有权图，则用矩阵元素值表示权值。

以下是一个无向图的邻接矩阵存储示例：

   0  1  2  3  4
0  0  1  1  0  0
1  1  0  0  1  1
2  1  0  0  1  0
3  0  1  1  0  1
4  0  1  0  1  0

示意图如下：

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

2. 邻接表存储

邻接表是一个数组，每个数组元素对应一个顶点，其值为一个链表，链表中存储该顶点所连接的所有顶点。如果有权图，则链表节点还需存储权值。

以下是一个无向图的邻接表存储示例：

0 -> 1 -> 2 -> NULL
1 -> 0 -> 3 -> 4 -> NULL
2 -> 0 -> 3 -> NULL
3 -> 1 -> 2 -> 4 -> NULL
4 -> 1 -> 3 -> NULL

示意图如下：

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

接下来分别介绍深度优先搜索和广度优先搜索算法。

3. 深度优先搜索

深度优先搜索（Depth First Search，DFS）是一种遍历图的算法，它从某个顶点开始，沿着一条路径一直走到底，然后回溯到离起点最近的未访问过的顶点，继续沿着另一条路径走到底，直到所有顶点都被访问过。

深度优先搜索可以用递归或栈来实现。下面是用栈实现深度优先搜索的示例代码：

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

#define MAX_VERTEX_NUM 100  // 最大顶点数

// 邻接矩阵存储图
typedef struct {
    int vexs[MAX_VERTEX_NUM];  // 顶点数组
    int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  // 邻接矩阵
    int vexnum, arcnum;  // 顶点数、边数
} MGraph;

// 邻接表存储图
typedef struct ArcNode {
    int adjvex;  // 邻接点下标
    int weight;  // 边权值
    struct ArcNode *next;  // 下一个邻接点指针
} ArcNode;

typedef struct VNode {
    int data;  // 顶点数据
    ArcNode *first;  // 第一个邻接点指针
} VNode;

typedef struct {
    VNode adjlist[MAX_VERTEX_NUM];  // 邻接表头结点数组
    int vexnum, arcnum;  // 顶点数、边数
} ALGraph;

// 初始化邻接矩阵图
void initMGraph(MGraph *G) {
    int i, j, k, w;
    printf("请输入顶点数和边数：");
    scanf("%d %d", &G->vexnum, &G->arcnum);
    printf("请输入顶点信息（如：0 1 2 ...）：");
    for (i = 0; i < G->vexnum; i++) {
        scanf("%d", &G->vexs[i]);
    }
    for (i = 0; i < G->vexnum; i++) {
        for (j = 0; j < G->vexnum; j++) {
            G->edges[i][j] = 0;
        }
    }
    printf("请输入边信息（如：0 1 5 1 2 4 ...）：");
    for (k = 0; k < G->arcnum; k++) {
        scanf("%d %d %d", &i, &j, &w);
        G->edges[i][j] = w;
        G->edges[j][i] = w;  // 若为无向图，此行不需要
    }
}

// 初始化邻接表图
void initALGraph(ALGraph *G) {
    int i, j, k, w;
    ArcNode *p;
    printf("请输入顶点数和边数：");
    scanf("%d %d", &G->vexnum, &G->arcnum);
    printf("请输入顶点信息（如：0 1 2 ...）：");
    for (i = 0; i < G->vexnum; i++) {
        scanf("%d", &G->adjlist[i].data);
        G->adjlist[i].first = NULL;
    }
    printf("请输入边信息（如：0 1 5 1 2 4 ...）：");
    for (k = 0; k < G->arcnum; k++) {
        scanf("%d %d %d", &i, &j, &w);
        p = (ArcNode*) malloc(sizeof(ArcNode));
        p->adjvex = j;
        p->weight = w;
        p->next = G->adjlist[i].first;
        G->adjlist[i].first = p;
        p = (ArcNode*) malloc(sizeof(ArcNode));
        p->adjvex = i;
        p->weight = w;
        p->next = G->adjlist[j].first;
        G->adjlist[j].first = p;  // 若为有向图，此行不需要
    }
}

// 深度优先搜索
void DFS(MGraph G, int i, int *visited) {
    int j;
    visited[i] = 1;
    printf("%d ", G.vexs[i]);
    for (j = 0; j < G.vexnum; j++) {
        if (G.edges[i][j] && !visited[j]) {
            DFS(G, j, visited);
        }
    }
}

void DFSTraverse(MGraph G) {
    int i;
    int visited[MAX_VERTEX_NUM] = {0};
    printf("深度优先搜索序列：");
    for (i = 0; i < G.vexnum; i++) {
        if (!visited[i]) {
            DFS(G, i, visited);
        }
    }
    printf("\n");
}

// 深度优先搜索（邻接表）
void DFS(ALGraph G, int i, int *visited) {
    ArcNode *p;
    visited[i] = 1;
    printf("%d ", G.adjlist[i].data);
    p = G.adjlist[i].first;
    while (p) {
        if (!visited[p->adjvex]) {
            DFS(G, p->adjvex, visited);
        }
        p = p->next;
    }
}

void DFSTraverse(ALGraph G) {
    int i;
    int visited[MAX_VERTEX_NUM] = {0};
    printf("深度优先搜索序列：");
    for (i = 0; i < G.vexnum; i++) {
        if (!visited[i]) {
            DFS(G, i, visited);
        }
    }
    printf("\n");
}

4. 广度优先搜索

广度优先搜索（Breadth First Search，BFS）是一种遍历图的算法，它从某个顶点开始，先访问所有与该顶点相邻的顶点，然后依次访问这些相邻顶点的所有未访问过的相邻顶点，直到所有顶点都被访问过。

广度优先搜索可以用队列来实现。下面是用队列实现广度优先搜索的示例代码：

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

#define MAX_VERTEX_NUM 100  // 最大顶点数

// 邻接矩阵存储图
typedef struct {
    int vexs[MAX_VERTEX_NUM];  // 顶点数组
    int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  // 邻接矩阵
    int vexnum, arcnum;  // 顶点数、边数
} MGraph;

// 邻接表存储图
typedef struct ArcNode {
    int adjvex;  // 邻接点下标
    int weight;  // 边权值
    struct ArcNode *next;  // 下一个邻接点指针
} ArcNode;

typedef struct VNode {
    int data;  // 顶点数据
    ArcNode *first;  // 第一个邻接点指针
} VNode;

typedef struct {
    VNode adjlist[MAX_VERTEX_NUM];  // 邻接表头结点数组
    int vexnum, arcnum;  // 顶点数、边数
} ALGraph;

// 初始化邻接矩阵图
void initMGraph(MGraph *G) {
    int i, j, k, w;
    printf("请输入顶点数和边数：");
    scanf("%d %d", &G->vexnum, &G->arcnum);
    printf("请输入顶点信息（如：0 1 2 ...）：");
    for (i = 0; i < G->vexnum; i++) {
        scanf("%d", &G->vexs[i]);
    }
    for (i = 0; i < G->vexnum; i++) {
        for (j = 0; j < G->vexnum; j++) {
            G->edges[i][j] = 0;
        }
    }
    printf("请输入边信息（如：0 1 5 1 2 4 ...）：");
    for (k = 0; k < G->arcnum; k++) {
        scanf("%d %d %d", &i, &j, &w);
        G->edges[i][j] = w;
        G->edges[j][i] = w;  // 若为无向图，此行不需要
    }
}

// 初始化邻接表图
void initALGraph(ALGraph *G) {
    int i, j, k, w;
    ArcNode *p;
    printf("请输入顶点数和边数：");
    scanf("%d %d", &G->vexnum, &G->arcnum);
    printf("请输入顶点信息（如：0 1 2 ...）：");
    for (i = 0; i < G->vexnum; i++) {
        scanf("%d", &G->adjlist[i].data);
        G->adjlist[i].first = NULL;
    }
    printf("请输入边信息（如：0 1 5 1 2 4 ...）：");
    for (k = 0; k < G->arcnum; k++) {
        scanf("%d %d %d", &i, &j, &w);
        p = (ArcNode*) malloc(sizeof(ArcNode));
        p->adjvex = j;
        p->weight = w;
        p->next = G->adjlist[i].first;
        G->adjlist[i].first = p;
        p = (ArcNode*) malloc(sizeof(ArcNode));
        p->adjvex = i;
        p->weight = w;
        p->next = G->adjlist[j].first;
        G->adjlist[j].first = p;  // 若为有向图，此行不需要
    }
}

// 广度优先搜索
void BFS(MGraph G, int i, int *visited) {
    int j, front = 0, rear = 0;
    int queue[MAX_VERTEX_NUM];
    visited[i] = 1;
    printf("%d ", G.vexs[i]);
    queue[rear++] = i;
    while (front != rear) {
        i = queue[front++];
        for (j = 0; j < G.vexnum; j++) {
            if (G.edges[i][j] && !visited[j]) {
                visited[j] = 1;
                printf("%d ", G.vexs[j]);
                queue[rear++] = j;
            }
        }
    }
}

void BFSTraverse(MGraph G) {
    int i;
    int visited[MAX_VERTEX_NUM] = {0};
    printf("广度优先搜索序列：");
    for (i = 0; i < G.vexnum; i++) {
        if (!visited[i]) {
            BFS(G, i, visited);
        }
    }
    printf("\n");
}

// 广度优先搜索（邻接表）
void BFS(ALGraph G, int i, int *visited) {
    int j, front = 0, rear = 0;
    int queue[MAX_VERTEX_NUM];
    ArcNode *p;
    visited[i] = 1;
    printf("%d ", G.adjlist[i].data);
    queue[rear++] = i;
    while (front != rear) {
        i = queue[front++];
        p = G.adjlist[i].first;
        while (p) {
            j = p->adjvex;
            if (!visited[j]) {
                visited[j] = 1;
                printf("%d ", G.adjlist[j].data);
                queue[rear++] = j;
            }
            p = p->next;
        }
    }
}

void BFSTraverse(ALGraph G) {
    int i;
    int visited[MAX_VERTEX_NUM] = {0};
    printf("广度优先搜索序列：");
    for (i = 0; i < G.vexnum; i++) {
        if (!visited[i]) {
            BFS(G, i, visited);
        }
    }
    printf("\n");
}