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

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

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

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

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

相关问题

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语言

在邻接表存储结构中，我们可以采用一个一维数组和一个链表数组来表示图。其中，一维数组的每个元素表示一个顶点，链表数组则用于表示该顶点所连向的其他顶点。因此，我们可以定义如下结构体：

typedef struct EdgeNode{
    int adjvex; // 邻接点域，存储该顶点对应的下标
    struct EdgeNode *next; // 链域，指向下一个邻接点
}EdgeNode;

typedef struct VertexNode{
    int data; // 顶点域，存储顶点信息
    EdgeNode *first_edge; // 边表头指针
}VertexNode, AdjList[MAX_VERTEX_NUM];

typedef struct{
    AdjList adj_list; // 图的邻接表
    int vex_num, edge_num; // 图的当前顶点数和边数
}GraphAdjList;

建立图的邻接表存储结构需要先创建一个空表，然后再逐个插入各个顶点及其相邻顶点。具体操作如下：

void CreateGraph(GraphAdjList *G){
    int i, j, k;
    EdgeNode *e;

    printf("请输入图的顶点数和边数：");
    scanf("%d %d", &G->vex_num, &G->edge_num);

    printf("请输入每个顶点的值：");
    for(i=0; i<G->vex_num; i++){
        scanf("%d", &G->adj_list[i].data);
        G->adj_list[i].first_edge = NULL; // 将边表头指针初始化为空
    }

    printf("请输入每条边依附的两个顶点序号：\n");
    for(k=0; k<G->edge_num; k++){
        scanf("%d %d", &i, &j);

        e = (EdgeNode*)malloc(sizeof(EdgeNode));
        e->adjvex = j;
        e->next = G->adj_list[i].first_edge;
        G->adj_list[i].first_edge = e;

        e = (EdgeNode*)malloc(sizeof(EdgeNode));
        e->adjvex = i;
        e->next = G->adj_list[j].first_edge;
        G->adj_list[j].first_edge = e;
    }
}

至于深度优先遍历和广度优先遍历的实现，可以参考以下代码：

int visited[MAX_VERTEX_NUM];

void DFS(GraphAdjList G, int v){
    EdgeNode *e;

    visited[v] = 1;
    printf("%d ", G.adj_list[v].data);

    e = G.adj_list[v].first_edge;
    while(e){
        if(!visited[e->adjvex]){
            DFS(G, e->adjvex);
        }
        e = e->next;
    }
}

void DFSTraverse(GraphAdjList G){
    int i;

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

    for(i=0; i<G.vex_num; i++){
        if(!visited[i]){
            DFS(G, i);
        }
    }
}

void BFSTraverse(GraphAdjList G){
    int i, j;
    EdgeNode *e;
    Queue Q;

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

    InitQueue(&Q);
    for(i=0; i<G.vex_num; i++){
        if(!visited[i]){
            visited[i] = 1;
            printf("%d ", G.adj_list[i].data);
            EnQueue(&Q, i);
            while(!QueueEmpty(Q)){
                DeQueue(&Q, &j);
                e = G.adj_list[j].first_edge;
                while(e){
                    if(!visited[e->adjvex]){
                        visited[e->adjvex] = 1;
                        printf("%d ", G.adj_list[e->adjvex].data);
                        EnQueue(&Q, e->adjvex);
                    }
                    e = e->next;
                }
            }
        }
    }
}