无向图的深度优先遍历

无向图的深度优先遍历（Depth First Search，DFS）是一种用于遍历或搜索树或图的算法。在深度优先遍历中，从一个节点开始，尽可能深地探索每个分支，直到无法继续为止，然后回溯到前一个节点，尝试探索其他分支。这个过程一直进行到所有节点都被访问为止。

以下是无向图的深度优先遍历的伪代码：

1. 从起始顶点开始遍历

2. 标记起始顶点为已访问

3. 对于起始顶点的每个未访问的邻居顶点：

1. 递归调用深度优先遍历函数

4. 返回

在实际编程中，可以使用递归或栈来实现深度优先遍历。以下是使用递归实现的 Python 代码示例：

def dfs(graph, vertex, visited):
    visited.add(vertex)
    print(vertex)
    for neighbor in graph[vertex]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

其中，graph 是一个字典，表示无向图的邻接表，vertex 是当前遍历的顶点，visited 是一个集合，用于保存已访问过的顶点。

相关问题

无向图深度优先遍历序列

无向图深度优先遍历序列可以通过深度优先搜索（DFS）算法获得。DFS算法可以通过递归或栈实现。下面是一种递归实现的DFS算法，其中visited数组用于记录每个节点是否被访问过，dfs函数用于递归地访问每个节点并将其加入遍历序列中：

vector<int> dfs(vector<vector<int>>& graph, vector<bool>& visited, int node) {
    visited[node] = true;
    vector<int> traversal{node};
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            vector<int> neighbor_traversal = dfs(graph, visited, neighbor);
            traversal.insert(traversal.end(), neighbor_traversal.begin(), neighbor_traversal.end());
        }
    }
    return traversal;
}

vector<int> dfsTraversal(vector<vector<int>>& graph) {
    int n = graph.size();
    vector<bool> visited(n, false);
    vector<int> traversal;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            vector<int> i_traversal = dfs(graph, visited, i);
            traversal.insert(traversal.end(), i_traversal.begin(), i_traversal.end());
        }
    }
    return traversal;
}

其中，graph是无向图的邻接表表示，visited是一个bool类型的数组，表示各个节点是否被访问过。dfsTraversal函数返回的是遍历序列。

无向图的深度优先遍历结构体

以下是一个简单的无向图深度优先遍历的结构体示例：

#include <iostream>
#include <vector>

using namespace std;

struct Graph {
    int V; // 顶点数
    vector<int> *adj; // 邻接表

    Graph(int V) {
        this->V = V;
        adj = new vector<int>[V];
    }

    void addEdge(int v, int w) {
        adj[v].push_back(w);
        adj[w].push_back(v);
    }

    void DFSUtil(int v, bool visited[]) {
        visited[v] = true;
        cout << v << " ";

        for (auto i = adj[v].begin(); i != adj[v].end(); ++i) {
            if (!visited[*i]) {
                DFSUtil(*i, visited);
            }
        }
    }

    void DFS(int v) {
        bool *visited = new bool[V];
        for (int i = 0; i < V; i++) {
            visited[i] = false;
        }

        DFSUtil(v, visited);
    }
};

int main() {
    Graph g(5);
    g.addEdge(1, 0);
    g.addEdge(0, 2);
    g.addEdge(2, 1);
    g.addEdge(0, 3);
    g.addEdge(1, 4);

    cout << "Depth First Traversal starting from vertex 0: " << endl;
    g.DFS(0);

    return 0;
}

在这个结构体中，我们定义了一个 `Graph` 结构体，该结构体包含了图的顶点数 `V` 和邻接表 `adj`。我们还定义了 `addEdge` 函数来添加边，以及 `DFSUtil` 函数来实现递归深度优先遍历，和 `DFS` 函数来初始化并调用 `DFSUtil` 函数。在 `DFSUtil` 函数中，我们使用了一个布尔类型的数组 `visited` 来跟踪哪些节点已经被访问过了。最后，在 `main` 函数中，我们创建了一个 `Graph` 对象，并添加了一些边，然后调用 `DFS` 函数来进行深度优先遍历。