#include<iostream>
#include<stdio.h>
#include "Stack.h"
#define Status int
#define MAXVEX 100
#define OK 0
#define ERROR -1
using namespace std;
typedef struct EdgeNode /*边结点*/
{
int adjvex;//邻接点域，存储该顶点对应的下标
struct EdgeNode *next;//指向下一条弧的指针
}EdgeNode;
typedef struct VertexNode /*顶点表结点*/
{
int in; //顶点的入度
char data; //顶点域，存储顶点信息
EdgeNode *firstedge;//边表头指针
}VertexNode, AdjList[MAXVEX];
typedef struct //图结构
{
AdjList adjList; //邻接表
int numVertexes, numEdges; //顶点数和弧数
}ALGraph;
//找到顶点所在数组的位置
int LocateVex(ALGraph G,char v){
for(int i = 0; i<G.numVertexes; ++i){ //头结点表
if( G.adjList[i].data==v){
return i;
} //输入顶点值
}
return ERROR;
}
Status CreateUDG(ALGraph &G){//采用邻接表表示法，创建无向图G
cout<<"输入图的顶点数目和边的数目：";
char v1,v2;
EdgeNode *p1;
int i,j;
cin>>G.numVertexes;
cin>>G.numEdges; //输入总顶点数，总边数
cout<<"输入图的顶点：";
for(int m=0; m<G.numVertexes; ++m){ //输入各点，构造头结点表
cin>> G.adjList[m].data; //输入顶点值
G.adjList[m].firstedge=NULL; //初始化表头结点的指针域为NULL
G.adjList[m].in=0;
}
//for
cout<<"按方向输入图的边的关联的两个顶点：";
for(int k = 0; k<G.numEdges;++k){ //输入各边，构造邻接表
cin>>v1>>v2; //输入一条边依附的两个顶点v1->v2
i = LocateVex(G, v1); //找到顶点所在的位置
j = LocateVex(G, v2);
//将新结点*p1插入顶点vi的边表头部
p1=new EdgeNode; //生成一个新的边结点*p1
p1->adjvex=j; //邻接点序号为j
p1->next= G.adjList[i].firstedge;
G.adjList[i].firstedge=p1;
//v2入度加一
G.adjList[j].in++;
}//for
return OK;
}//CreateUDG
//拓扑排序，若GL无回路，则输出拓扑排序序列并返回OK，若有回路返回ERROR
Status TopologicalSort(ALGraph GL) {
Stack s;
EdgeNode *e;
int i, k, gettop;
int count=0;//用于统计输出顶点的个数
for(i=0;i<GL.numVertexes; i++)
if(GL.adjList[i].in==0)
s.push(i); //将入度为0的顶点的下标入栈
while(s.isEmpty()==false)//栈不是空的时候
{
gettop=s.pop();//得到栈顶中顶点的下标
//cout<<s.pop()<<" "; //打印此顶点
cout<<GL.adjList[gettop].data<<" "; //打印此顶点
// cout<<GL.adjList[0].data<<" "; //打印此顶点
count++;//顶点数加一
e=GL.adjList[gettop].firstedge;//得到该顶点的第一条边
while(e!=NULL)
{
//cout<<"进入"<<" "; //打印此顶点
k=e->adjvex;//得到第一个对应的顶点数组下标
GL.adjList[k].in--;
int n= GL.adjList[k].in;
if(n==0)//将k号顶点邻接点的入度减1
s.push(k);//若为0，则入栈
e=e->next;
}
}
if (count< GL.numVertexes)
return ERROR;
else
return OK;
}
int main(){
ALGraph G;
CreateUDG(G);
TopologicalSort(G);
}
//栈文件
#ifndef STACK_H_INCLUDED #define STACK_H_INCLUDED #define MAX 100 class Stack{ private: int s[MAX]; int head; public: //初始化栈 Stack(){ head = 0; } //出栈 int pop(){ char t; if(head>0){ t = s[--head];//先减,后pop } return t; } //入栈 void push(int value){//后加 s[head++] = value; } //栈是否为空 bool isEmpty(){ if(head==0) return true; return false; } }; #endif // STACK_H_INCLUDED
