{"id":310,"date":"2011-10-07T14:08:31","date_gmt":"2011-10-07T06:08:31","guid":{"rendered":"http:\/\/wangkaixuan.tech\/?p=310"},"modified":"2020-06-06T14:09:48","modified_gmt":"2020-06-06T06:09:48","slug":"%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84_%e5%9b%be_%e6%b1%82%e6%9c%89%e5%90%91%e5%9b%be%e7%9a%84%e5%bc%ba%e8%bf%9e%e9%80%9a%e5%88%86%e9%87%8f","status":"publish","type":"post","link":"http:\/\/www.wangkaixuan.tech\/?p=310","title":{"rendered":"\u6570\u636e\u7ed3\u6784_\u56fe_\u6c42\u6709\u5411\u56fe\u7684\u5f3a\u8fde\u901a\u5206\u91cf"},"content":{"rendered":"\n

head.h<\/p>\n\n\n\n

#include<iostream>\nusing namespace std;\n#define MAX_VEX_NUM 20\n\nclass ArcNode \/\/\u8bb0\u5f55\u4e00\u6761\u5f27 \n{\npublic:\n\tArcNode();\n\tint headvex, tailvex;\n\tArcNode *hlink, *tlink;\n};\n\nArcNode::ArcNode()\n{\n\theadvex = tailvex = 0;\n\thlink = tlink = NULL;\n}\n\nclass VexNode \/\/\u8bb0\u5f55\u4e00\u4e2a\u9876\u70b9\u8fde\u63a5\u7684\u6240\u6709\u5f27\n{\npublic:\n\tVexNode();\n\tbool visited;\n\tchar vexname;\n\tArcNode *firstin, *firstout;\n};\n\nVexNode::VexNode()\n{\n\tvisited = false;\n\tfirstin = firstout = NULL;\n}\n\nclass VexBox \/\/\u9876\u70b9\u96c6\u5408\n{\npublic:\n\tVexBox();\n\tVexNode vexlist[MAX_VEX_NUM];\n\tint vexnum;\n};\n\nVexBox::VexBox()\n{\n\tvexnum = 0;\n}\n\nclass Graph \/\/\u56fe\u7c7b\n{\npublic:\n\tvoid ShowGraph(); \/\/\u63a5\u53e3\u51fd\u6570\nprivate:\n\tvoid GetVexList(); \/\/\u5f97\u5230\u9876\u70b9\u5217\u8868\n\tvoid CreatGraph(); \/\/\u5efa\u56fe\n\tvoid Print(); \/\/\u6253\u5370\u56fe\u4fe1\u606f\n\tvoid StrongComp(); \/\/\u6c42\u5f3a\u8fde\u901a\u5206\u91cf\n\tvoid DFSHead(int); \/\/\u6b63\u5411DFS\n\tvoid DFSTail(int); \/\/\u53cd\u5411DFS\n\tVexBox vbox;\n\tint count, finished[MAX_VEX_NUM], ans[MAX_VEX_NUM], nans;\n};\n\nvoid Graph::ShowGraph() \/\/\u63a5\u53e3\u51fd\u6570\n{\n\tGetVexList(); \/\/\u5f97\u5230\u9876\u70b9\u5217\u8868\n\tCreatGraph(); \/\/\u5efa\u56fe\n\tPrint(); \/\/\u6253\u5370\u56fe\u4fe1\u606f\n\tStrongComp(); \/\/\u6c42\u5f3a\u8fde\u901a\u5206\u91cf\n}\n\nvoid Graph::GetVexList() \/\/\u5f97\u5230\u9876\u70b9\u5217\u8868\n{\n\tcout << \"Please Input Vertexes :\" << endl << endl;\n\tchar name;\n\twhile (cin >> name)\n\t{\n\t\tvbox.vexlist[vbox.vexnum++].vexname = name;\n\t}\n\tcin.clear();\n}\n\nvoid Graph::CreatGraph() \/\/\u5efa\u56fe\n{\n\tcout << \"Please Input Arces :\" << endl << endl;\n\tint head, tail;\n\tArcNode *newnode, *p;\n\twhile (cin >> tail >> head)\n\t{\n\t\tnewnode = new ArcNode;\n\t\tnewnode->headvex = head;\n\t\tnewnode->tailvex = tail;\n\t\tp = vbox.vexlist[tail].firstout;\n\t\tif (p == NULL)\n\t\t{\n\t\t\tvbox.vexlist[tail].firstout = newnode;\n\t\t}\n\t\telse\n\t\t{\n\t\t\twhile (p->tlink != NULL)\n\t\t\t{\n\t\t\t\tp = p->tlink;\n\t\t\t}\n\t\t\tp->tlink = newnode;\n\t\t}\n\t\tp = vbox.vexlist[head].firstin;\n\t\tif (p == NULL)\n\t\t{\n\t\t\tvbox.vexlist[head].firstin = newnode;\n\t\t}\n\t\telse\n\t\t{\n\t\t\twhile (p->hlink != NULL)\n\t\t\t{\n\t\t\t\tp = p->hlink;\n\t\t\t}\n\t\t\tp->hlink = newnode;\n\t\t}\n\t}\n\tcin.clear();\n}\n\nvoid Graph::Print() \/\/\u6253\u5370\u56fe\u4fe1\u606f\n{\n\tArcNode *p;\n\tfor (int i = 0; i < vbox.vexnum; i++)\n\t{\n\t\tcout << vbox.vexlist[i].vexname << endl;\n\t\tp = vbox.vexlist[i].firstout;\n\t\twhile (p != NULL)\n\t\t{\n\t\t\tcout << \"\\t\" << vbox.vexlist[p->tailvex].vexname << \"->\"\n\t\t\t\t\t<< vbox.vexlist[p->headvex].vexname << endl;\n\t\t\tp = p->tlink;\n\t\t}\n\t}\n}\n\nvoid Graph::StrongComp() \/\/\u6c42\u5f3a\u8fde\u901a\u5206\u91cf\n{\n\tcount = 0;\n\tfor (int i = 0; i < vbox.vexnum; i++)\n\t{\n\t\tif (vbox.vexlist[i].visited == false)\n\t\t\tDFSHead(i);\n\t}\n\tfor (int i = 0; i < vbox.vexnum; i++)\n\t\tvbox.vexlist[i].visited = false;\n\tfor (int i = count - 1; i >= 0; i--)\n\t{\n\t\tif (vbox.vexlist[i].visited == false)\n\t\t{\n\t\t\tnans = 0;\n\t\t\tDFSTail(i);\n\t\t\tif (nans > 0)\n\t\t\t{\n\t\t\t\tcout << vbox.vexlist[ans[0]].vexname;\n\t\t\t\tfor (int i = 1; i < nans; i++)\n\t\t\t\t\tcout << \"<->\" << vbox.vexlist[ans[i]].vexname;\n\t\t\t\tcout << endl;\n\t\t\t}\n\t\t}\n\t}\n}\n\nvoid Graph::DFSHead(int k) \/\/\u6b63\u5411DFS\n{\n\tvbox.vexlist[k].visited = true;\n\tArcNode *p = vbox.vexlist[k].firstout;\n\twhile (p != NULL)\n\t{\n\t\tif (vbox.vexlist[p->headvex].visited == false)\n\t\t\tDFSHead(p->headvex);\n\t\tp = p->tlink;\n\t}\n\tfinished[count++] = k;\n}\n\nvoid Graph::DFSTail(int k) \/\/\u53cd\u5411DFS\n{\n\tans[nans++] = k;\n\tvbox.vexlist[k].visited = true;\n\tArcNode *p = vbox.vexlist[k].firstin;\n\twhile (p != NULL)\n\t{\n\t\tif (vbox.vexlist[p->tailvex].visited == false)\n\t\t{\n\t\t\tDFSTail(p->tailvex);\n\t\t}\n\t\tp = p->tlink;\n\t}\n}\n<\/code><\/pre>\n\n\n\n
main.cpp<\/p>\n\n\n\n
#include\"head.h\"\n \nint main()\n{\n\tGraph g;\n\tg.ShowGraph();\n\tsystem(\"pause\");\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
head.h main.cpp<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[9],"tags":[],"class_list":["post-310","post","type-post","status-publish","format-standard","hentry","category-06-02-"],"_links":{"self":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/310","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=310"}],"version-history":[{"count":0,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/310\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=310"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=310"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=310"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}