拓扑排序（基于邻接表实现）

#include <iostream>#include <stack> using namespace std;#define MAX 100typedef char VertexType; typedef struct ArcNode { int adjvex;//邻接点域,存储该弧指向顶点的下标 (终点） struct ArcNode *next;//指向下一条弧的指针 int weight;//权重 }ArcNode;//边结构 typedef struct VertexNode {VertexType data;//数据域 ArcNode *firstArc;//指向第一条依附该顶点的弧的指针 }VertexNode,AdjVerList[MAX];typedef struct {AdjVerList vertices;//顶点集int vexnum,arcnum;//图的顶点数和弧数}ALGraph;//图结构int indegree[MAX];//每个顶点对应的入度数组 void CreateALGraph(ALGraph *G);void Display(ALGraph *G);int TopoSort(ALGraph *G);//a b c d e f g h i /*a c 0a h 0b c 0b d 0b e 0c d 0d f 0d g 0e f 0h i 0i g 0*/int main(){ALGraph G;CreateALGraph(&G);//Display(&G);TopoSort(&G);return 0;}//求顶点位置函数int LocateVex(ALGraph *G,VertexType v){int i;for(i=0;i<G->vexnum;i++){if(G->vertices[i].data == v)return i;}return -1;}//有向无环图 void CreateALGraph(ALGraph *G){VertexType v1,v2;int w;ArcNode *Arc;cout<<"请输入顶点数和边数：";cin>>G->vexnum>>G->arcnum;cout<<"请输入各顶点的数据:";for(int i=0;i<G->vexnum;i++){cin>>G->vertices[i].data;G->vertices[i].firstArc = NULL;//顶点的边表设为空}cout<<"请依次输入"<<G->arcnum<<"组边对应的两个顶点以及权值,以空格分割:"<<endl;for(int k=0;k<G->arcnum;k++) {cin>>v1>>v2>>w;int i = LocateVex(G,v1);int j = LocateVex(G,v2);Arc = new ArcNode;//新建边Arc->adjvex = j;Arc->weight = w;Arc->next = G->vertices[i].firstArc;G->vertices[i].firstArc = Arc;}}void Display(ALGraph *G){ArcNode *p;cout<<"编号，， 顶点， 相邻边的顶点\n";for(int i=0;i<G->vexnum;i++){cout<<i<<"\t"<<G->vertices[i].data;for(p=G->vertices[i].firstArc;p!=NULL;p=p->next)cout<<"\t"<<p->adjvex;cout<<endl;}}//求各顶点的入度（遍历整个邻接表）void FindIndegree(ALGraph *G){int i;ArcNode *p;//初始化每个顶点的入度为0for(i=0;i<G->vexnum;i++)indegree[i] = 0;for(i=0;i<G->vexnum;i++){p = G->vertices[i].firstArc;while(p){//将每一个临接到的点（终点）自增indegree[p->adjvex]++;p = p->next;}//cout<<i<<"元素的入度为："<<indegree[i]<<endl;} } //返回值的失败与否代表该有向图是否存在回路//拓扑排序 int TopoSort(ALGraph *G){cout<<"该有向图的一种拓扑排序结果为："<<endl; stack<int> s;//设置辅助栈，避免重复检测入度为0的顶点ArcNode *p;int i,k;FindIndegree(G);for(i=0;i<G->vexnum;i++){//将入度为0的顶点入栈if(indegree[i]==0)s.push(i); }int count = 0;while(!s.empty()){i = s.top();s.pop();cout<<G->vertices[i].data<<" "; //将栈顶出栈并打印count++;//统计已输出的顶点数p = G->vertices[i].firstArc;while(p!=NULL){k = p->adjvex;indegree[k]–;//i号顶点已出栈，所以将i号顶点的每个邻接点的入度自减if(indegree[k]==0)s.push(k);//如果入度减为0，则入栈p = p->next; }}if(count<G->vexnum)return -1;//存在回路 elsereturn 0;}

等待故人的归来。山上的树，大多数是松树比较突出。