图深度优先遍历和广度优先遍历

图的深度优先遍历和广度优先遍历是两种常见的图遍历算法。

深度优先遍历（Depth First Search，DFS）是一种先访问深度较深的节点的搜索方法。具体实现可以使用递归或栈来实现。在遍历过程中，每个节点只会被访问一次，因此时间复杂度为 O(V+E)，其中 V 表示节点数，E 表示边数。

广度优先遍历（Breadth First Search，BFS）是一种先访问离起始节点近的节点的搜索方法。具体实现可以使用队列来实现。在遍历过程中，每个节点只会被访问一次，因此时间复杂度为 O(V+E)，其中 V 表示节点数，E 表示边数。

相关问题

图的深度优先遍历和广度优先遍历代码

以下是JavaScript实现图的深度优先遍历和广度优先遍历的代码：

深度优先遍历：

function dfs(node) {
  if (!node) return;
  console.log(node.val);
  node.visited = true;
  for (let i = 0; i < node.neighbors.length; i++) {
    const neighbor = node.neighbors[i];
    if (!neighbor.visited) {
      dfs(neighbor);
    }
  }
}

广度优先遍历：

function bfs(node) {
  if (!node) return;
  const queue = [node];
  node.visited = true;
  while (queue.length) {
    const curr = queue.shift();
    console.log(curr.val);
    for (let i = 0; i < curr.neighbors.length; i++) {
      const neighbor = curr.neighbors[i];
      if (!neighbor.visited) {
        neighbor.visited = true;
        queue.push(neighbor);
      }
    }
  }
}

C语言图的深度优先遍历和广度优先遍历

以下是C语言实现的图的深度优先遍历和广度优先遍历的代码示例：

深度优先遍历：

#define MAX 100
int visited[MAX] = {0}; // 全局数组，用于标记节点是否被访问过

// 深度优先遍历算法
void DFS(AdjGraph *G, int v) {
    ArcNode *p;
    visited[v] = 1; // 标记节点v已被访问
    printf("%d ", v); // 输出被访问的节点编号
    p = G->adjlist[v].firstarc;
    while (p != NULL) {
        if (visited[p->adjvex] == 0) { // 若节点未被访问，则递归访问它
            DFS(G, p->adjvex);
        }
        p = p->nextarc;    }
}

// 深度优先遍历入口函数
void DFSTraverse(AdjGraph *G) {
    int i;
    for (i = 0; i < G->n; i++) {
        visited[i] = 0; // 初始化visited数组
    }
    for (i = 0; i < G->n; i++) {
        if (visited[i] == 0) { // 若节点未被访问，则从该节点开始进行深度优先遍历
            DFS(G, i);
        }
    }
}

广度优先遍历：

#define MAX 100
int visited[MAX] = {0}; // 全局数组，用于标记节点是否被访问过

// 广度优先遍历算法
void BFS(AdjGraph *G, int v) {
    int queue[MAX], front = 0, rear = 0; // 定义队列
    ArcNode *p;
    visited[v] = 1; // 标记节点v已被访问
    printf("%d ", v); // 输出被访问的节点编号
    rear = (rear + 1) % MAX;
    queue[rear] = v; // 将节点v入队
    while (front != rear) { // 队列不为空时循环
        front = (front + 1) % MAX;
        v = queue[front]; // 出队一个节点
        p = G->adjlist[v].firstarc;
        while (p != NULL) {
            if (visited[p->adjvex] == 0) { // 若节点未被访问，则标记为已访问并入队
                visited[p->adjvex] = 1;
                printf("%d ", p->adjvex);
                rear = (rear + 1) % MAX;
                queue[rear] = p->adjvex;
            }
            p = p->nextarc;
        }
    }
}

// 广度优先遍历入口函数
void BFSTraverse(AdjGraph *G) {
    int i;
    for (i = 0; i < G->n; i++) {
        visited[i] = 0; // 初始化visited数组
    }
    for (i = 0; i < G->n; i++) {
        if (visited[i] == 0) { // 若节点未被访问，则从该节点开始进行广度优先遍历
            BFS(G, i);
        }
    }
}