toposortofgraph.cpp

关于数据结构的各章节的c原代码实现

// toposortofgraph.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdlib.h>
#include <stdio.h>
#define  MAX 20
typedef struct node
{
	int vertex;
	struct node* next;
}vnode;
typedef vnode* link;
vnode head[8];
int queue[MAX];
int front=-1;
int rear=-1;
int enqueue(int value)
{ 
   if(rear+1==front||(rear==(MAX-1)&&front<=0))return -1;
   rear++;
   if(rear==MAX)rear=0;
   queue[rear]=value;
}
int dequeue()
{
	if(front==rear)return -1;
	front++;
	if(front==MAX)front=0;
	return queue[front];
}
void creategraph(int *node,int num)
{
  int from,to;
  link newnode,p;
  for (int i=0;i<num;i++)
  {
	  from=node[2*i];
	  to=node[2*i+1];
	  head[to].vertex++;
      newnode=(link)malloc(sizeof(vnode));
	  newnode->vertex=to;
	  newnode->next=NULL;
      p=&(head[from]);
	  while (p->next!=NULL)
	  { 
		  p=p->next;
	  }
	  p->next=newnode;
  }
}
int toposort(link head,int num)
{ 
  link p;
  for (int i=1;i<num;i++)
  if(head[i].vertex==0)enqueue(i);
  while ((i=dequeue())!=-1)
  {
	  printf("%d",i);
	  p=head[i].next;
	  while (p!=NULL)
	  {   
		  i=p->vertex;
		  head[i].vertex--;
		  if(head[i].vertex==0)enqueue(i);
		  p=p->next;

	  }

  }
  printf("\n");
  for(i=1;i<num;i++)
	  if(head[i].vertex!=0)
		  return 1;
	  return 0;
}
int main(int argc, char* argv[])
{   
	link p;
	int node[10][2]={{3,2},{2,1},{2,5},{2,6},{1,4},{5,4},{7,4},{6,7},{5,6},{7,5}};
	for (int i=1;i<8;i++)
	{
		head[i].vertex=0;
		head[i].next=NULL;
	}
	creategraph(node[0],10);
	printf("含入度的邻接表内容：\n");
	for (i=1;i<8;i++)
	{
		printf("顶点[%d]度%d",i,head[i].vertex);
		p=head[i].next;
		while (p!=NULL)
		{
			printf("=>%d",p->vertex);
			p=p->next;
		}
     printf("\n");
	}
printf("拓扑排序的内容：\n");
if(toposort(head,8))
 printf("图有回路\n");
else
    printf("图没有回路\n");
	return 0;
}