基本数据结构(图: 基本结构，DFS，prim算法, kruskal算法)

#include <iostream>
using namespace std;
//约定：
//1. 图是由很多节点(VERTEX)构成的, 因此图结构是由一个VERTEX的链表构成的, 每个VERTEX则需要有一个id,也就是start, 取start是为了跟LINE更直观地结合。
//2. 每个节点关联着很多(LINE)构成,因此每个VERTEX由很多LINE构成, LINE不需要id, 但是它有3 要素: (start, end, weight), start不必说,取VERTEX中的即可,因此需要end和weight2种.注意: 每个VERTEX中都有一个LINE链表哦..
//3. 因此,图的结构如下所示:
/*
Graph{VERTEX1{line1->line2->line3}|VERTEX2{line1->line2->line3}...Vertexn{line1->line2->line3}
}*/
//图的边
struct LINE{int end;//尾端点int weight;//权重LINE *next;//所有LINE的链表LINE(int e, int w){end = e;weight = w;next = 0;cout<<"LINE:"<<end<<","<<weight<<" created"<<endl;}
};struct VERTEX{int start;//起始点int lineNums;//LINE的数量LINE *first;//与点相关联的边的链表VERTEX *next;//所有VERTEX的链表VERTEX(int s){start = s;lineNums = 0;first = 0;next = 0;cout<<"VERTEX:"<<start<<" created"<<endl;}void visit(){cout<<start<<" ";}
};
//最小生成树的Line结构
struct PrimTreeLine{int start;int end;//尾端点int weight;//权重PrimTreeLine *next;//所有LINE的链表PrimTreeLine(int s, int e, int w){start = s;end = e;weight = w;next = 0;}PrimTreeLine(){}
};
//prim最小生成树结构
struct PrimTree{int start; int vn, ln;int weight;PrimTreeLine*first;VERTEX* list;PrimTree(int s){start = s;vn = 1;ln = 0;weight = 0;first = 0;list = 0;}void insertVertex(int start){if(list){VERTEX * tmp = list;while(tmp->next){tmp = tmp->next;}tmp->next = new VERTEX(start);}else{list = new VERTEX(start);}}void deleteVertex(int start){if(list){VERTEX* tmp = list;if(tmp->start == start){delete tmp;list = 0;return;}else{while(tmp->next){if(tmp->start ==start){VERTEX* t = tmp;tmp = tmp->next;delete t;}}}}}PrimTreeLine* getLast(){PrimTreeLine* l = first;if(l){while(l->next){l = l->next;}return l;}else{return 0;}}PrimTreeLine* getFormer(PrimTreeLine* l){PrimTreeLine* line = first;while(line){if(line->next && line->next->end == l->end){break;}else{line = line->next;}}return line;}void insertLine(PrimTreeLine* l){if(first){getLast()->next = l;}else{first = l;}ln++;vn++;//cout<<"加入line: "<<l->end<<"####ln=="<<ln<<", vn =="<<vn<<endl;}void rmLine(PrimTreeLine*l){//不用delete，因为Line是在graph中的。PrimTreeLine * f = getFormer(l);if(f){PrimTreeLine*d = f->next;f->next = d->next;delete d;}else{PrimTreeLine*d = first;first = first->next;delete d;}}~PrimTree(){while(first){PrimTreeLine* tmp = first;first = first->next;rmLine(tmp);}}void print(){int p = start;PrimTreeLine*l = first;while(l){cout<<"["<<l->start<<"]---"<<l->weight<<"---["<<l->end<<"]";l = l->next;}cout<<endl;}
};//kruskal 开始
struct kruskalVertex{int root;int start;kruskalVertex*next;kruskalVertex*children;kruskalVertex(int start): start(start), root(0), children(0), next(0){}
};
typedef struct PrimTreeLine kruskalLine;
struct kruskalTree{kruskalVertex * root;kruskalLine * first;kruskalTree(int r){root = new kruskalVertex(r);first = 0;}void print(){kruskalLine*l = first;while(l){cout<<"["<<l->start<<"]---"<<l->weight<<"---["<<l->end<<"]";l = l->next;}cout<<endl;}kruskalVertex * findVertex(kruskalVertex * root, int start){kruskalVertex* bl = root;if(bl){if(bl->start == start){return root;}else{kruskalVertex * child = bl->children;while(child){kruskalVertex* res =  findVertex(child, start);if(res) return res;else child = child->next;}}}return 0;}void addLine(kruskalLine* l){if(first){while(first->next) first = first->next;first->next = l;}else{first = l;}}
};
kruskalLine ** allLines;
//kruskal endstruct GRAPH{enum Kind{DG, NG, DN, NN};Kind kind;int count;VERTEX* first;bool *visitDFSArr;GRAPH(): count(0), first(0){kind = DG;visitDFSArr = 0;}GRAPH(Kind k): count(0), first(0){kind = k;visitDFSArr = 0;}GRAPH(Kind k, int start, int end, int weight){kind = k;visitDFSArr = 0;addVertexWithLine(start, end, weight);}~GRAPH(){while(first){VERTEX* v = first;first = first->next;deleteVertex(v->start);}if(visitDFSArr)delete visitDFSArr;}//建立一条新的LineLINE* createNewLine(int end, int weight){//建立一个新LINEreturn new LINE(end,weight);}//建立一个新的VertexVERTEX* createNewVertex(int start){//创建新Vertexreturn new VERTEX(start);}//在图中查找一个Vertex, 如果找到p返回的就是该vertex否则返回最后一个节点。VERTEX* findVertex(VERTEX** p, int start){//寻找Vertex在graph中VERTEX* tmp = first;if(p)*p = 0;while(tmp){if(tmp->start == start)return tmp;if(p)*p = tmp;tmp = tmp->next;}return 0;}//从某一个Vertex的Line表中，查找一个Line, 如果找到, p返回的就是该Line否则返回最后一个Line。LINE* findLine(LINE**p, LINE*first, int end){LINE* tmp = first;if(p) *p = 0;while(tmp){if(tmp->end == end)return tmp;if(p)*p = tmp;tmp = tmp->next;}return 0;}//增加一个Vertex到图中VERTEX* addVertexToGraph(int start){VERTEX*f = 0;if(!findVertex(&f, start)){if(f){f->next = createNewVertex(start);count++;return f->next;}else{first = createNewVertex(start);count++;return first;}}return 0;}LINE* addLineToVertex(LINE *l, VERTEX*v){//前提:l和v必须都存在.LINE* vl = v->first;LINE *p = v->first;if(!vl){v->first = l;}else{while(vl){p = vl;vl = vl->next;}p->next = l;}}//增加一条线到VertexLINE* addLineToVertex(int start, int end, int weight){VERTEX *v;LINE* resLine = 0;if(findVertex(&v, start)){LINE* f = 0;if(v){v = v->next;}else{v = first;}if(!findLine(&f, v->first, end)){if(f){f->next = createNewLine(end,weight);resLine = f->next;}else{v->first = createNewLine(end,weight);resLine = v->first;}v->lineNums++;if(kind == NG){//如果是无向图还需要反向来一次的说,这个不会形成无限递归的.addLineToVertex(end, start, weight);}}}return resLine;}//增加一个带有一条Line的节点, 只有带边的点，和孤独的点，却没有孤独的边。因此没有类似的addLine的函数。void addVertexWithLine(int start, int end, int weight){if(addVertexToGraph(start)){if(addLineToVertex(start, end, weight)){cout<<"addVertexWithLine sucess!"<<endl;}else{cout<<"addVertexWithLine error1"<<endl;}}else{cout<<"addVertexWithLine error2!"<<endl;}}//删除一条线，首先，在LINE中的链表中删除，然后在Vertex中删除void deleteLine(int start, int end){//只有知道边的2个端点才能唯一确定一条边//首先找到顶点VERTEX *v;if(findVertex(&v, start)){if(v){v = v->next;}else{v = first;}}deleteLine(v, end);}    //删除一条线，首先，在LINE中的链表中删除，然后在Vertex中删除void deleteLine(VERTEX*v, int end){//只有知道边的2个端点才能唯一确定一条边LINE*l;if(findLine(&l, v->first, end)){if(l){delete l->next;l->next = l->next->next;}else{LINE*f =  v->first;v->first = f->next;delete f;}v->lineNums--;}}void deleteAllLine(VERTEX*v){//只有知道边的2个端点才能唯一确定一条边LINE*l = v->first;while(l){LINE*tmp = l;l = l->next;delete tmp;}v->first = 0;v->lineNums = 0;}void deleteAllLine(int start){//只有知道边的2个端点才能唯一确定一条边//首先找到顶点VERTEX *v;if(findVertex(&v, start)){if(v){v = v->next;}else{v = first;}}deleteAllLine(v);}void deleteVertex(int start){VERTEX*v;if(findVertex(&v, start)){//首先删除从start点出发的LINEdeleteAllLine(start);//然后删除节点VERTEX*tmp = v->next;v->next = v->next->next;delete tmp;count--;//删除以start为终点的Lines.VERTEX* f = first;while(f){deleteLine(f, start);f = f->next;}}}//深度优先遍历。void DFS(VERTEX*v){v->visit();visitDFSArr[v->start] = true;LINE * l = v->first;while(l){VERTEX* pv;findVertex(&pv, l->end);if(pv){pv = pv->next;}else{pv = first;}if(!visitDFSArr[pv->start]) DFS(pv);l = l->next;}}void DFSTraversal(){delete visitDFSArr;visitDFSArr = new bool[count];//泄漏for(int i = 0; i < count; i++){visitDFSArr[i] = false;}VERTEX*v = first;while(v){if(!visitDFSArr[v->start]) DFS(v);v = v->next;}cout<<endl;}//广度优先遍历。广度优先遍历选择一个队列辅助操作还是比较合理的。略//最小生成树//prim算法: 条件是加权连通图。找出图的最小生成树。PrimTree getPrimPrimTree(int start){PrimTree p(start);if(visitDFSArr){delete []visitDFSArr;visitDFSArr = 0;}visitDFSArr = new bool[count];for(int i = 0; i < count; i++){visitDFSArr[i] = false;}p.insertVertex(start);//起点加入p.listvisitDFSArr[start] = true;while(p.list){//如果list为空则结束。每次循环增加一条线VERTEX* vlist = p.list;VERTEX* vp =0;//遍历当前list表找出最短的linePrimTreeLine* shortest = 0;//最短linewhile(vlist){//遍历p.list中的所有的点，在所有点中找到一个最短的路径。vp = findVertex(0, vlist->start);LINE* bianli = vp->first;//遍历linewhile(bianli){//遍历该点上的所有lineif(!visitDFSArr[bianli->end]){//这条LINE是合法的。if里面是判断它是否最短if(shortest){//如果shortest已经有值了。则判断if(bianli->weight < shortest->weight){shortest->start = vlist->start;shortest->end = bianli->end;shortest->weight = bianli->weight;}}else{//如果没有值，shortest被赋值为合法值shortest = new PrimTreeLine(vlist->start, bianli->end, bianli->weight);}}bianli = bianli->next;}if(!shortest){//这说明，某个点上没有找到可以用的LINE,那就应该删除这个点。p.deleteVertex(vp->start);}vlist = vlist->next;//下一个点}if(shortest){//cout<<"加入: "<<shortest->start<<"-"<<shortest->end<<"("<<shortest->weight<<")"<<endl<<endl;p.insertLine(shortest);p.insertVertex(shortest->end);visitDFSArr[shortest->end] = true;shortest = 0;}else{//cout<<"结束"<<endl;//break;}}if(visitDFSArr){delete []visitDFSArr;visitDFSArr = 0;}return p;}void qsort(kruskalLine **arr, int start, int end){if(end - start <= 0) return;int ps = start, pe = end;kruskalLine* mark = arr[start];while(end > start){while(end > start&& arr[end]->weight > mark->weight) end--;if(end > start){arr[start] = arr[end];start++;}while(end > start && mark->weight > arr[start]->weight) start++;if(end > start) {arr[end] = arr[start];end--;}}arr[start] = mark;qsort(arr, ps, start - 1);qsort(arr, start+ 1, pe);}kruskalTree getKruskalTree(){//1. init linesVERTEX* vcount = first;int linenums = 0;while(vcount){linenums += vcount->lineNums;vcount = vcount->next;}if(allLines) delete []allLines;allLines = new kruskalLine*[linenums];VERTEX* v = first;int li = 0;while(v){LINE*l = v->first;while(l){kruskalLine *k = new kruskalLine(v->start, l->end, l->weight);allLines[li++] = k;l = l->next;}v = v->next;}//2. sortfor(int i = 0; i < linenums; i++){cout<<allLines[i]->weight<<" ";}cout<<endl;qsort(allLines, 0, linenums-1);for(int i = 0; i < linenums; i++){cout<<allLines[i]->weight<<" ";}cout<<endl;//3. init TreeskruskalTree ** trees = new kruskalTree*[count];VERTEX* vs = first;int vi = 0;while(vs){trees[vi++] = new kruskalTree(vs->start);vs = vs->next;}cout<<"count = "<<count<<", vi = "<<vi<<endl;//4. select one line. attach two tree;for(int i = 0; i < linenums; i++){//a. 取出一条线kruskalLine * kl = allLines[i];cout<<"the selected line kl = ["<<kl->start<<","<<kl->weight<<","<<kl->end<<"]"<<endl;//b. 找出对应的2棵树int startTree = -1;int endTree = -1;kruskalVertex* findVstart = 0;kruskalVertex* findVend = 0;for(int i = 0; i < count; i++){if(trees[i]){if(!findVstart){findVstart = trees[i]->findVertex(trees[i]->root, kl->start) ;if(findVstart && trees[i]->root->root == findVstart->root){startTree = i;if(startTree == endTree){//说明这条Line的2个端点在同一棵树上，返回循环开始处。break;}}}if(!findVend){findVend = trees[i]->findVertex(trees[i]->root, kl->end) ;if(findVend && trees[i]->root->root == findVend->root){endTree = i;if(startTree == endTree){break;}}}}if(startTree != -1 && endTree != -1) break;}if(-1 == startTree || -1 == endTree) {cout<<"startTree =="<<startTree<<endl;cout<<"endTree =="<<endTree<<endl;break;}else if(startTree == endTree){cout<<"startTree == endTree == "<<startTree<<endl;continue;}//c. 合并2棵树//i>首先, endTree的root作为, findVstart的一个childkruskalVertex * child = findVstart->children;if(child){while(child->next) {child = child->next;}child->next = trees[endTree]->root;}else{findVstart->children = trees[endTree]->root;}//ii>把endTree的所有child的root变成 startTree的root, 在i>中完成kruskalVertex* endBL = trees[endTree]->root;while(endBL){endBL->root = findVstart->root;endBL = endBL->next;}//iii>把endTree的所有Line加入startTree中kruskalLine * klOfStartTree = trees[startTree]->first;kruskalLine * klOfEndTree = trees[endTree]->first;if(!klOfStartTree){trees[startTree]->first = klOfEndTree;} else {while(klOfStartTree->next){klOfStartTree = klOfStartTree->next;}klOfStartTree->next = klOfEndTree;}//iV>删除endTree节点。并把数组对应下标置空。delete trees[endTree];trees[endTree] = 0;//d. 把kl 加入到新树中if(klOfEndTree){while(klOfEndTree->next) klOfEndTree = klOfEndTree->next;klOfEndTree->next = kl;cout<<"kl加入到tree中 1"<<endl;}else{if(klOfStartTree){klOfStartTree->next = kl;}else{trees[startTree]->first = kl;}cout<<"kl加入到tree中 2"<<endl;}}//5. clean scenefor(int i = 0; i < count; i++){if(trees[i]) return *trees[i];}}
};//希望在构造图的时候应该先构造所有的点.
int main(){//GRAPH g(GRAPH::DG);GRAPH g(GRAPH::NG);//使用维基百科上prim词条中的图g.addVertexToGraph(1);g.addVertexToGraph(2);g.addVertexToGraph(3);g.addVertexToGraph(4);g.addVertexToGraph(5);g.addVertexToGraph(6);g.addVertexToGraph(7);g.addLineToVertex(1, 2, 7);g.addLineToVertex(1, 4, 5);g.addLineToVertex(2, 3, 8);g.addLineToVertex(2, 4, 9);g.addLineToVertex(2, 5, 7);g.addLineToVertex(3, 5, 5);g.addLineToVertex(4, 5, 15);g.addLineToVertex(4, 6, 6);g.addLineToVertex(5, 6, 8);g.addLineToVertex(5, 7, 9);g.addLineToVertex(6, 7, 11);cout<<g.count<<endl;g.DFSTraversal();/*g.deleteVertex(2);g.deleteVertex(3);g.DFSTraversal();*///prim算法PrimTree p = g.getPrimPrimTree(5);p.print();cout<<p.ln<<" "<<p.vn<<endl;cout<<"\n-----------------------------------"<<endl;//kruskal算法kruskalTree kt = g.getKruskalTree();kt.print();
}