graph2.h

这个是我的大学作业哦 里面有些很经典的代码 出自清华大学的数据结构课本

#ifndef GRAPH2_H
#define GRAPH2_H
#include "Graph1.h"
#include<queue>
//*****************************************
template <class NameType, class DistType> 
Graph<NameType,DistType>::Graph(int sz = DefaultSize):
NumVertex(0),NumEdge(0),NodeTable(NULL),count1(NULL),count2(NULL) {
	int n,e,k,l;
	NameType name,tail,head;

	NodeTable = new Vertex<NameType,DistType>[DefaultSize];
	count1 = new int[DefaultSize];
	count2 = new int[DefaultSize];

	for(int j = 0; j < DefaultSize; j++)
	{
		count1[j]=0;
		count2[j]=0;
	}

	cout<<"输入顶点数\n";
	cin>>n;
	for(j = 0; j < n; j++)
	{
		cout<<"输入顶点名\n";
		cin>>name;
		InsertVertex(name);
	}
	cout<<"输入边数\n";
	cin>>e;
	for(j = 0; j < e; j++)
	{
		cout<<"输入尾和头\n";
		cin>>tail>>head;
		k = GetVertexPos(tail);    
		l = GetVertexPos(head);
		InsertEdge(k,l);
	}
}
//----------------------------------------------------------------------
template <class NameType,class DistType> 
int Graph<NameType,DistType>::GetVertexPos(const NameType &vertex) {
	for(int i = 0 ; i< NumVertex; i++)
	{
		if(NodeTable[i].data==vertex)  return i;
	}
	return -1;
}
//--------------------------------------------------------------------
template <class NameType,class DistType> 
void Graph<NameType,DistType>::InsertVertex(NameType& vertex) {
	NodeTable[NumVertex].data = vertex;
	NumVertex++;
}
//插入的结点类型决定搜索的结点类型

template <class NameType,class DistType>
void Graph<NameType,DistType>::InsertEdge(int v1,int v2) {
	Edge<DistType> *q = new Edge<DistType>;
	q->Value(v2);
	//Edge<DistType>*p = q->Getlink(); 
	q->link = NodeTable[v1].adj;
	NodeTable[v1].adj = q;

	count1[v2]++;//indegree
	count2[v1]++;//outdegree
}
//-------------------------------------------------------------------
template <class NameType,class DistType>
void Graph<NameType,DistType>::Count() {
	for(int i=0; i<DefaultSize; i++)
	{
		cout<<"顶点"<<NodeTable[i].data<<"的入度为"<<count1[i]<<endl;
		cout<<"顶点"<<NodeTable[i].data<<"的出度为"<<count2[i]<<endl;
	}
}
//-----------------------------------------------------------------------------
template <class NameType,class DistType>
int Graph<NameType,DistType>::GetFirstNeighbor(int v) {
	if(v!=-1)
	{
		Edge<DistType>*p = new Edge<DistType>;
		p=NodeTable[v].adj;
		if(p!=NULL)
		{
			int t=p->Getdest();
			return t;
		}
	}
	return -1;
}

template <class NameType,class DistType>
int Graph<NameType,DistType>::GetNextNeighbor(int v1,int v2) {
	if(v1!=-1)
	{
		Edge<DistType>*p = NodeTable[v1].adj;
		while(p!=NULL)
		{
			if(p->Getdest()==v2&&p->Getlink()!=NULL)
			{
				p=p->Getlink();
				int c=p->Getdest();
				return c;
			}
			else p=p->Getlink();
		}
	}
	return -1;
}
//----------------------------------------------------------------
template <class NameType,class DistType>
void Graph<NameType,DistType>::DFS() {
	int *visited=new int[DefaultSize];
	for(int z=0;z<DefaultSize;z++)visited[z]=0;
	DFS(0,visited);
	delete[]visited;
}

template <class NameType,class DistType>
void Graph<NameType,DistType>::DFS(int v,int visited[]) {
	cout<<NodeTable[v].data<<" ";
	visited[v]=1;
	int w=GetFirstNeighbor(v);
	while(w!=-1)
	{
		if(!visited[w])DFS(w,visited);
		w=GetNextNeighbor(v,w);
	}
}
//-----------------------------------------------------------
template <class NameType,class DistType>
void Graph<NameType,DistType>::BFS(int v) {
	int *visited=new int[DefaultSize];
	for(int z=0;z<DefaultSize;z++)visited[z]=0;
	cout<<NodeTable[v].data<<" ";
	visited[v]=1;
	queue<int>q;
	q.push(v);
	int x=0;
	while(!q.empty())
	{
		x=q.front();
		q.pop();
		int w=GetFirstNeighbor(x);
		while(w!=-1)
		{
			if(!visited[w])
			{
				cout<<NodeTable[w].data<<" ";
				visited[w]=1;
				q.push(w);
			}
			w=GetNextNeighbor(x,w);
		}
	}
	delete[]visited;
}
//---------------------------------------------------------
template <class NameType,class DistType>
void Graph<NameType,DistType>::TopologicalSort() {
	int top = -1;
	for(int i = 0; i < DefaultSize; i++)
	{
		if(count1[i]==0)
		{
			count1[i] = top;
			top = i;
		}
	}
	for(i = 0; i < DefaultSize; i++)
	{
		if(top==-1)cout<<"NetWork has a cycle\n";
		else
		{
			int j = top;
			top = count1[top];
			cout<<NodeTable[j].data<<endl;
			Edge<DistType> *l = NodeTable[j].adj;
			while(l)
			{
				int k = l->Getdest();
				if(--count1[k]==0)
				{
					count1[k]=top;
					top=k;
				}
				l = l->Getlink();
			}
		}
	}
}

#endif