实现深度遍历邻接矩阵存储的图头歌

深度优先搜索（DFS，Depth First Search）是一种用于遍历或搜索树形结构或图的数据结构算法。对于用邻接矩阵表示的图，深度优先遍历的过程通常是这样的：

1. **初始化**：选择一个起始节点，通常标记为已访问。
2. **访问节点**：将当前节点添加到访问序列中，并打印出来。
3. **探索边**：对于当前节点的所有未访问邻居，如果它们尚未访问，则递归地对它们进行深度优先搜索。
4. **回溯**：完成当前节点的邻居访问后，返回上一个节点，继续从其他未访问的邻居开始。

以下是用Python实现深度优先遍历邻接矩阵存储的图的伪代码：

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    
    visited.add(start)
    print(start)  # 打印当前节点

    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# 示例用法
graph = [[0, 1, 1], [1, 0, 1], [1, 1, 0]]
dfs(graph, 0)  # 从节点0开始遍历

相关问题

深度优先遍历邻接矩阵代码

深度优先遍历（Depth First Search, DFS）是一种用于遍历或搜索树或图的算法。在遍历时，从起点开始，尽可能深地搜索图的分支，直到没有未访问的节点为止，然后回溯到上一个节点，继续搜索下一个分支。邻接矩阵是一种表示图的常见方式，下面是深度优先遍历邻接矩阵的代码实现：

#include <iostream>
using namespace std;

const int MAXSIZE = 100;

class Graph {
private:
    int vertex[MAXSIZE];    // 存储节点信息
    int arc[MAXSIZE][MAXSIZE];  // 存储边信息
    bool visited[MAXSIZE];  // 标记节点是否被访问过
    int vertex_num, arc_num;  // 节点数和边数

public:
    Graph(int vnum, int anum) : vertex_num(vnum), arc_num(anum) {
        for (int i = 0; i < vertex_num; ++i) {
            for (int j = 0; j < vertex_num; ++j) {
                arc[i][j] = 0;
            }
        }
    }
    ~Graph() {}

    void createGraph() {
        cout << "请输入节点信息：" << endl;
        for (int i = 0; i < vertex_num; ++i) {
            cin >> vertex[i];
        }

        cout << "请输入边信息：" << endl;
        for (int i = 0; i < arc_num; ++i) {
            int vi, vj;
            cin >> vi >> vj;
            arc[vi][vj] = 1;
            arc[vj][vi] = 1;  // 如果是有向图，则只存储arc[vi][vj] = 1即可
        }
    }

    void DFS(int v) {
        visited[v] = true;
        cout << vertex[v] << " ";

        for (int i = 0; i < vertex_num; ++i) {
            if (arc[v][i] == 1 && !visited[i]) {
                DFS(i);
            }
        }
    }
};

int main() {
    int vnum, anum;
    cout << "请输入节点数和边数：" << endl;
    cin >> vnum >> anum;

    Graph graph(vnum, anum);
    graph.createGraph();

    cout << "深度优先遍历序列为：" << endl;
    for (int i = 0; i < vnum; ++i) {
        if (!graph.visited[i]) {
            graph.DFS(i);
        }
    }

    return 0;
}

写一段C++代码，要求图的邻接矩阵存储方式深度遍历和广度遍历算法的实现； 图的邻接表存储方式深度遍历和广度遍历算法的实现。

在C++中，我们可以使用邻接矩阵和邻接表两种方式来表示图。这里分别给出这两种存储方式下，深度优先搜索(DFS)和广度优先搜索(BFS)的简单实现：

**邻接矩阵的方式**

#include <iostream>
using namespace std;

// 图结构，邻接矩阵表示
const int MAXN = 100;
bool adj[MAXN][MAXN];

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

    for (int v = 0; v < MAXN; ++v)
        if (adj[u][v] && !visited[v])
            DFS(v, visited);
}

void BFS(int s, bool visited[]) {
    queue<int> q;
    visited[s] = true;
    q.push(s);

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        cout << u << " ";
        
        for (int v = 0; v < MAXN; ++v)
            if (adj[u][v] && !visited[v])
                q.push(v), visited[v] = true;
    }
}

int main() {
    // 初始化图的邻接矩阵...
    
    // 调用DFS和BFS
    bool visited[MAXN];
    DFS(0, visited);   // 深度优先遍历
    cout << "\nDepth First Traversal: \n";
    BFS(0, visited);   // 广度优先遍历
    cout << "\nBreadth First Traversal: \n";

    return 0;
}

**邻接表的方式**

#include <iostream>
#include <vector>
using namespace std;

struct Node {
    int dest;
    vector<Node*> adj;  // 存储邻接节点
};

void DFS(Node* node, bool visited[]) {
    visited[node->dest] = true;
    cout << node->dest << " ";

    for (Node* n : node->adj)
        if (!visited[n->dest])
            DFS(n, visited);
}

void BFS(Node* root, bool visited[]) {
    queue<Node*> q;
    visited[root->dest] = true;
    q.push(root);

    while (!q.empty()) {
        Node* node = q.front();
        q.pop();

        cout << node->dest << " ";

        for (Node* n : node->adj)
            if (!visited[n->dest])
                q.push(n), visited[n->dest] = true;
    }
}

int main() {
    // 初始化图的邻接表...
    
    // 调用DFS和BFS
    bool visited[MAXN];
    DFS(graph[0], visited);   // 深度优先遍历
    cout << "\nDepth First Traversal: \n";
    BFS(graph[0], visited);   // 广度优先遍历
    cout << "\nBreadth First Traversal: \n";

    return 0;
}

在这里，`graph`是一个邻接表形式的图，`Node`结构表示每个顶点及其相邻顶点列表。