。。。
#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 end
struct 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;
}
//建立一条新的Line
LINE* createNewLine(int end, int weight){//建立一个新LINE
return new LINE(end,weight);
}
//建立一个新的Vertex
VERTEX* createNewVertex(int start){//创建新Vertex
return 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;
}
}
//增加一条线到Vertex
LINE* 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点出发的LINE
deleteAllLine(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.list
visitDFSArr[start] = true;
while(p.list){//如果list为空则结束。每次循环增加一条线
VERTEX* vlist = p.list;
VERTEX* vp =0;//遍历当前list表找出最短的line
PrimTreeLine* shortest = 0;//最短line
while(vlist){//遍历p.list中的所有的点，在所有点中找到一个最短的路径。
vp = findVertex(0, vlist->start);
LINE* bianli = vp->first;//遍历line
while(bianli){//遍历该点上的所有line
if(!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 lines
VERTEX* 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. sort
for(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 Trees
kruskalTree ** 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的一个child
kruskalVertex * 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 scene
for(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();
}
没有考虑优化问题，有内存泄漏的可能。
有时空复杂度不佳的可能。