图的创建、深度优先遍历、广度优先遍历

图的创建：

图由节点和边组成，可以使用邻接矩阵或邻接表来表示。

1.邻接矩阵：用一个二维数组来表示节点之间的关系，其中矩阵的行和列分别表示节点，矩阵中的元素表示节点之间是否有连边。

2.邻接表：用一个数组和若干个链表来表示，数组中的元素表示节点，每个节点对应一个链表，链表中存储与该节点相连的其他节点。

深度优先遍历：

深度优先遍历是一种遍历图的方式，从一个节点开始，尽可能深地访问该节点的所有子节点，直到所有的子节点都被访问完毕，然后回溯到上一个节点，继续访问其未被访问过的子节点，直到整个图被遍历完毕。

1.从起点开始遍历，将起点标记为已访问。

2.对于起点的每个未被访问过的邻居节点，递归地进行深度优先遍历。

3.回溯到上一个节点，继续访问其未被访问过的邻居节点，直到所有节点都被访问过。

广度优先遍历：

广度优先遍历是一种遍历图的方式，从一个节点开始，依次访问其所有邻居节点，然后再访问邻居节点的邻居节点，以此类推，直到整个图被遍历完毕。

1.从起点开始遍历，将起点标记为已访问，并将其加入队列。

2.从队列中取出一个节点，访问其所有未被访问过的邻居节点，并将这些邻居节点加入队列。

3.重复步骤2，直到队列为空，即所有节点都被访问过。

相关问题

深度优先遍历 广度优先遍历

深度优先遍历（Depth-First Search，DFS）和广度优先遍历（Breadth-First Search，BFS）是两种常用的图遍历算法。

深度优先遍历是一种通过递归或者栈的方式来遍历图的算法。它从图的某个顶点开始，沿着一条路径一直遍历到最后一个顶点，然后回溯到前一个顶点，再继续遍历其它未遍历的路径。重复这个过程，直到遍历完所有的顶点。

广度优先遍历是一种通过队列的方式来遍历图的算法。它从图的某个顶点开始，首先访问该顶点，然后将其所有未访问过的邻接顶点加入到队列中。之后从队列中取出一个顶点，并访问它的邻接顶点，再将这些邻接顶点加入队列。重复这个过程，直到队列为空。

总结起来，深度优先遍历是先纵向遍历到底再回溯，而广度优先遍历是先横向遍历一层再逐层向下。这两种遍历算法在不同的问题中有不同的应用场景和特点。

无向图的深度优先遍历广度优先遍历c语言

在C语言中，无向图的深度优先遍历（Depth-First Search, BFS）都是用于搜索图的数据结构算法。

**深度优先遍历（DFS）**:
1. **递归实现**：从起始顶点开始，选择一条未访问的边并深入探索。如果当前节点的所有邻接节点都已访问，则回溯到上一个节点继续处理。

   void dfs(int node, int graph[], int visited[]) {
       visited[node] = 1;
       for (int i = 0; i < num_nodes; i++) {
           if (graph[node][i] == 1 && visited[i] == 0)
               dfs(i, graph, visited);
       }
   }

2. **栈实现**：可以使用栈数据结构模拟递归过程，将待访问的节点压入栈中。

**广度优先遍历（BFS）**:
1. **队列实现**：从起始顶点开始，首先将其加入队列，然后每次从队列头部取出一个节点，访问其所有邻接节点并将它们加入队列，直到队列为空。

   void bfs(int start) {
       queue<int> q;
       visited[start] = 1;
       q.push(start);
       while (!q.empty()) {
           int curr = q.front();
           q.pop();
           // Process the current node
           for (int neighbor = 0; neighbor < num_nodes; neighbor++) {
               if (graph[curr][neighbor] == 1 && visited[neighbor] == 0) {
                   visited[neighbor] = 1;
                   q.push(neighbor);
               }
           }
       }
   }