应用拓扑排序算法求得的是什么序列

数据结构（C语言版） 图的遍历和拓扑排序

#include #include #include /* malloc()等*/ #include /* INT_MAX 等*/ #include /* EOF(=^Z 或F6),NULL */ #include /* atoi() */ #include /* eof() */ #include /* floor(),ceil(),abs() */ #include /* exit() */ /* 函数结果状态代码*/ #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 /*...全部

  #include #include #include /* malloc()等*/ #include /* INT_MAX 等*/ #include /* EOF(=^Z 或F6),NULL */ #include /* atoi() */ #include /* eof() */ #include /* floor(),ceil(),abs() */ #include /* exit() */ /* 函数结果状态代码*/ #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 /* #define OVERFLOW -2 因为在math。
  h 中已定义OVERFLOW 的值为3,故去掉此行*/ typedef int Status; /* Status 是函数的类型,其值是函数结果状态代码，如OK 等*/ typedef int Boolean; Boolean 是布尔类型,其值是TRUE 或FALSE */ /* 。
  。。。。。。。。。。。。。。。。。。。。。。。。*/ #define MAX_VERTEX_NUM 20 typedef enum{DG,DN,AG,AN}GraphKind; /* {有向图,有向网,无向图,无向网} */ typedef struct ArcNode { int adjvex; /* 该弧所指向的顶点的位置*/ struct ArcNode *nextarc; /* 指向下一条弧的指针*/ InfoType *info; /* 网的权值指针） */ }ArcNode; /* 表结点*/ typedef struct { VertexType data; /* 顶点信息*/ ArcNode *firstarc; /* 第一个表结点的地址,指向第一条依附该顶点的弧的指针*/ }VNode,AdjList[MAX_VERTEX_NUM]; /* 头结点*/ typedef struct { AdjList vertices; int vexnum,arcnum; /* 图的当前顶点数和弧数*/ int kind; /* 图的种类标志*/ }ALGraph; /* 。
  。。。。。。。。。。。。。。。。。。。。。。。。*/ /* 。。。。。。。。。。。。。。。。。。。。。。。。。*/ /*ALGraphAlgo。cpp 图的邻接表存储(存储结构由ALGraphDef。
  h 定义)的基本操作*/ int LocateVex(ALGraph G,VertexType u) { /* 初始条件: 图G 存在,u 和G 中顶点有相同特征*/ /* 操作结果: 若G 中存在顶点u,则返回该顶点在图中位置;否则返回-1 */ int i; for(i=0;iadjvex=j; if(G。
  kind==1||G。kind==3) /* 网*/ { p->info=(int *)malloc(sizeof(int)); *(p->info)=w; } else p->info=NULL; /* 图*/ p->nextarc=G。
  vertices[i]。firstarc; /* 插在表头*/ G。vertices[i]。firstarc=p; if(G。kind>=2) /* 无向图或网,产生第二个表结点*/ { p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=i; if(G。
  kind==3) /* 无向网*/ { p->info=(int*)malloc(sizeof(int)); *(p->info)=w; } else p->info=NULL; /* 无向图*/ p->nextarc=G。
  vertices[j]。firstarc; /* 插在表头*/ G。vertices[j]。firstarc=p; } } return OK; } void DestroyGraph(ALGraph &G) { /* 初始条件: 图G 存在。
  操作结果: 销毁图G */ int i; ArcNode *p,*q; G。vexnum=0; G。arcnum=0; for(i=0;inextarc; if(G。kind%2) /* 网*/ free(p->info); free(p); p=q; } } } VertexType* GetVex(ALGraph G,int v) { /* 初始条件: 图G 存在,v 是G 中某个顶点的序号。
  操作结果: 返回v 的值*/ if(v>=G。vexnum||vadjvex; else return -1; } int NextAdjVex(ALGraph G,VertexType v,VertexType w) { /* 初始条件: 图G 存在,v 是G 中某个顶点,w 是v 的邻接顶点*/ /* 操作结果: 返回v 的(相对于w 的)下一个邻接顶点的序号。
  */ /* 若w 是v 的最后一个邻接点,则返回-1 */ ArcNode *p; int v1,w1; v1=LocateVex(G,v); /* v1 为顶点v 在图G 中的序号*/ w1=LocateVex(G,w); /* w1 为顶点w 在图G 中的序号*/ p=G。
  vertices[v1]。firstarc; while(p&&p->adjvex!=w1) /* 指针p 不空且所指表结点不是w */ p=p->nextarc; if(!p||!p->nextarc) /* 没找到w 或w 是最后一个邻接点*/ return -1; else /* p->adjvex==w */ return p->nextarc->adjvex; /* 返回v 的(相对于w 的)下一个邻接顶点的序号*/ } Boolean visited[MAX_VERTEX_NUM]; /* 访问标志数组(全局量) */ void(*VisitFunc)(char* v); /* 函数变量(全局量) */ void DFS(ALGraph G,int v) { /* 从第v 个顶点出发递归地深度优先遍历图G。
  算法7。5 */ int w; VertexType v1,w1; strcpy(v1,*GetVex(G,v)); visited[v]=TRUE; /* 设置访问标志为TRUE(已访问) */ VisitFunc(G。
  vertices[v]。data); /* 访问第v 个顶点*/ for(w=FirstAdjVex(G,v1);w>=0;w=NextAdjVex(G,v1,strcpy(w1,*GetVex(G,w)))) if(!visited[w]) DFS(G,w); /* 对v 的尚未访问的邻接点w 递归调用DFS */ } void DFSTraverse(ALGraph G,void(*Visit)(char*)) { /* 对图G 作深度优先遍历。
  算法7。4 */ int v; VisitFunc=Visit; /* 使用全局变量VisitFunc,使DFS 不必设函数指针参数*/ for(v=0;v=0;w=NextAdjVex(G,u1,strcpy(w1,*GetVex(G,w)))) if(!visited[w]) /* w 为u 的尚未访问的邻接顶点*/ { visited[w]=TRUE; Visit(G。
  vertices[w]。data); EnQueue(Q,w); /* w 入队*/ } } } printf(" "); } void Display(ALGraph G) { /* 输出图的邻接矩阵G */ int i; ArcNode *p; switch(G。
  kind) { case DG: printf("有向图 "); break; case DN: printf("有向网 "); break; case AG: printf("无向图 "); break; case AN: printf("无向网 "); } printf("%d 个顶点： ",G。
  vexnum); for(i=0;iadjvex]。data); if(G。kind==DN) /* 网*/ printf(":%d ",*(p->info)); } else /* 无向(避免输出两次) */ { if(iadjvex) { printf("%s－%s ",G。
  vertices[i]。data,G。vertices[p->adjvex]。data); if(G。kind==AN) /* 网*/ printf(":%d ",*(p->info)); } } p=p->nextarc; } printf(" "); } } /* 。
  。。。。。。。。。。。。。。。。。。。。。。。。*/ /* 。。。。。。。。。。。。。。。。。。。。。。。。。*/ #include "pubuse。h" #define MAX_NAME 3 /* 顶点字符串的最大长度 1 */ typedef int InfoType; /* 存放网的权值*/ typedef char VertexType[MAX_NAME]; /* 字符串类型*/ #include"ALGraphDef。
  h" #include"ALGraphAlgo。
  h" void print(char *i) { printf("%s ",i); } void main() { int i,j,k,n; ALGraph g; VertexType v1,v2; printf("请选择有向图 "); CreateGraph(g); Display(g); printf("深度优先搜索的结果: "); DFSTraverse(g,print); printf("广度优先搜索的结果: "); BFSTraverse(g,print); DestroyGraph(g); /* 销毁图*/ }。收起