建立无向图邻接表存储结构，输出深度和宽度优先遍历顶点访问次序。

建立无向图邻接表存储结构，可以使用链表来表示每个顶点的邻接点。对于每个顶点，我们可以用一个链表来存储它的邻接点，这个链表的头结点就是该顶点本身。

深度优先遍历可以使用递归或者栈来实现。从起始顶点开始，首先访问它的一个邻接点，然后再访问这个邻接点的一个邻接点，以此类推，直到访问完所有的顶点。在访问每个顶点时，我们可以记录下它的访问次序。

宽度优先遍历可以使用队列来实现。从起始顶点开始，首先访问它的所有邻接点，然后再访问这些邻接点的所有邻接点，以此类推，直到访问完所有的顶点。在访问每个顶点时，我们可以记录下它的访问次序。

无论是深度优先遍历还是宽度优先遍历，都需要遍历所有的顶点，因此时间复杂度都是O(V+E)，其中V是顶点数，E是边数。

相关问题

建立无向图邻接表存储结构，输出深度和宽度优先遍历顶点访问次序。C语言完整代码

在C语言中，我们可以使用邻接表来存储无向图，并分别实现深度优先搜索（DFS）和广度优先搜索（BFS）。这里给出的是基本的代码框架，你需要根据实际的顶点数（`vertices`）和边数填充相应的邻接列表：

首先，我们定义一个简单的结构体表示节点：

#include <stdbool.h>
#include <stdio.h>

#define MAX_VERTICES 100

typedef struct {
    int vertex;
    bool visited; // 标记是否已被访问
    struct Node* adj; // 指向邻接节点的指针
} Node;

// 创建邻接表表示无向图
void createAdjacencyList(Node* vertices[], int edges[]) {
    for (int i = 0; i < MAX_VERTICES; i++) {
        vertices[i].visited = false;
        vertices[i].adj = NULL;
    }
    // 这里假设edges数组是一个二维数组，存储了每条边的两端节点索引
    for (int i = 0; i < edges.length; i += 2) {
        int u = edges[i];
        int v = edges[i + 1];
        vertices[u].adj = &vertices[v];
        vertices[v].adj = &vertices[u]; // 无向图
    }
}

接下来，我们实现DFS和BFS的遍历：

void dfs(Node* start, char (*print)(int)) {
    stack<Node*> s;
    s.push(start);
    while (!s.empty()) {
        Node* node = s.top();
        s.pop();
        print(node->vertex); // 访问当前节点
        if (node->adj != NULL) { // 遍历相邻节点
            for (Node* adj : *node->adj) {
                if (!adj->visited) {
                    adj->visited = true;
                    s.push(adj);
                }
            }
        }
    }
}

void bfs(Node* start, char (*print)(int)) {
    queue<Node*> q;
    q.enqueue(start);
    while (!q.empty()) {
        Node* node = q.dequeue();
        print(node->vertex); // 访问当前节点
        for (Node* adj : *node->adj) {
            if (!adj->visited) {
                adj->visited = true;
                q.enqueue(adj);
            }
        }
    }
}

最后，你可以这样调用它们：

int main() {
    Node vertices[MAX_VERTICES];
    int edges[] = {/*你的边的连接信息*/};
    createAdjacencyList(vertices, edges);

    // 输出DFS顶点访问次序
    printf("DFS: ");
    dfs(&vertices[0], printf);

    // 输出BFS顶点访问次序
    printf("\nBFS: ");
    bfs(&vertices[0], printf);

    return 0;
}

注意，这只是一个基础版本，实际应用中需要根据具体需求调整代码细节，比如错误检查、输入数据读取等。

**相关问题--:**
1. 在邻接表中如何添加和删除边？
2. 对于大规模图，这两种算法的空间复杂性有何区别？
3. DFS和BFS的时间复杂性分别是多少？

写完整代码，实现建立无向图邻接表存储结构，输出深度和宽度优先遍历顶点访问次序。

首先，我们需要定义一个图的数据结构表示邻接表，以及用于深度优先搜索（DFS）和广度优先搜索（BFS）的方法。以下是一个简单的C语言实现：

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

// 定义节点结构
typedef struct Node {
    int value;   // 节点值
    struct Node* next;  // 邻接列表中的下一个节点指针
} Node;

// 创建新节点
Node* create_node(int val) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->value = val;
    newNode->next = NULL;
    return newNode;
}

// 添加边到邻接表
void add_edge(Node** adj_list, int src, int dest) {
    Node* new_edge = create_node(dest);
    new_edge->next = (*adj_list)[src];
    (*adj_list)[src] = new_edge;
}

// 深度优先遍历
void dfs(Node** adj_list, int start, int visited[], int level) {
    visited[start] = 1;
    printf("%d ", start + 1);  // 输出顶点编号
    for (Node* node = (*adj_list)[start]; node != NULL; node = node->next) {
        if (!visited[node->value]) {
            dfs(adj_list, node->value, visited, level + 1);
        }
    }
}

// 广度优先遍历
void bfs(Node** adj_list, int start, int visited[]) {
    int queue[100], front = -1, rear = -1;
    visited[start] = 1;
    queue[++rear] = start;
    
    while (front < rear) {
        int curr = queue[++front];
        printf("%d ", curr + 1);  // 输出顶点编号
        
        for (Node* node = (*adj_list)[curr]; node != NULL; node = node->next) {
            if (!visited[node->value]) {
                visited[node->value] = 1;
                queue[++rear] = node->value;
            }
        }
    }
}

int main() {
    int num_vertices;  // 图的顶点数
    printf("Enter number of vertices: ");
    scanf("%d", &num_vertices);

    // 初始化邻接表，假设为完全图
    Node** adj_list = (Node**)malloc(num_vertices * sizeof(Node*));
    for (int i = 0; i < num_vertices; ++i) {
        adj_list[i] = NULL;
    }

    // 假设添加了所有可能的边
    for (int i = 0; i < num_vertices; ++i) {
        for (int j = i+1; j < num_vertices; ++j) {
            add_edge(adj_list, i, j);
            add_edge(adj_list, j, i);  // 无向图，双向连接
        }
    }

    // 深度优先搜索
    printf("\nDepth First Traversal:\n");
    int visited[num_vertices] = {0};
    dfs(adj_list, 0, visited, 0);

    // 广度优先搜索
    printf("\nBreadth First Traversal:\n");
    memset(visited, 0, sizeof(visited));
    bfs(adj_list, 0, visited);

    return 0;
}

在这个例子中，我们使用邻接表存储了一个无向图，然后分别实现了深度优先搜索和广度优先搜索。请注意，这个程序没有处理用户输入边的情况，所以你需要自己提供一个图。