将有向图转换为树

描绘实体之间连接的强大数据结构是有向图。在某些情况下，为了便于分析或提高算法效率，将有向图转换为树结构可能是有益的。在这篇文章中，我们将探讨两种将有向图转换为树的 CPP 算法方法。我们将介绍每种方法的算法，提供相关的代码示例，并展示每种方法的独特结果。

使用的方法

  • 深度优先搜索 (DFS)

  • 拓扑排序

深度优先搜索 (DFS)

第一种方法使用深度优先搜索算法遍历图以创建树结构。我们从根节点开始，在每个未探索的节点与其相邻节点之间建立边，以确保生成的树不包含任何循环。算法按以下方式工作

算法

  • 选择一个根节点。

  • 创建一个空树。

  • 从根节点开始，运行深度优先搜索。

  • 从当前节点到遇到的每个未探索节点形成一条边，并递归地对其进行探索。

  • 继续直到每个节点都被访问。

示例

#include <iostream>
#include <vector>

using namespace std;

class Graph {
private:
    vector<vector<int>> adjacencyList;

public:
    Graph(int numVertices) {
        adjacencyList.resize(numVertices);
    }

    void addEdge(int u, int v) {
        adjacencyList[u].push_back(v);
        adjacencyList[v].push_back(u);
    }

    int getNumVertices() {
        return adjacencyList.size();
    }

    vector<int> getAdjacentNodes(int node) {
        return adjacencyList[node];
    }
};

void convertGraphToTreeDFS(Graph& graph, int rootNode, vector<bool>& visited, vector<vector<int>>& tree) {
    visited[rootNode] = true;

    for (int adjacentNode : graph.getAdjacentNodes(rootNode)) {
        if (!visited[adjacentNode]) {
            tree[rootNode].push_back(adjacentNode);
            convertGraphToTreeDFS(graph, adjacentNode, visited, tree);
        }
    }
}

void convertGraphToTree(Graph& graph) {
    int numVertices = graph.getNumVertices();
    vector<bool> visited(numVertices, false);
    vector<vector<int>> tree(numVertices);

      int rootNode = 0;

    // Convert graph to tree using DFS
    convertGraphToTreeDFS(graph, rootNode, visited, tree);

    // Print tree structure
    for (int i = 0; i < numVertices; i++) {
        cout << "Node " << i << " -> ";
        for (int child : tree[i]) {
            cout << child << " ";
        }
        cout << endl;
    }
}

int main() {
    // Create an instance of the Graph class
    int numVertices = 5;
    Graph graph(numVertices);

    // Add edges to the graph
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 3);
    graph.addEdge(1, 4);

    // Call the function to convert the graph to a tree
    convertGraphToTree(graph);

    return 0;
}

输出

Node 0 -> 1 2 
Node 1 -> 3 4 
Node 2 -> 
Node 3 ->
Node 4 ->

拓扑排序

第三种技术通过使用拓扑排序的概念将有向图转换为树。通过确保创建的树是无环的，拓扑排序确保它是对有向图的充分表示。

算法

  • 按拓扑顺序对有向图进行排序。

  • 创建一个空树。

  • 在当前节点之间建立链接。

示例

#include <iostream>
#include <vector>
#include <stack>
#include <unordered_map>

using namespace std;

// Structure to represent a node in the tree
struct Node {
    int value;
    vector<Node*> children;
};

// Function to perform topological sorting using DFS
void topologicalSortDFS(int node, vector<vector<int>>& graph, vector<bool>& visited, stack<int>& stk) {
    visited[node] = true;

    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            topologicalSortDFS(neighbor, graph, visited, stk);
        }
    }

    stk.push(node);
}

// Function to convert directed graph into a tree
Node* convertToTree(vector<vector<int>>& graph) {
    int numVertices = graph.size();
    vector<bool> visited(numVertices, false);
    stack<int> stk;

    // Perform topological sorting
    for (int i = 0; i < numVertices; i++) {
        if (!visited[i]) {
            topologicalSortDFS(i, graph, visited, stk);
        }
    }

    // Create the tree
    unordered_map<int, Node*> nodes;
    Node* root = nullptr;

    while (!stk.empty()) {
        int nodeValue = stk.top();
        stk.pop();

        if (nodes.find(nodeValue) == nodes.end()) {
            Node* node = new Node{nodeValue, {}};
            nodes[nodeValue] = node;

            if (graph[nodeValue].empty()) {
                root = node;
            } else {
                for (int neighbor : graph[nodeValue]) {
                    if (nodes.find(neighbor) != nodes.end()) {
                        nodes[neighbor]->children.push_back(node);
                    }
                }
            }
        }
    }

    return root;
}

// Function to print the tree in pre-order traversal
void printTree(Node* root) {
    if (root == nullptr) {
        return;
    }

    cout << root->value << " ";

    for (Node* child : root->children) {
        printTree(child);
    }
}

int main() {
    // Example graph representation (adjacency list)
    vector<vector<int>> graph = {
        {},       // Node 0
        {0},      // Node 1
        {0},      // Node 2
        {1, 2},   // Node 3
        {2},      // Node 4
        {4},      // Node 5
        {3, 4},   // Node 6
    };

    // Convert directed graph into a tree
    Node* treeRoot = convertToTree(graph);

    // Print the tree in pre-order traversal
    cout << "Tree nodes: ";
    printTree(treeRoot);

    return 0;
}

输出

Tree nodes: 0

结论

本文讨论了两种在 C 中将有向图转换为树结构的方法。所研究的方法是深度优先搜索 (DFS) 和拓扑排序。每种方法都进行了阐述，随后是说明每种方法的使用和结果的代码示例。本文旨在为读者提供全面了解如何使用不同的算法将有向图转换为树。

更新于: 2023年7月14日

2K+ 阅读量

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告