邻接矩阵实现的拓扑排序

向右看齐 2022-09-18 12:58 156阅读 0赞

由于书上的大部分都是邻接表实现的拓扑排序，所以我又写了一个顺序栈实现的拓扑排序算法，觉得有一点想法，所以在此和大家分享一下。

首先是算法的思想，数据结构这一门课其实追究到底是学习各种数据结构的思想以及根据不同的问题选择适合的数据结构的能力，很难说一种数据结构一定比另一种数据结构好，只能说一种数据结构比那一种数据结构更加适合在这个场合。

拓扑排序算法思想就是，首先找寻入度为一的节点，然后将节点存入栈，然后出栈，把和这个节点相连的入度减去1，寻找和这个节点相连的入度为0的节点，然后再出栈，直至栈为空。

\#include <stdio.h>

//顺序栈数据结构  
\#define STACK\_MAXSIZE 100

typedef int StackType;

typedef struct  
\{  
 StackType data\[STACK\_MAXSIZE\];  
 int top;  
\}Stack;

void StackInit(Stack \*S)  
\{  
 S->top = 0;  
\}

bool StackEmpty(Stack \*S)  
\{  
 if(S->top == 0)  
  return true;  
 return false;  
\}

bool StackFull(Stack \* S)  
\{  
 if(S->top == STACK\_MAXSIZE-1)  
  return true;  
 return false;  
\}

bool StackPop(Stack \*S,int \*e)  
\{  
 if(StackEmpty(S))  
  return false;  
 \*e = S->data\[S->top--\];  
 return true;  
\}

bool StackPush(Stack \*S,int e)  
\{  
 if(StackFull(S))  
  return false;  
 S->data\[++S->top\] = e;  
 return true;  
\}

//邻接矩阵的数据结构  
\#define MGRAPH\_MAXVEX 100  
\#define INFINITY 65535

typedef int EdgeType;  
typedef char VertexType;

typedef struct  
\{  
 int numVexs,numEdges;  
 VertexType vexs\[MGRAPH\_MAXVEX\];  
 EdgeType arc\[MGRAPH\_MAXVEX\]\[MGRAPH\_MAXVEX\];  
 int in\[MGRAPH\_MAXVEX\];  
\}MGraph;

//创建有向图，以便进行拓扑排序  
void CreateMGraph(MGraph \*G)  
\{  
 int i,j,k;  
 printf("图的节点数目:");  
 scanf("%d",&G->numVexs);  
 printf("图的边的数目:");  
 scanf("%d",&G->numEdges);  
 getchar();  
 //输入节点信息  
 printf("依次输入图的节点信息:\\n");  
 for(i=0;i<G->numVexs;i++)  
 \{  
  printf("输入第%d个节点信息:",i+1);  
  scanf("%c",&G->vexs\[i\]);  
  getchar();  
 \}  
 //入度初始化  
 for(i=0;i<G->numVexs;i++)  
 \{  
  G->in\[i\] = 0;  
 \}  
 //所有节点的边初始化  
 for(i=0;i<G->numVexs;i++)  
 \{  
  for(j=0;j<G->numVexs;j++)  
  \{  
   G->arc\[i\]\[j\] = G->arc\[j\]\[i\] = 0;  
  \}  
 \}  
 printf("输入边的信息vi,vj:\\n");  
 for(k=0;k<G->numEdges;k++)  
 \{  
  printf("输入第%d条边:",k+1);  
  scanf("%d,%d",&i,&j);  
  G->arc\[i\]\[j\] = 1;  
  G->in\[j\]++;  
 \}  
\}

//邻接矩阵实现拓扑排序  
bool MGraphTopologicalSort(MGraph \*G)  
\{  
 //循环变量  
 int i,j,k;  
 //计数器，计算拓扑排序所走过的节点数目  
 int count = 0;  
 //栈  
 Stack S;  
 StackInit(&S);  
 //初始化数据，把所有的入度为0的加入栈  
 for(i=0;i<G->numVexs;i++)  
 \{  
  if(G->in\[i\] == 0)  
  \{  
   StackPush(&S,i);  
  \}  
 \}  
 while(!StackEmpty(&S))  
 \{  
  StackPop(&S,&k);  
  printf("%c->",G->vexs\[k\]);  
  count++;  
  for(i=0;i<G->numVexs;i++)  
  \{  
   if(G->arc\[k\]\[i\] == 1)  
   \{  
    G->in\[i\]--;  
    if(G->in\[i\] == 0)  
    \{  
     StackPush(&S,i);  
    \}  
   \}  
  \}  
 \}  
 //如果计算得到的拓扑排序的节点数目小于总的，说明不是连通图  
 if(count<G->numVexs)  
  return false;  
 return true;  
\}

int main()  
\{  
 MGraph G;  
 CreateMGraph(&G);  
 MGraphTopologicalSort(&G);  
 return 1;  
\}

很希望有人可以和我交流下，如果有什么意见尽管提出，鱼鱼哥很乐意回答的。

样例：

图的节点数目:4  
图的边的数目:4  
依次输入图的节点信息:  
输入第1个节点信息:a  
输入第2个节点信息:b  
输入第3个节点信息:c  
输入第4个节点信息:d  
输入边的信息vi,vj:  
输入第1条边:0,1  
输入第2条边:0,2  
输入第3条边:1,3  
输入第4条边:2,3

a->c->b->d