graph.h

实现了图的主要操作:（1）分别用邻接矩阵和邻接表实现图的基本操作（包括图的广度和深度优先搜索）；(2）判断该图是否连通

#include "list.h"
#include <iostream>
using namespace std;

class Edge
{
public:
	int vertex,weight;
	Edge(int v=-1,int w=-1)
	{
		vertex = v;
		weight = w;
	}
};

class Graph
{
	public:
		Graph(int );
		~Graph();
		int n(){return cntV;}
		int e(){return cntE;}
		int first(int i)
		{
			Edge it;
			vertex[i].setStart();
			if(vertex[i].getValue(it)) return it.vertex;
			else return cntV;
		}
		int next(int v1,int v2)
		{
			Edge it;
			vertex[v1].getValue(it);
			if(it.vertex == v2) vertex[v1].next();
			else 
			{
				vertex[v1].setStart();
				while(vertex[v1].getValue(it) && it.vertex <= v2)
				{
					vertex[v1].next();
				}
			}
			if(vertex[v1].getValue(it)) return it.vertex;
			else return cntV;
		}
		void setEdge(int v1,int v2,int w)
		{
			Edge it(v2,w);
			Edge cur;
			vertex[v1].getValue(cur);
			if(cur.vertex != v2)
			{
				for(vertex[v1].setStart();vertex[v1].getValue(cur);vertex[v1].next())
				{
					if(cur.vertex >= v2) break;
				}
			}
			if(cur.vertex == v2) vertex[v1].remove(cur);
			else cntE++;
			vertex[v1].insert(it);
		}
		void delEdge(int v1,int v2)
		{
			Edge cur;
			vertex[v1].getValue(cur);
			if(cur.vertex != v2)
			{
				for(vertex[v1].setStart();vertex[v1].getValue(cur);vertex[v1].next())
				{
					if(cur.vertex >= v2) break;
				}
			}
			if(cur.vertex == v2)
			{
				vertex[v1].remove(cur);
				cntE--;
			}
		}
		int weight(int v1,int v2)
		{
			Edge cur;
			vertex[v1].getValue(cur);
			if(cur.vertex != v2)
			{
				for(vertex[v1].setStart();vertex[v1].getValue(cur);vertex[v1].next())
				{
					if(cur.vertex >= v2) break;
				}
			}
			if(cur.vertex == v2)
			{
				return cur.weight;
			}
			else return 0;
		}
		void DFS(int v1)
		{
			for(int i=0;i<cntV;i++)
			{
				mark[i] = 0;
			}
			mark[v1] = 1;
			cout << "深度优先搜索访问顺序: " ;
			cout << v1 ;
			_DFS(v1);
			cout << endl;
		}
		void BFS(int v1)
		{
			int i,front,rear,t;
			int *q;
			q = new int[cntV];
			front=1;rear=0;
			q[0] = v1;
			for(i=0;i<cntV;i++) mark[i] = 0;
			mark[v1] = 1;
			cout << "广度优先搜索访问顺序: " ;
			while(front > rear)
			{
				t = front;
				for(i=rear;i<t;i++)
				{
					cout << q[i] << " " ;
					for(int v = first(q[i]); v!=cntV; v=next(q[i],v))
					{
						if(!mark[v])
						{
							mark[v] = 1;
							q[front++] = v;
						}
					}
				}
				rear = t;
			}
			cout << endl;
		}
		int cntC()
		{
			int i,cnt=0;
			for(i=0;i<cntV;i++)
				mark[i] = 0;
			for(i=0;i<cntV;i++)
			{
				if(!mark[i])
				{
					cnt++;
					_cntC(i);
				}
			}
			return cnt;
		}
		void prim()
		{
			const int MAX = 99999999;
			int * path = new int [cntV];
			int * value = new int [cntV];
			int * level = new int[cntV];
			int tmp,i,j,p,v,min,cntlevel=0,from;
			for(i=0;i<cntV;i++)
			{
				mark[i] = 0;
				path[i] = -1;
				value[i] = MAX;
				level[i] = -1;
			}
			for(v=0;v<cntV;v++)
			{
				if(!mark[v])
				{
					cntlevel++;
					level[v] = cntlevel;
					while(1)
					{
						min = MAX; p = -1;
						for(j=0;j<cntV;j++)
						{
							if(level[j]==cntlevel)
							{
								//cout << "----" << j << endl;
								for(i=first(j);i!=cntV;i=next(j,i))
								{	
									if(!mark[i])
									{
										tmp = weight(j,i);
										if(tmp<min) 
										{
											min = tmp;
											from = j;
											p = i;
										}
									}
								}
							}
						}
						if(p!=-1)
						{
							mark[p]=1;
							path[p]=from;
							level[p]=cntlevel;
						}
						else break;	
					}
				}
			}
			for(i=1;i<=cntlevel;i++)
			{
				cout << "第" << i << "个连通分量的最小生成树" << endl;
				for(j=0;j<cntV;j++)
				{
					if(level[j]==i && path[j]!= -1)
					{
						cout << "(" << path[j] << "," << j << ")" << endl;
					}
				}
			}
		}
	private:
		int cntV,cntE;
		int *mark;
		mylist<Edge> * vertex;
		void _DFS(int v1)
		{
			for(int v = first(v1); v != cntV; v = next(v1,v))
			{
				if(!mark[v])
				{
					cout << " ->" << v;
					mark[v] = 1;
					_DFS(v);
				}
			}
		}
		void _cntC(int v1)
		{
			for(int v = first(v1); v != cntV; v = next(v1,v))
			{
				if(!mark[v])
				{
					mark[v] = 1;
					_cntC(v);
				}
			}
		}
};

Graph::Graph (int totalV)
{
	int i;
	cntV = totalV;
	cntE = 0;
	mark = new int[cntV];
	for(i=0;i<cntV;i++) 
	{
		mark[i] = 0;//0 unvisited 1 visited;
	}
	vertex = new mylist<Edge> [cntV];
}
Graph::~Graph()
{
	delete []mark;
	delete []vertex;
}