输入无向图的顶点数、边数及各条边的顶点对，建立用邻接表表示的无向图。对图进行深度优先搜索和广度优先搜索遍历，并分别输出其遍历序列

好的，我知道了。这是一个关于图的算法问题。

首先，我需要确认一下你的输入格式。你可以按照以下格式输入无向图的顶点数、边数及各条边的顶点对：

6 7
0 1
0 2
1 3
2 3
2 4
3 4
4 5

这表示该无向图有6个顶点、7条边，其中0和1、0和2、1和3、2和3、2和4、3和4、4和5相连。

然后，我会使用邻接表来表示这个无向图，并进行深度优先搜索和广度优先搜索遍历。最后，分别输出它们的遍历序列。

以下是代码实现：

相关问题

C语言输入无向图的顶点数、边数及各条边的顶点对，建立用邻接表表示的无向图。 对图进行深度优先搜索和广度优先搜索遍历，并分别输出其遍历序列

好的，以下是C语言实现：

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

#define MAX_VERTEX_NUM 100 // 最大顶点数

// 邻接表节点结构体
typedef struct ArcNode {
    int adjvex;             // 该边所指向的顶点的位置
    struct ArcNode *next;   // 指向下一条边的指针
} ArcNode;

// 顶点表结构体
typedef struct VertexNode {
    int data;               // 顶点信息
    ArcNode *first;         // 指向第一条依附该顶点的边的指针
} VertexNode;

// 邻接表结构体
typedef struct {
    VertexNode vertex[MAX_VERTEX_NUM];  // 顶点表
    int vexnum, arcnum;                 // 图的当前顶点数和边数
} AdjList;

// 初始化邻接表
void InitAdjList(AdjList *G) {
    int i;
    G->vexnum = G->arcnum = 0;
    for (i = 0; i < MAX_VERTEX_NUM; i++) {
        G->vertex[i].data = 0;
        G->vertex[i].first = NULL;
    }
}

// 添加边
void AddEdge(AdjList *G, int u, int v) {
    ArcNode *p;
    p = (ArcNode *)malloc(sizeof(ArcNode));
    p->adjvex = v;
    p->next = G->vertex[u].first;
    G->vertex[u].first = p;
}

// 深度优先搜索遍历
void DFS(AdjList *G, int v, int *visited) {
    ArcNode *p;
    printf("%d ", v);
    visited[v] = 1;
    p = G->vertex[v].first;
    while (p != NULL) {
        if (!visited[p->adjvex]) {
            DFS(G, p->adjvex, visited);
        }
        p = p->next;
    }
}

// 广度优先搜索遍历
void BFS(AdjList *G, int v, int *visited) {
    int queue[MAX_VERTEX_NUM], front = 0, rear = 0;
    ArcNode *p;
    printf("%d ", v);
    visited[v] = 1;
    queue[rear++] = v;
    while (front < rear) {
        v = queue[front++];
        p = G->vertex[v].first;
        while (p != NULL) {
            if (!visited[p->adjvex]) {
                printf("%d ", p->adjvex);
                visited[p->adjvex] = 1;
                queue[rear++] = p->adjvex;
            }
            p = p->next;
        }
    }
}

int main() {
    AdjList G;
    int visited[MAX_VERTEX_NUM] = {0};  // 初始化为0
    int i, u, v;

    // 初始化邻接表
    InitAdjList(&G);

    // 输入无向图的顶点数和边数
    scanf("%d %d", &G.vexnum, &G.arcnum);

    // 输入各条边的顶点对，建立邻接表
    for (i = 0; i < G.arcnum; i++) {
        scanf("%d %d", &u, &v);
        AddEdge(&G, u, v);
        AddEdge(&G, v, u);
    }

    // 输出邻接表
    for (i = 0; i < G.vexnum; i++) {
        printf("%d: ", i);
        ArcNode *p = G.vertex[i].first;
        while (p != NULL) {
            printf("%d ", p->adjvex);
            p = p->next;
        }
        printf("\n");
    }

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

    // 广度优先搜索遍历
    for (i = 0; i < G.vexnum; i++) {
        visited[i] = 0;  // 重置visited数组
    }
    printf("BFS: ");
    for (i = 0; i < G.vexnum; i++) {
        if (!visited[i]) {
            BFS(&G, i, visited);
        }
    }
    printf("\n");

    return 0;
}

代码中，`AdjList`代表邻接表，`ArcNode`代表邻接表节点，`VertexNode`代表顶点表节点。`InitAdjList`函数用于初始化邻接表，`AddEdge`函数用于添加边，`DFS`函数和`BFS`函数分别用于深度优先搜索遍历和广度优先搜索遍历。在`main`函数中，我们先输入无向图的顶点数和边数，再输入各条边的顶点对，建立邻接表。然后，我们输出邻接表，并进行深度优先搜索遍历和广度优先搜索遍历，并输出它们的遍历序列。

c语言实现输入无向图的顶点数、边数及各条边的顶点对，建立用邻接表表示的无向图。 并对图进行深度优先搜索和广度优先搜索遍历，并分别输出其遍历序列。

以下是C语言实现输入无向图的顶点数、边数及各条边的顶点对，建立用邻接表表示的无向图。并对图进行深度优先搜索和广度优先搜索遍历，并分别输出其遍历序列的代码：

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

#define MAX_VERTEX_NUM 50 //最大顶点数

//邻接表节点结构体
typedef struct node{
    int adjvex; //邻接点在顶点数组中的下标
    struct node *next; //指向下一邻接点的指针
}EdgeNode;

//顶点表结构体
typedef struct{
    char vertex; //顶点值
    EdgeNode *firstedge; //指向第一个邻接点的指针
}VertexNode;

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

//初始化邻接表
void InitGraph(GraphAdjList *G);

//添加边
void AddEdge(GraphAdjList *G, int u, int v);

//深度优先搜索遍历
void DFS(GraphAdjList G, int v, int visited[]);

//深度优先搜索
void DFSTraverse(GraphAdjList G);

//广度优先搜索遍历
void BFS(GraphAdjList G, int v, int visited[], int queue[], int *head, int *tail);

//广度优先搜索
void BFSTraverse(GraphAdjList G);

int main(){
    GraphAdjList G;
    InitGraph(&G); //初始化邻接表
    int n, m, i, u, v;
    printf("请输入顶点数和边数：");
    scanf("%d%d", &n, &m);
    G.vertexnum = n;
    G.edgenum = m;
    getchar();
    for(i=0; i<n; i++){
        printf("请输入第%d个顶点的值：", i+1);
        scanf("%c", &G.adjlist[i].vertex);
        G.adjlist[i].firstedge = NULL;
        getchar();
    }
    for(i=0; i<m; i++){
        printf("请输入第%d条边的两个顶点下标：", i+1);
        scanf("%d%d", &u, &v);
        AddEdge(&G, u-1, v-1);
        AddEdge(&G, v-1, u-1);
    }
    printf("深度优先搜索遍历序列：");
    DFSTraverse(G);
    printf("\n广度优先搜索遍历序列：");
    BFSTraverse(G);
    return 0;
}

//初始化邻接表
void InitGraph(GraphAdjList *G){
    int i;
    for(i=0; i<MAX_VERTEX_NUM; i++){
        G->adjlist[i].vertex = ' ';
        G->adjlist[i].firstedge = NULL;
    }
}

//添加边
void AddEdge(GraphAdjList *G, int u, int v){
    EdgeNode *e = (EdgeNode*)malloc(sizeof(EdgeNode));
    e->adjvex = v;
    e->next = G->adjlist[u].firstedge;
    G->adjlist[u].firstedge = e;
}

//深度优先搜索遍历
void DFS(GraphAdjList G, int v, int visited[]){
    visited[v] = 1; //标记为已访问
    printf("%c ", G.adjlist[v].vertex); //输出遍历到的顶点值
    EdgeNode *e = G.adjlist[v].firstedge;
    while(e){
        if(!visited[e->adjvex]){ //若该邻接点未被访问，则递归搜索它
            DFS(G, e->adjvex, visited);
        }
        e = e->next;
    }
}

//深度优先搜索
void DFSTraverse(GraphAdjList G){
    int visited[MAX_VERTEX_NUM] = {0}; //初始化所有顶点均未被访问
    int i;
    for(i=0; i<G.vertexnum; i++){
        if(!visited[i]){ //若该顶点未被访问，则从该顶点开始深度优先搜索
            DFS(G, i, visited);
        }
    }
}

//广度优先搜索遍历
void BFS(GraphAdjList G, int v, int visited[], int queue[], int *head, int *tail){
    visited[v] = 1; //标记为已访问
    printf("%c ", G.adjlist[v].vertex); //输出遍历到的顶点值
    queue[(*tail)++] = v; //将该顶点入队
    EdgeNode *e;
    while((*head) < (*tail)){ //当队列非空时
        e = G.adjlist[queue[(*head)++]].firstedge;
        while(e){
            if(!visited[e->adjvex]){ //若该邻接点未被访问，则标记为已访问并入队
                visited[e->adjvex] = 1;
                printf("%c ", G.adjlist[e->adjvex].vertex);
                queue[(*tail)++] = e->adjvex;
            }
            e = e->next;
        }
    }
}

//广度优先搜索
void BFSTraverse(GraphAdjList G){
    int visited[MAX_VERTEX_NUM] = {0}; //初始化所有顶点均未被访问
    int queue[MAX_VERTEX_NUM], head=0, tail=0; //定义队列
    int i;
    for(i=0; i<G.vertexnum; i++){
        if(!visited[i]){ //若该顶点未被访问，则从该顶点开始广度优先搜索
            BFS(G, i, visited, queue, &head, &tail);
        }
    }
}

其中，深度优先搜索遍历的时间复杂度为O(|V|+|E|)，广度优先搜索遍历的时间复杂度为O(|V|+|E|)。其中|V|为顶点数，|E|为边数。