数据结构邻接表问题C语言

Question

根据输入的邻接表矩阵创建图的邻接表，然后进行遍历操历操作。
（1）输入图的邻接表矩阵数据
（2）创建图的邻接表并数出
（3）按照DFS遍历输出
（4）按照BFS遍历输出
要求输入：
顶点个数n
邻接矩阵nxn
顶点编号（DFS起点）
顶点编号（BFS起点）

Answer 1

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

// 图的邻接表节点
struct Node {
    int vertex;
    Node* next;
};

// 创建图的邻接表
vector<Node*> createGraph(int n, int** matrix) {
    vector<Node*> adjacencyList(n, nullptr);

    for (int i = 0; i < n; i++) {
        Node* current = nullptr;
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == 1) {
                Node* newNode = new Node();
                newNode->vertex = j;
                newNode->next = nullptr;

                if (current == nullptr) {
                    adjacencyList[i] = newNode;
                    current = newNode;
                } else {
                    current->next = newNode;
                    current = newNode;
                }
            }
        }
    }

    return adjacencyList;
}

// DFS遍历
void DFS(vector<Node*>& adjacencyList, int start) {
    vector<bool> visited(adjacencyList.size(), false);
    stack<int> s;
    s.push(start);

    while (!s.empty()) {
        int current = s.top();
        s.pop();

        if (!visited[current]) {
            cout << current << " ";
            visited[current] = true;

            Node* temp = adjacencyList[current];
            while (temp != nullptr) {
                s.push(temp->vertex);
                temp = temp->next;
            }
        }
    }
}

// BFS遍历
void BFS(vector<Node*>& adjacencyList, int start) {
    vector<bool> visited(adjacencyList.size(), false);
    queue<int> q;
    q.push(start);

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

        if (!visited[current]) {
            cout << current << " ";
            visited[current] = true;

            Node* temp = adjacencyList[current];
            while (temp != nullptr) {
                q.push(temp->vertex);
                temp = temp->next;
            }
        }
    }
}

int main() {
    int n;
    cout << "请输入顶点个数n：";
    cin >> n;

    int** matrix = new int*[n];
    for (int i = 0; i < n; i++) {
        matrix[i] = new int[n];
        cout << "请输入邻接矩阵第 " << i+1 << " 行的数据（以空格分隔）：";
        for (int j = 0; j < n; j++) {
            cin >> matrix[i][j];
        }
    }

    int dfsStart, bfsStart;
    cout << "请输入DFS起点的顶点编号：";
    cin >> dfsStart;
    cout << "请输入BFS起点的顶点编号：";
    cin >> bfsStart;

    vector<Node*> adjacencyList = createGraph(n, matrix);

    cout << "DFS遍历结果为：";
    DFS(adjacencyList, dfsStart);

    cout << endl;

    cout << "BFS遍历结果为：";
    BFS(adjacencyList, bfsStart);

    // 释放内存
    for (int i = 0; i < n; i++) {
        delete[] matrix[i];
    }
    delete[] matrix;

    return 0;
}