将有向图转换为树
data structurec++programming
有向图是描述实体之间连接的强大数据结构。为了便于分析或提高算法效率，在某些情况下将有向图转换为树结构可能会有所帮助。在这篇文章中，我们将介绍两种将有向图转换为树的 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;
// 使用 DFS 将图转换为树
convertGraphToTreeDFS(graph, rootNode, visited, tree);
// 打印树结构
for (int i = 0; i < numVertices; i++) {
cout << "Node " << i << " -> ";
for (int child : tree[i]) {
cout << child << " ";
}
cout << endl;
}
}
int main() {
// 创建 Graph 类的实例
int numVertices = 5;
Graph graph(numVertices);
// 向图添加边
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
// 调用函数将图转换为树
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;
// 表示树中节点的结构
struct Node {
int value;
vector<Node*> children;
};
// 使用 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);
}
// 将有向图转换为树的函数
Node* convertToTree(vector<vector<int>>& graph) {
int numVertices = graph.size();
vector<bool> visited(numVertices, false);
stack<int> stk;
// 执行拓扑排序
for (int i = 0; i < numVertices; i++) {
if (!visited[i]) {
topologicalSortDFS(i, graph, visited, stk);
}
}
// 创建树
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;
}
// 以前序遍历方式打印树的函数
void printTree(Node* root) {
if (root == nullptr) {
return;
}
cout << root->value << " ";
for (Node* child : root->children) {
printTree(child);
}
}
int main() {
// 图形表示示例(邻接表)
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
};
// 将有向图转换为树
Node* treeRoot = convertToTree(graph);
// 按前序遍历打印树
cout << "Tree nodes: ";
printTree(treeRoot);
return 0;
}
输出
Tree nodes: 0
结论
本文讨论了在 C 语言中将有序图转换为树结构的两种方法。研究的方法是深度优先查找 (DFS) 和拓扑排序。每种方法都进行了说明，然后通过代码示例说明了每种方法的用法和结果。本文旨在让读者全面了解如何使用不同的算法将有序图转换为树。
