Some more rough and ready algorithm code, non-OO C++. Pretty bad code, not well tested, just playing.<\/p>\n
\r\n#include <iostream>\r\n#include <vector>\r\n#include <stdlib.h>\r\n#include <algorithm>\r\n\r\nusing namespace std;\r\n\r\n\r\nclass Node {\r\n\r\npublic:\r\n\r\n Node() {\r\n }\r\n\r\n vector<Node *> children;\r\n Node *parent;\r\n};\r\n\r\nNode *make_random_tree(size_t size,Node *root=NULL) {\r\n\r\n if(root == NULL) {\r\n root = new Node();\r\n }\r\n\r\n Node *current = root;\r\n\r\n size_t children=rand()%size;\r\n for(size_t i=0;i<children;i++) {\r\n Node *nd = new Node();\r\n nd->parent = current;\r\n current->children.push_back(nd);\r\n }\r\n\r\n for(size_t n=0;n<current->children.size();n++) {\r\n make_random_tree(size-children,current->children[n]);\r\n }\r\n\r\n return root;\r\n}\r\n\r\nNode *get_random(Node *root,size_t avg_size) {\r\n\r\n Node *current = root;\r\n for(;rand()%(avg_size*2) != 0;) {\r\n if(current->children.size() == 0) return current;\r\n\r\n current = current->children[rand()%current->children.size()];\r\n }\r\n\r\n return current;\r\n}\r\n\r\nNode * get_next_child(Node *node,Node *child) {\r\n\r\n bool next=false;\r\n for(size_t n=0;n<node->children.size();n++) {\r\n\r\n if(next==true) {\r\n return node->children[n];\r\n }\r\n\r\n if(node->children[n] == child) next=true;\r\n }\r\n\r\n return NULL;\r\n}\r\n\r\nvector<Node *> get_path(Node *root,Node *n) {\r\n\r\n vector<Node *> current_path;\r\n current_path.push_back(root);\r\n\r\n if(n==root) return current_path;\r\n\r\n Node *current_child = root->children[0];\r\n\r\n for(;;) {\r\n\r\n current_path.push_back(current_child);\r\n if(current_child == n) return current_path;\r\n\r\n if(current_child->children.size() != 0) {\r\n current_path.push_back(current_child->children[0]);\r\n current_child = current_child->children[0];\r\n } else {\r\n current_child = NULL;\r\n for(;current_child == NULL;) {\r\n Node *old_child = current_path[current_path.size()-1];\r\n current_path.erase(current_path.begin()+current_path.size()-1,current_path.end());\r\n current_child = get_next_child(current_path[current_path.size()-1],old_child);\r\n\r\n if(old_child==root) { return vector<Node *>(); }\r\n }\r\n }\r\n }\r\n\r\n \/\/ Should never get here\r\n return vector<Node *>();\r\n}\r\n\r\nvector<Node *> get_path_parent(Node *root,Node *n) {\r\n\r\n vector<Node *> v;\r\n\r\n for(Node *current = n;current != root;current = current->parent) {\r\n v.push_back(current);\r\n }\r\n v.push_back(root);\r\n\r\n reverse(v.begin(),v.end());\r\n\r\n return v;\r\n}\r\n\r\nNode *find_lca_parent(Node *root,Node *n1,Node *n2) {\r\n\r\n vector<Node *> path1 = get_path_parent(root,n1);\r\n vector<Node *> path2 = get_path_parent(root,n2);\r\n\r\n for(size_t n=0;n<path1.size();n++) {cout << path1[n] << " ";} cout << endl;\r\n for(size_t n=0;n<path2.size();n++) {cout << path2[n] << " ";} cout << endl;\r\n\r\n size_t shortest_path_length;\r\n if(path1.size() < path2.size()) shortest_path_length = path1.size();\r\n else shortest_path_length = path2.size();\r\n\r\n size_t n;\r\n for(n=0;(n<shortest_path_length) && (path1[n] == path2[n]);n++);\r\n\r\n return path1[n-1];\r\n}\r\n\r\nNode *find_lca(Node *root,Node *n1,Node *n2) {\r\n\r\n vector<Node *> path1 = get_path(root,n1);\r\n vector<Node *> path2 = get_path(root,n2);\r\n\r\n size_t shortest_path_length;\r\n if(path1.size() < path2.size()) shortest_path_length = path1.size();\r\n else shortest_path_length = path2.size();\r\n\r\n size_t n;\r\n for(n=0;(n<shortest_path_length) && (path1[n] == path2[n]);n++);\r\n\r\n return path1[n-1];\r\n}\r\n\r\nint main() {\r\n\r\n Node *root = make_random_tree(100);\r\n\r\n Node *n1 = get_random(root,20);\r\n Node *n2 = get_random(root,20);\r\n\r\n Node *lca1a = find_lca_parent(root,n1,n2);\r\n Node *lca1b = find_lca (root,n1,n2);\r\n\r\n cout << "LCA1-a: " << lca1a << endl;\r\n cout << "LCA1-b: " << lca1a << endl;\r\n\r\n Node *n3 = root->children[0]->children[0]->children[0];\r\n Node *n4 = root->children[0]->children[0]->children[1];\r\n Node *lca2a = find_lca_parent(root,n3,n4);\r\n Node *lca2b = find_lca (root,n3,n4);\r\n\r\n cout << "LCA2-a: " << lca2a << endl;\r\n cout << "LCA2-b: " << lca2b << endl;\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"Some more rough and ready algorithm code, non-OO C++. Pretty bad code, not well tested, just playing. #include <iostream> #include <vector> #include <stdlib.h> #include <algorithm> using namespace std; class Node { public: Node() { } vector<Node *> children; Node *parent; }; Node *make_random_tree(size_t size,Node *root=NULL) { if(root == NULL) { root = new Node(); } […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[1],"tags":[],"class_list":["post-844","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p1RRoU-dC","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts\/844","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/comments?post=844"}],"version-history":[{"count":2,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts\/844\/revisions"}],"predecessor-version":[{"id":846,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts\/844\/revisions\/846"}],"wp:attachment":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/media?parent=844"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/categories?post=844"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/tags?post=844"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}