graph.h

该压缩文件夹内有诸多常用算法和数据结构的c++模板编程实现

#ifndef GRAPH_H
#define GRAPH_H
#include<iostream.h>
#include"lStack.h"
//------------------------------表节点类-------------------------------------------------------------------------
template<class T>
class graphicNode
{
public:
	int hNode;
	int weight;
	graphicNode<T>* next;
	graphicNode(int el,int po,graphicNode<T>* p=NULL)
	{
		hNode=el;
		next=p;
		weight=po;
	}
};
//------------------------------头节点类-----------------------------------------------------------------
template<class T>
class headNode
{
public:
	T info;
	graphicNode<T>* next;
	headNode(T el,graphicNode<T>* p=NULL)
	{
		info=el;
		next=p;
	}
};
//---------------------------------边类--------------------------------------------------------------
class edge
{
public:
	int node1;
	int weight;
	int	node2;
	edge(int a=0,int b=0,int c=0)
	{
		node1=a;
		weight=b;
		node2=c;
	}
};
//--------------------------简单图类-------------------------------------------------------------
template<class T>
class Graph						
{
private:
	headNode<T>* nodes[20];
	int count;
public:
	Graph(int a=0)		{count=a;}
	void insertV(T el)				//适合所有种类的图
	{
		nodes[count]=new headNode<T>(el);
		count++;
	}
	void insertE(edge e)			//适合无向图
	{
		nodes[e.node2]->next=new graphicNode<T>(e.node1,e.weight,nodes[e.node2]->next);
		nodes[e.node1]->next=new graphicNode<T>(e.node2,e.weight,nodes[e.node1]->next);		
	}
	void delE(edge e)				//适合的图同上
	{
		graphicNode<T> *p1=NULL,*p2=NULL;
		for(p2=p1=nodes[e.node1]->next;p1->hNode!=e.node2;p2=p1,p1=p1->next);
			if(p1==p2)
			{
				nodes[e.node1]->next=p1->next;
				delete p1;
			}
			else
			{
				p2->next=p1->next;
				delete p1;
			}
		for(p2=p1=nodes[e.node2]->next;p1->hNode!=e.node1;p2=p1,p1=p1->next);
			if(p1==p2)
			{
				nodes[e.node2]->next=p1->next;
				delete p1;
			}
			else
			{
				p2->next=p1->next;
				delete p1;
			}
	}
	void delV(T el)					//适合的图同上
	{
		edge e[20];
		int j=0;
		for(int i=0;nodes[i]->info!=el&&i<count;i++);
		for(graphicNode<T>* p=nodes[i]->next;p!=NULL;p=p->next,j++)
		{
			e[j].node1=i;
			e[j].node2=p->hNode;
			e[j].weight=p->weight;
		}
		for(i=0;i<j;i++)
			delE(e[i]);
		for(i=e[0].node1;i<count-1;i++)
			nodes[i]=nodes[i+1];
		count--;
	}
	void print()				//适合所有种类的图
	{
		for(int i=1;i<=count;i++)
		{
			cout<<i-1<<" "<<nodes[i-1]->info;
			for(graphicNode<T>* p=nodes[i-1]->next;p!=NULL;p=p->next)
				cout<<"->"<<p->hNode<<" "<<p->weight;
			cout<<endl;
		}
	}
	bool isCircle()				// 适合分离，连通，有向和无向的简单图
	{
		graphicNode<T>* p2=NULL;
		int k=0;
		edge e[380];
		edge tmp;
		lStack<graphicNode<T>*> a;
		bool v[20]={0};
		bool m;
		for(int i=1;i<=count;i++)
		{
			for(int i2=0;i2<=19;i2++)
				v[i2]=0;
			k=0;
			for(graphicNode<T>* p=nodes[i-1]->next;p!=NULL;p=p->next)
			{
				a.push(p);
				v[i-1]=1;
				e[k].node1=i-1;
				e[k].node2=p->hNode;
				e[k].weight=p->weight;
				k++;
			}
			while(!a.isEmpty())
			{
				p2=a.pop();
				if(v[p2->hNode]==1)
					return true;
				else v[p2->hNode]=1;
				for(graphicNode<T>* p=nodes[p2->hNode]->next;p!=NULL;p=p->next)
				{
					m=0;
					tmp.node1=p2->hNode;
					tmp.node2=p->hNode;
					tmp.weight=p->weight;
					for(int j=0;j<k;j++)
						if(tmp.node1==e[j].node2&&tmp.node2==e[j].node1)
						{
							m=1;
							break;
						}
					if(m==0)
					{
						e[k]=tmp;
						a.push(p);
						k++;
					}
				}
			}
		}
		return false;
	}
	bool isSeparate()					//适合的图同上
	{
		lStack<graphicNode<T>*> a;
		graphicNode<T>* p1=NULL;
		int b[20]={0};
		b[0]=1;
		for(graphicNode<T>* p=nodes[0]->next;p!=NULL;p=p->next)
			a.push(p);
		while(!a.isEmpty())
		{
			p1=a.pop();
			if(b[p1->hNode]==0)
			{
				for(p=nodes[p1->hNode]->next;p!=NULL;p=p->next)
					if(b[p->hNode]==0)
						a.push(p);
				
				b[p1->hNode]=1;
			}
		}
		for(int i=0;b[i]==1;i++);
		if(i<count)
			return true;
		else return false;
			
	}
	void KruskalTree()						//适合连通无向简单图
	{
		edge s[380],tmp;
		graphicNode<T> *p1=NULL,*p2=NULL;
		int j=0,i;
		for( i=1;i<=count;i++)
			for(graphicNode<T>* p=nodes[i-1]->next;p!=NULL;p=p->next)
			{
				s[j].node1=i-1;
				s[j].node2=p->hNode;
				s[j].weight=p->weight;
				j++;
			}
		for(i=0;i<j-1;i++)
			for(int k=i+1;k<=j-1;k++)
				if(s[i].weight>s[k].weight)
				{
					tmp=s[i];
					s[i]=s[k];
					s[k]=tmp;
				}
		for(i=1;i<=count;i++)
		{
			for(p1=nodes[i-1]->next;p1!=NULL;1)
			{
				p2=p1;
				p1=p1->next;
				delete p2;
			}
			nodes[i-1]->next=NULL;
		}
		for(i=0;i<=j-1;i+=2)
		{
			insertE(s[i]);
			if(isCircle())
				delE(s[i]);
		}
	}
	void rebourKruskalTree()				//适合的图同上
	{
		edge s[380],tmp;
		int j=0,i;
		for( i=1;i<=count;i++)
			for(graphicNode<T>* p=nodes[i-1]->next;p!=NULL;p=p->next)
			{
				s[j].node1=i-1;
				s[j].node2=p->hNode;
				s[j].weight=p->weight;
				j++;
			}
		for(i=0;i<j-1;i++)
			for(int k=i+1;k<=j-1;k++)
				if(s[i].weight<s[k].weight)
				{
					tmp=s[i];
					s[i]=s[k];
					s[k]=tmp;
				}
		for(i=0;i<=j-1;i+=2)
		{
			delE(s[i]);
			if(isSeparate())
				insertE(s[i]);
		}
	}
};
#endif