建立图的邻接表存储并在此基础上实现图的深度优先遍历和广度优先遍历。

邻接表是一种图的存储方式，它将每个顶点的所有邻接点存储在一个链表中。这样，我们可以通过遍历链表来访问每个顶点的邻接点。

在邻接表的基础上，我们可以实现图的深度优先遍历和广度优先遍历。深度优先遍历是一种递归的方式，从一个顶点开始，沿着一条路径尽可能深地访问图中的顶点，直到到达一个没有未访问邻接点的顶点。然后回溯到前一个顶点，继续访问其他未访问的邻接点，直到所有顶点都被访问。

广度优先遍历是一种迭代的方式，从一个顶点开始，先访问它的所有邻接点，然后访问它们的邻接点，以此类推，直到所有顶点都被访问。在广度优先遍历中，我们使用一个队列来存储待访问的顶点，每次从队列中取出一个顶点进行访问。

总之，邻接表是一种常用的图的存储方式，可以方便地实现图的深度优先遍历和广度优先遍历。

相关问题

c语言实现 建立图的邻接表存储并在此基础上实现图的深度优先遍历和广度优先遍历。

以下是C语言实现建立图的邻接表存储，并在此基础上实现图的深度优先遍历和广度优先遍历的示例代码。

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

#define MAX_VERTEX_NUM 20 // 最大顶点数

// 边表节点
typedef struct EdgeNode{
    int adjvex; // 邻接点序号
    struct EdgeNode *next; // 指向下一个邻接点的指针
}EdgeNode;

// 顶点表节点
typedef struct VertexNode{
    char data; // 顶点信息
    EdgeNode *firstedge; // 指向第一个邻接点的指针
}VertexNode;

// 图
typedef struct{
    VertexNode vertex[MAX_VERTEX_NUM]; // 顶点表
    int vexnum; // 顶点数
    int edgenum; // 边数
}Graph;

// 建立图的邻接表存储
void CreateGraph(Graph *G){
    printf("请输入顶点数和边数：");
    scanf("%d%d", &G->vexnum, &G->edgenum);
    getchar(); // 吸收换行符

    // 输入顶点数据
    printf("请输入顶点的信息：");
    for(int i = 0; i < G->vexnum; i++){
        scanf("%c", &G->vertex[i].data);
        G->vertex[i].firstedge = NULL;
        getchar(); // 吸收换行符
    }

    // 输入边的信息
    printf("请输入每条边的两个顶点的序号：");
    for(int i = 0; i < G->edgenum; i++){
        int v1, v2;
        scanf("%d%d", &v1, &v2);
        EdgeNode *e1 = (EdgeNode*)malloc(sizeof(EdgeNode));
        e1->adjvex = v2;
        e1->next = G->vertex[v1].firstedge;
        G->vertex[v1].firstedge = e1;

        EdgeNode *e2 = (EdgeNode*)malloc(sizeof(EdgeNode));
        e2->adjvex = v1;
        e2->next = G->vertex[v2].firstedge;
        G->vertex[v2].firstedge = e2;
    }
}

// 深度优先遍历
void DFS(Graph G, int v, int visited[]){
    visited[v] = 1;
    printf("%c ", G.vertex[v].data);
    EdgeNode *p = G.vertex[v].firstedge;
    while(p != NULL){
        int w = p->adjvex;
        if(!visited[w]){
            DFS(G, w, visited);
        }
        p = p->next;
    }
}

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

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

    while(front < rear){
        int w = queue[front++]; // 出队
        EdgeNode *p = G.vertex[w].firstedge;
        while(p != NULL){
            int u = p->adjvex;
            if(!visited[u]){
                visited[u] = 1;
                printf("%c ", G.vertex[u].data);
                queue[rear++] = u; // 入队
            }
            p = p->next;
        }
    }
}

int main(){
    Graph G;
    CreateGraph(&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; // 重置访问标记数组
    }
    for(int i = 0; i < G.vexnum; i++){
        if(!visited[i]){
            BFS(G, i, visited);
        }
    }

    return 0;
}

在上述代码中，我们创建了三个数据结构：边表节点、顶点表节点和图。其中，边表节点包含了邻接点的序号和指向下一个邻接点的指针；顶点表节点包含了顶点的信息和指向第一个邻接点的指针；图则由顶点表构成，包含了顶点数和边数。

在建立图的邻接表存储后，我们实现了图的深度优先遍历和广度优先遍历。具体而言，深度优先遍历使用递归实现，广度优先遍历使用队列实现。在遍历过程中，使用访问标记数组来避免重复访问。

以上就是C语言实现建立图的邻接表存储并实现深度优先遍历和广度优先遍历的示例代码。

请用C语言:建立带权值无向图的邻接表存储并在此基础上实现图的深度优先遍历和广度优先遍历。

以下是建立带权值无向图的邻接表存储的C语言代码：

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

#define MAX_VERTEX_NUM 20  // 最大顶点数

// 边表节点
typedef struct EdgeNode {
    int adjvex;  // 邻接点编号
    int weight;  // 权值
    struct EdgeNode* next;  // 指向下一个邻接点的指针
} EdgeNode;

// 顶点表节点
typedef struct VertexNode {
    int data;  // 顶点编号
    EdgeNode* firstedge;  // 指向第一个邻接点的指针
} VertexNode;

// 图结构体
typedef struct {
    VertexNode adjlist[MAX_VERTEX_NUM];  // 邻接表
    int vexnum, edgenum;  // 顶点数和边数
} Graph;

// 创建邻接表存储的带权值无向图
void CreateGraph(Graph* G) {
    printf("输入顶点数和边数（用空格隔开）：");
    scanf("%d %d", &G->vexnum, &G->edgenum);

    // 初始化邻接表
    for (int i = 0; i < G->vexnum; i++) {
        G->adjlist[i].data = i;
        G->adjlist[i].firstedge = NULL;
    }

    // 添加边
    int v1, v2, w;
    EdgeNode* e1, * e2;
    for (int i = 0; i < G->edgenum; i++) {
        printf("输入第%d条边的两个顶点和权值（用空格隔开）：", i + 1);
        scanf("%d %d %d", &v1, &v2, &w);

        // 添加边<v1, v2>
        e1 = (EdgeNode*)malloc(sizeof(EdgeNode));
        e1->adjvex = v2;
        e1->weight = w;
        e1->next = G->adjlist[v1].firstedge;
        G->adjlist[v1].firstedge = e1;

        // 添加边<v2, v1>
        e2 = (EdgeNode*)malloc(sizeof(EdgeNode));
        e2->adjvex = v1;
        e2->weight = w;
        e2->next = G->adjlist[v2].firstedge;
        G->adjlist[v2].firstedge = e2;
    }
}

// 深度优先遍历
void DFS(Graph* G, int v, int visited[]) {
    printf("%d ", v);  // 访问顶点v
    visited[v] = 1;  // 标记顶点v已访问

    EdgeNode* p = G->adjlist[v].firstedge;
    while (p != NULL) {
        if (visited[p->adjvex] == 0) {  // 如果邻接点未被访问
            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;  // 队列头和尾指针
    int w;

    printf("%d ", v);  // 访问顶点v
    visited[v] = 1;  // 标记顶点v已访问
    queue[rear++] = v;  // 将顶点v入队

    while (front != rear) {  // 队列不为空时
        w = queue[front++];  // 出队一个顶点w

        EdgeNode* p = G->adjlist[w].firstedge;
        while (p != NULL) {
            if (visited[p->adjvex] == 0) {  // 如果邻接点未被访问
                printf("%d ", p->adjvex);  // 访问邻接点
                visited[p->adjvex] = 1;  // 标记邻接点已访问
                queue[rear++] = p->adjvex;  // 将邻接点入队
            }
            p = p->next;
        }
    }
}

int main() {
    Graph G;
    CreateGraph(&G);

    // 初始化visited数组
    int visited[MAX_VERTEX_NUM] = { 0 };

    printf("深度优先遍历结果：");
    DFS(&G, 0, visited);
    printf("\n");

    // 重新初始化visited数组
    for (int i = 0; i < G.vexnum; i++) {
        visited[i] = 0;
    }

    printf("广度优先遍历结果：");
    BFS(&G, 0, visited);
    printf("\n");

    return 0;
}

在该代码中，我们使用了邻接表来存储带权值无向图，并实现了图的深度优先遍历和广度优先遍历。在深度优先遍历中，我们使用递归的方式访问每个顶点的邻接点。在广度优先遍历中，我们使用队列来存储待访问的顶点，并按照广度优先的顺序依次访问它们的邻接点。