graphlink.h

该代码为图的拓扑排序

#include<iostream>
#include<fstream>
#include<limits>
#include<vector>
#include<algorithm>

using namespace std;

//利用邻接表实现图的算法

#define MAX_VEX_NUM 10
#define INF  INT_MAX


typedef int VertexType;

struct ArcNode{ //单链表结点结构
     int    adjvex; //该弧所指向的顶点的位置
     ArcNode   *nextarc;//指向下一条弧的指针
     //InfoType     *info；      //该弧相关信息的指针
};


typedef struct  VNode{//顶点结构
      int   data;//顶点信息
      ArcNode    *firstarc; //指向第一条依附该顶点的弧的指针
	  int   indegree;//入度
}VNode,AdjList[MAX_VEX_NUM];

typedef struct { //邻接表结构
       AdjList    vertices;
       int    vexnum,arcnum;   //图的当前顶点数和弧数
}ALGraph;


class Graph{
  public:
    Graph();
    Graph(const char*);
    void degree(vector<int>&,vector<int>&);
    int order();
    int size();
    void output();
	void tpsort(vector<int>id);
	int printDegree (const vector<int>id, const vector<int>od);
  private:
    ALGraph g;
	int Matrix[MAX_VEX_NUM][MAX_VEX_NUM];
};

Graph::Graph()
{
	cout<<"请输入节点数：";
	cin>>g.vexnum;
	int m=0;
	for(int i=0;i<g.vexnum;i++)
	{
		g.vertices[i].data=i;
		ArcNode* p=new ArcNode();
	    g.vertices[i].firstarc=p;
		for(int j=0;j<g.vexnum;j++)
		{
			cout<<"Matrix["<<i<<']'<<'['<<j<<']'<<'=';
			cin>>Matrix[i][j];
			if(i==j && Matrix[i][j]!=0)
				Matrix[i][j]=0;
			if(Matrix[i][j]==1)
			{
				m++;
				p->adjvex=j;
                p->nextarc=new ArcNode();
				p=p->nextarc;
			}
			if(j==g.vexnum-1)
				p->nextarc=NULL;
		}
	}
  g.arcnum= m;
}

//**********************************************************
Graph::Graph(const char* f)
{
	ifstream in(f);
	int m=0;
	in>>g.vexnum;
	for(int i=0;i<g.vexnum;i++)
	{
		g.vertices[i].data=i;
		ArcNode* p=new ArcNode();
	    g.vertices[i].firstarc=p;
		for(int j=0;j<g.vexnum;j++)
		{
			in>>Matrix[i][j];
			if(i==j && Matrix[i][j]!=0)
				Matrix[i][j]=0;
			if(Matrix[i][j]==1)
			{
				m++;
				p->adjvex=j;
                p->nextarc=new ArcNode();
				p=p->nextarc;
			}
			if(j==g.vexnum-1)
				p->nextarc=NULL;
		}
	}
	g.arcnum = m;
}
//***********************************************************************
void Graph::degree(vector<int>& indeg,vector<int>& outdeg)
{
	for(int count=0;count<g.vexnum;count++)
	{
		indeg[count]=outdeg[count]=0;
	}
	for(int i=0;i<g.vexnum;i++)
	{
		for(int j=0;j<g.vexnum;j++)
		{
			if(Matrix[i][j]>0&&Matrix[i][j]<INF)
			{
				 indeg[j]++;
				 outdeg[i]++;
			}
		}
	}
}
//****************************************************************************
int Graph::order()
{
	return g.vexnum;
}
//****************************************************************************
int Graph::size()
{
	return g.arcnum;
}

//******************************************************************************
void Graph::output()
{
	cout<<"该图的邻接矩阵是："<<endl;
	for (int i=0;i<g.vexnum;i++)
	{
		for (int j=0; j<g.vexnum; j++)
		{
			cout<<Matrix[i][j]<<"  ";
		}
		cout<<endl;
	}
	cout<<"图的节点数为:"<<g.vexnum<<endl;
    cout<<"图的边数为:"<<g.arcnum<<endl;
	cout<<"该图的邻接表表示为："<<endl;
	for(int count=0; count<g.vexnum;count++)
	{
		cout<<g.vertices[count].data+1<<"->";
		ArcNode* p=g.vertices[count].firstarc;
        while(p->nextarc!=NULL)
		{
			if(p->nextarc->nextarc!=NULL)
			{
				cout<<p->adjvex+1<<"->";
			}
			else
                cout<<p->adjvex+1;
			p=p->nextarc;
		}
		cout<<endl;
	}
	cout<<endl;
}
//********************************************************************************
void Graph::tpsort(vector<int>id)//拓扑排序
{
	int top=-1,m=0,i,j;
	ArcNode *p=NULL;
	vector<int>::iterator it;
	for(i=0,it=id.begin();i<g.vexnum,it!=id.end();i++,it++)
	{
		g.vertices[i].indegree=*it;
	}
	for(i=0;i<g.vexnum;i++)
	{
		if(g.vertices[i].indegree==0)
		{
			g.vertices[i].indegree=top;
			top=i;
		}
	}
    cout<<endl;
	while(top!=-1)
	{
		m++;
		cout<<g.vertices[top].data+1<<" ";
		p=g.vertices[top].firstarc;
		top=g.vertices[top].indegree;
		while(p->nextarc!=NULL)
		{
			j=p->adjvex;
			g.vertices[j].indegree--;
			if(g.vertices[j].indegree==0)
			{
				g.vertices[j].indegree=top;
				top=j;
			}
			p=p->nextarc;
		}
	}
	if(m==g.vexnum)
	{
		cout<<"为拓扑序列."<<endl;
	}
	else
	{
		cout<<"拓扑序列不存在."<<endl;
	}
}
//**************************************************************************************
int Graph::printDegree (const vector<int>id, const vector<int>od)
{
	//输出入度和出度
	for(int i=0;i<id.size();i++)
	{
		cout<<"第 "<<i+1<<" 个节点的入度为: "<<id[i]<<endl;
	}
	for(int j=0;j<od.size();j++)
	{
		cout<<"第 "<<j+1<<" 个节点的出度为: "<<od[j]<<endl;
	}
    return 0;
}