邻接表实现的拓扑排序

妖狐艹你老母 2022-09-18 12:58 11阅读 0赞

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

//邻接矩阵的图的数据结构表示

\#define INFINITY 65535  
\#define MAXVEX 100

typedef int EdgeType;  
typedef char VertexType;

typedef struct EdgeNode  
\{  
 int adjvex;  
 EdgeNode \*next;  
 int weight;  
\}EdgeNode;

typedef struct VertexNode  
\{  
 int in;  
 VertexType data;  
 EdgeNode \*first;  
\}VertexNode,AdjList\[MAXVEX\];

typedef struct  
\{  
 int numVexs,numEdges;  
 AdjList adjList;  
\}MGraphAdjList;

//顺序栈  
typedef int StackType;

\#define STACKMAXSIZE 100

typedef struct  
\{  
 StackType data\[STACKMAXSIZE\];  
 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 == STACKMAXSIZE-1)  
  return true;  
 return false;  
\}

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

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

bool TopologicalSort(MGraphAdjList \*G)  
\{  
 EdgeNode \*temp;  
 int i,j,k;  
 int t;  
 int count=0;  
 Stack S;  
 StackInit(&S);  
 for(i=0;i<G->numVexs;i++)  
 \{  
  if(G->adjList\[i\].in == 0)  
   StackPush(&S,i);  
 \}  
 while(!StackEmpty(&S))  
 \{  
  StackPop(&S,&t);  
  count++;  
  for(temp = G->adjList\[t\].first;temp;temp = temp->next)  
  \{  
   if(!(--G->adjList\[temp->adjvex\].in))  
   \{  
    StackPush(&S,temp->adjvex);  
   \}  
  \}  
 \}  
 if(count<G->numVexs)  
  return false;  
 return true;  
\}

int main()  
\{  
 return 1;  
\}

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