实验六 图的应用及其实现 (2)

typedef int SElemType;

#define STACK_INIT_SIZE 100 #define STAXKINCREMENT 10 #define MAX_VERTEX_NUM 20 typedef struct ArcNode {

int adjvex;

struct ArcNode *nextarc; InfoType *info; }ArcNode;

typedef struct VNode {

VertexType data;

struct ArcNode *firstarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct ALGraph

{ AdjList vertices; int vexnum, arcnum;

int kind; }ALGraph;

typedef struct {

SElemType *base; SElemType *top; int stacksize; }SqStack;

int CreateDG(ALGraph &G) {

int i,j,k,v1,v2;

cout<<\请输入该图的顶点数：\请输入该图的边数： cin>>G.vexnum>>G.arcnum; for(i=0;i

G.vertices[i].data=i;

G.vertices[i].firstarc=NULL; }

cout<<\请输入一条边的始点和终点：\ for(k=0;k

\ {

cout<<\请输入第 \条边的始点和终点: \ cin>>v1>>v2; i=v1; j=v2;

while(i<1||i>G.vexnum||j<1||j>G.vexnum) {

cout<<\请输入第 \条边的始点和终点: \ cin>>v1>>v2; i=v1; j=v2; }

i--;j--; ArcNode *p;

p=(ArcNode *)malloc(sizeof(ArcNode)); if(!p) return -1; p->adjvex=j;

p->nextarc=G.vertices[i].firstarc;

p->info=NULL; G.vertices[i].firstarc=p; G.vertices[i]; }

return 0; }

int InitStack(SqStack &S) {

S.base=(SElemType

*)malloc(STACK_INIT_SIZE*sizeof(SElemType));

if(!S.base) exit (-1); S.top=S.base;

S.stacksize=STACK_INIT_SIZE; return 0; }

int Push(SqStack &S,SElemType e) {

if(S.top-S.base>=S.stacksize) {

S.base=(SElemType*)realloc(S.base,(S.stacksize+STAXKINCREMENT)*sizeof(SElemType));

if(!S.base) exit (-1); S.top=S.base+S.stacksize;

S.stacksize+=STAXKINCREMENT; }

*S.top++=e; return 0; }

int Pop(SqStack &S,SElemType &e) {

if(S.top==S.base) return -1; e=*--S.top; return 0; }

int StackEmpty(SqStack S) {

if(S.top==S.base) return -1; else return 0; }

void FindInDegree(ALGraph G,int *indegree) {

int i;

for(i=0;i

for(i=0;i

while(G.vertices[i].firstarc) {

indegree[G.vertices[i].firstarc->adjvex]++;

G.vertices[i].firstarc=G.vertices[i].firstarc->nextarc;

} }

int TopologicalSort(ALGraph G) {

int i,k,indegree[MAX_VERTEX_NUM]; ArcNode *p; SqStack S;

FindInDegree(G,indegree); InitStack(S);

for(i=0;i

if(!indegree[i]) Push(S,i); int count=0;

while(!StackEmpty(S)) {

Pop(S,i);

cout<

for(p=G.vertices[i].firstarc; p; p=p->nextarc) {

k=p->adjvex;

if(!(--indegree[k])) Push(S,k); } }

if(count

int main() {

ALGraph G; CreateDG(G);

TopologicalSort(G); return 0; }

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新教学研究实验六 图的应用及其实现 (2)全文阅读和word下载服务。