拓扑排序（邻接表实现）

/**********************************
         title:   拓扑排序（邻接表实现）
         author:  jay chang
         date:    2009/07/16
**********************************/
#include<iostream>

#define MAXSIZE 99
#define TRUE 1
#define FALSE 0

using namespace std;

typedef char VertexData;
 
typedef int AdjType;

typedef struct Stack          //定义栈
{
  int data[MAXSIZE+1];
  int top;
}Stack;

typedef struct ArcNode		 //定义弧结点
{
  AdjType adj;
  ArcNode *nextArc;
}ArcNode;

typedef struct VertexNode    //定义顶点
{
  VertexData vertexData;
  ArcNode *firstArc;
}VertexNode;


typedef struct AdjMatrix     //定义图
{
  VertexNode vertexNodes[MAXSIZE+1];
  int verNum,arcNum;
}AdjMatrix;

//全局变量
int indegree[MAXSIZE+1]={0};

int LocateGraph(AdjMatrix *g, VertexData vertexData)
{
  int iIndex;
  for(iIndex=1;iIndex<=g->verNum;iIndex++)
  {
    if(vertexData==g->vertexNodes[iIndex].vertexData)
      return iIndex;
  }
  return FALSE;
}

void  CreateGraph(AdjMatrix *g)
{   
  int iCount,arcStart,arcEnd;char start,end;
  cout<<"*****************************************"<<endl;
  cout<<"***       拓扑排序\n";
  cout<<"***       Author: Jay Chang\n";
  cout<<"*****************************************"<<endl;
  cout<<"输入有向无环图的顶点,及弧数\n";
  cin>>g->verNum>>g->arcNum;
  cout<<"输入有向无环图的顶点信息\n";
  ArcNode *q=NULL;

  for(iCount=1;iCount<=g->verNum;iCount++)
  {    
	   cout<<"输入第"<<iCount<<"个顶点的信息"<<endl;
       cin>>g->vertexNodes[iCount].vertexData;
	   g->vertexNodes[iCount].firstArc=NULL;
  }

  for(iCount=1;iCount<=g->arcNum;iCount++)
  {
      cout<<"输入第"<<iCount<<"条弧的起始与结束的信息"<<endl;
      cin>>start>>end;

      arcStart=LocateGraph(g,start);
	  arcEnd  =LocateGraph(g,end);
	
	  //添加弧结点
      q=(ArcNode*)malloc(sizeof(ArcNode));
      q->adj=arcEnd;
      q->nextArc=g->vertexNodes[arcStart].firstArc;
      g->vertexNodes[arcStart].firstArc=q;
      //对于第arcEnd个顶点的入度值加1
	  indegree[arcEnd]++;
  }
}


//判栈空
int IsEmpty(Stack *stack)
{
  return stack->top==-1?TRUE:FALSE;
}

//初始化栈
void InitStack(Stack *stack)
{
  stack->top=-1;
}

//出栈
void Pop(Stack *stack,int *iIndex)
{
  *iIndex=stack->data[stack->top--];
}

//进栈
void Push(Stack *stack,int value)
{
  stack->data[++stack->top]=value;
}

//拓扑排序
int Tuopu(AdjMatrix *g)
{
  int iCount,count=0;
  Stack *stack=(Stack*)malloc(sizeof(Stack));
  InitStack(stack);
  ArcNode *p=NULL;

  //对于入度为0的顶点入栈
  for(iCount=1;iCount<=g->verNum;iCount++)
  {
    if(indegree[iCount]==0){
      Push(stack,iCount);
    }
  }

  cout<<"输出拓扑序列\n";
  
  //输出顶点后，将与该顶点相连的顶点的边删除，将与相连顶点的入度减1，如减后为0，入栈，栈空结束
  while(!IsEmpty(stack))
  {
    Pop(stack,&iCount);
    cout<<g->vertexNodes[iCount].vertexData<<" ";
    count++;
    p=g->vertexNodes[iCount].firstArc;
    while(p!=NULL)
    {	
		if(--indegree[p->adj]==0)
			Push(stack,p->adj);
		p=p->nextArc;
    }
  }//end while

  if(count<g->verNum){
    cout<<"有回路"<<endl;
    return FALSE;
  }
  cout<<endl;
}
   
int main()
{
    AdjMatrix *g=(AdjMatrix*)malloc(sizeof(AdjMatrix));
    CreateGraph(g);
    Tuopu(g);
    return 0;
}

 

评论

2 楼 jaychang 2010-07-15  

lixia0417 写道

不错，不过要是用java来描述就更好了

呵呵，有时间出个JAVA版的，敬请期待哈。。。

1 楼 lixia0417 2010-07-14  

不错，不过要是用java来描述就更好了