《最简单的AOV算法.doc》由会员分享，可在线阅读，更多相关《最简单的AOV算法.doc（4页珍藏版）》请在金锄头文库上搜索。
1、AOV#include#includetypedef char VertexType;/*图的顶点字符串类型*/typedef int InfoType;/*顶点权值类型*/#define MAX_VERTEX_NUM 20int visitedMAX_VERTEX_NUM;/(全局变量)访问标识数组，未访问标记0，访问标记1typedef struct ArcNode/int adjvex;/该弧所指向的顶点的位置struct ArcNode *nextarc;/指向下一条弧的指针ArcNode;/*表结点*/typedef struct/int indegree;/顶点入度VertexTy
2、pe data;/顶点信息ArcNode *firstarc;/第一个表结点的地址，指向第一条依附该顶点的弧的指针VNode,AdjListMAX_VERTEX_NUM;/*头结点*/typedef struct/AdjList vertices;int vexnum,arcnum;/图的当前顶点数和弧数(边数)ALGraph;/*LocateVex，初始条件：图g存在，u和g中顶点有相同的特征。操作结果：若图g中存在顶点u，则返回该顶点在图中的位置，否则返回-1*/int LocateVex(ALGraph *g,VertexType u)int i;for(i = 0;i vexnum;
3、+i)if(u = g-verticesi.data)return i;return -1;/*CreateGraph 采用邻接表存储结构，构造没有相关信息的有向图g*/void CreateGraph(ALGraph *g)int i,j,k;char ch;int GetNum(ALGraph *g,VertexType ch);VertexType va,vb;ArcNode *p;printf(Enter Vertex number,Arc number of the Graph:); scanf(%d%d,&g-vexnum,&g-arcnum);/输入图的顶点数和边数 printf
4、(Enter %d Vertex:n,g-vexnum); fflush(stdin); for(i = 0;i vexnum; i+)/构造顶点向量表头 ch = getchar(); if(ch != ) g-verticesi.data = ch; else i-; g-verticesi.firstarc = NULL; g-verticesi.indegree = 0; printf(Enter order every arc head and tail(Takes the gap by the blank space):n); fflush(stdin); for(k = 0;k
5、arcnum; +k) /输入图的边，构造表结点链表 scanf(%c%c%c,&va,&ch,&vb); g-verticesGetNum(g,vb).indegree+;/ fflush(stdin); i = LocateVex(g,va);/弧尾 j = LocateVex(g,vb);/弧头 p = (ArcNode *)malloc(sizeof(ArcNode); p-adjvex = j; p-nextarc = g-verticesi.firstarc;/插在表头 g-verticesi.firstarc = p; /*GetNum,初始条件：图g存在，ch是图中某个顶点的值
6、。操作结果：返回其序号*/int GetNum(ALGraph *g,VertexType ch)int i;for(i = 0;i vexnum; i+)if(ch = g-verticesi.data) break;return i;/*GetVex,初始条件:图g存在，v是图中的某个顶点的序号。操作将结果:返回v的值*/VertexType GetVex(ALGraph *g,int v)if(v =g-vexnum | v verticesv.data;/返回v对应的表头的值/* FirstAdjVex，初始条件：图g存在，v是图中的某个顶点。操作结果:返回v的第一个邻接顶点的序号。若
7、顶点在g中没有邻接顶点，则返回-1*/int FirstAdjVex(ALGraph *g,VertexType v)ArcNode *p;int v1;v1 = LocateVex(g,v);/返回v在图中的顶点序号p = g-verticesv1.firstarc;if(p)return p-adjvex;elsereturn -1;/*NextAdjVex，初始条件：图g存在，v是g中的某个顶点，w是v的邻接顶点操作结果：返回v的（相对于w的）下一个邻接顶点的序号。若w是v的最后一个邻接点，则返回-1*/int NextAdjVex(ALGraph *g,VertexType v,Ver
8、texType w)ArcNode *p;int v1,w1;v1 = LocateVex(g,v);/v1为顶点v在图中的序号w1 = LocateVex(g,w);/w1为顶点w在图中的序号p = g-verticesv1.firstarc;while(p & p-adjvex != w1)/指针p不空且所指的表结点不是wp = p-nextarc;if(!p | !p-nextarc)/没有找到w或w是最后一个邻接点return -1;elsereturn p-nextarc-adjvex;/返回v的（相对于w的）下一个邻接顶点的序号/*拓扑排序算法*/void TopSort(ALGr
9、aph *g)int stackMAX_VERTEX_NUM,top;int i,j,number;ArcNode *p;top = -1;number = 0;for(i = 0;i vexnum; i+)if(g-verticesi.indegree = 0)top+;stacktop = i;/顶点入度为零的进栈while(top = 0)i = stacktop;top-;number+;printf(%c ,g-verticesi.data);p = g-verticesi.firstarc;while(p)j = p-adjvex;g-verticesj.indegree-;if(
10、!g-verticesj.indegree)top+;stacktop = j;p = p-nextarc;if(number vexnum)printf(图中有回路！);printf(n);int main()ALGraph g;CreateGraph(&g);printf(该图的拓扑排序为:n);TopSort(&g);return 0;Enter vertex number,arc nmber of the graph:5 6Enter 5 vertex:a b c d eEnter order every are head and tail:ab bc ac bd cd ce de该图的拓扑排序为：a b c d e
