lx.cpp

vc编写的数据结构

// lx.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
//#include "lxastack.h"
#include "lxlstack.h"
//#include "lxaqueue.h"
#include "lxlqueue.h"
//#include "lxbst.h"
#include "lxgraphl.h"
#include <iostream.h>
//--------------------深度优先函数-------------------------------------
void DSF(lxgraphl* g,int v){
	g->setmark(v,1);
	cout<<v<<" ";
	for(int w=g->first(v);w<g->n();w=g->next(v,w))
		if(g->getmark(w)==0)
			DSF(g,w);
}
//--------------------广度优先函数-------------------------------------
void BFS(lxgraphl* g,int start){
	lxlqueue* q;
	q=new lxlqueue(1);
	int v,w;
	q->enqueue(start);
	g->setmark(start,1);
	while(q->length()!=0){
		q->dequeue(v);
		cout<<v<<" ";
		for(w=g->first(v);w<g->n();w=g->next(v,w))
			if(g->getmark(w)==0) {
				g->setmark(w,1);
				q->enqueue(w);
			}
	}
	cout<<endl;
}
//--------------------重载广度优先函数-------------------------------------
int BFS(lxgraphl* g,int start,int k){
	int count=0;
	lxlqueue* q;
	q=new lxlqueue(1);
	int v,w;
	q->enqueue(start);
	g->setmark(start,1);
	while(q->length()!=0){
		q->dequeue(v);
		count++;
		for(w=g->first(v);w<g->n();w=g->next(v,w))
			if(g->getmark(w)==0) {
				g->setmark(w,1);
				q->enqueue(w);
			}
	}
	return count;
}
//--------------------------计算连通分量并输出相映结点---------------------
int count(lxgraphl* g){
	int count=0;
	for(int i=0;i<g->n();i++)
		if(g->getmark(i)==0){
			BFS(g,i);
			count++;
		}
	return count;
}
//-----------------prim算法--------------------------------
void prim(lxgraphl* g,int s,int num){

	int tw,tv,ti;
	g->setmark(s,100);
	while(num-1>0){
		tw=1000;
		for(int i=0;i<g->n();i++)
			if(g->getmark(i)==100)
				for(int w=g->first(i);w<g->n();w=g->next(i,w))
					if((tw>g->weight(i,w))&&(g->getmark(w)!=100)){
						tw=g->weight(i,w);
						tv=w;
						ti=i;}
		cout<<"wight("<<ti<<","<<tv<<")="<<tw<<"\n";
		g->setmark(tv,100);
		num--;
	}

}
//----------------输出各连通分量的MST-----------------------------------
void print(lxgraphl* g){
    int i,num,c=0;
	for(i=0;i<g->n();i++)
		g->setmark(i,0);

	for(i=0;i<g->n();i++)
		if(g->getmark(i)==0){
			num=BFS(g,i,0);
			if(num==1)cout<<i<<endl<<endl;
			else {prim(g,i,num);
			cout<<endl;}
		}	
}

int main(int argc, char* argv[])
{
	int i;
	lxgraphl* a;
	a=new lxgraphl(8);
	a->setedge(0,2,7);
	a->setedge(1,2,5);
	a->setedge(2,3,1);
	a->setedge(1,5,6);
	a->setedge(3,5,2);
	a->setedge(0,4,9);
	a->setedge(4,5,1);
	a->setedge(2,5,2);
	a->setedge(6,7,1);
	cout<<"节点数："<<a->n()<<endl;

	cout<<"边数："<<a->e()<<endl;

	cout<<"深度优先搜索: ";
	DSF(a,0);

	for(i=0;i<a->n();i++)
		a->setmark(i,0);
	cout<<"\n广度优先搜索: ";
	BFS(a,0);

	for(i=0;i<a->n();i++)
		a->setmark(i,0);
	cout<<"\n计算连通分量： \n";
	cout<<"连通分量为 "<<count(a);

	cout<<endl<<"最小生成树：\n";
	print(a);

	return 0;
}