用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");
}