数据结构：对于图1所示的无向图： 1、编写一个函数让用户输入这张图，用邻接表存储。 2、编写函数实现此图的深度优先搜索遍历。 3、编程实现循环队列，编写初始化、创建、入队、出队等算法。 4、利用循环队列对图1实现广度优先搜索遍历。

1、输入无向图的邻接表存储：

#include <iostream>
using namespace std;

const int MAX_VERTEX_NUM = 20;

typedef struct ArcNode {
    int adjvex;  // 邻接点编号
    ArcNode* nextarc;  // 指向下一个邻接点的指针
} ArcNode;

typedef struct VNode {
    int data;  // 顶点数据
    ArcNode* firstarc;  // 指向第一个邻接点的指针
} AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices;  // 存储邻接表的一维数组
    int vexnum, arcnum;  // 顶点数和边数
} ALGraph;

void CreateGraph(ALGraph& G) {
    cout << "请输入顶点数和边数：" << endl;
    cin >> G.vexnum >> G.arcnum;
    cout << "请输入顶点数据：" << endl;
    for (int i = 0; i < G.vexnum; i++) {
        cin >> G.vertices[i].data;
        G.vertices[i].firstarc = nullptr;
    }
    cout << "请输入边的信息：" << endl;
    for (int k = 0; k < G.arcnum; k++) {
        int i, j;
        cout << "请输入边(vi, vj)的顶点序号：";
        cin >> i >> j;
        ArcNode* p = new ArcNode;
        p->adjvex = j;
        p->nextarc = G.vertices[i].firstarc;
        G.vertices[i].firstarc = p;
        p = new ArcNode;
        p->adjvex = i;
        p->nextarc = G.vertices[j].firstarc;
        G.vertices[j].firstarc = p;
    }
}

2、深度优先搜索遍历：

bool visited[MAX_VERTEX_NUM];  // 用于记录顶点是否被访问过

void DFS(ALGraph G, int v) {
    visited[v] = true;
    cout << G.vertices[v].data << " ";
    ArcNode* p = G.vertices[v].firstarc;
    while (p != nullptr) {
        int w = p->adjvex;
        if (!visited[w]) {
            DFS(G, w);
        }
        p = p->nextarc;
    }
}

void DFSTraverse(ALGraph G) {
    for (int i = 0; i < G.vexnum; i++) {
        visited[i] = false;
    }
    for (int i = 0; i < G.vexnum; i++) {
        if (!visited[i]) {
            DFS(G, i);
        }
    }
}

3、循环队列的实现：

typedef struct {
    int* dase;  // 存储队列元素的数组
    int front;  // 队头指针
    int rear;  // 队尾指针
} SqQueue;

void InitQueue(SqQueue& Q, int n) {
    Q.dase = new int[n];
    Q.front = Q.rear = 0;
}

void EnQueue(SqQueue& Q, int x) {
    Q.dase[Q.rear] = x;
    Q.rear = (Q.rear + 1) % MAX_VERTEX_NUM;
}

int DeQueue(SqQueue& Q) {
    int x = Q.dase[Q.front];
    Q.front = (Q.front + 1) % MAX_VERTEX_NUM;
    return x;
}

bool QueueEmpty(SqQueue Q) {
    return Q.front == Q.rear;
}

4、广度优先搜索遍历：

void BFSTraverse(ALGraph G) {
    for (int i = 0; i < G.vexnum; i++) {
        visited[i] = false;
    }
    SqQueue Q;
    InitQueue(Q, MAX_VERTEX_NUM);
    for (int i = 0; i < G.vexnum; i++) {
        if (!visited[i]) {
            visited[i] = true;
            cout << G.vertices[i].data << " ";
            EnQueue(Q, i);
            while (!QueueEmpty(Q)) {
                int v = DeQueue(Q);
                ArcNode* p = G.vertices[v].firstarc;
                while (p != nullptr) {
                    int w = p->adjvex;
                    if (!visited[w]) {
                        visited[w] = true;
                        cout << G.vertices[w].data << " ";
                        EnQueue(Q, w);
                    }
                    p = p->nextarc;
                }
            }
        }
    }
}