將有向圖轉換為樹

描繪實體之間連線的強大資料結構是有向圖。在某些情況下，為了便於分析或提高演算法效率，將有向圖轉換為樹結構可能是有益的。在這篇文章中，我們將探討兩種將有向圖轉換為樹的 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+ 閱讀量

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告