拓扑排序之邻接表实验

标签：拓扑排序

方法一：

FindInDegree()函数对各个顶点求入度，保存在indegree[]数组中。

#include 
   
    #include 
    
     #include 
     
      using namespace std;#define M 20typedef char vertextype;int indegree[M];typedef struct node{    int adjvex;    struct node *next;}edgenode;typedef struct de{    edgenode  *FirstEdge;    vertextype vertex;}vertexnode;typedef struct{    vertexnode adjlist[M];    int n,e;}AovGraph;void  creat(AovGraph *g, char *filename){    int i, j, k;    edgenode *s;    FILE *fp;    fp = fopen(filename, "r");    if(fp){        fscanf(fp, "%d %d", &g->n, &g->e);        for(i = 0; i < g->n; i++){            fscanf(fp, "%1s", &g->adjlist[i].vertex);            g->adjlist[i].FirstEdge = NULL;        }        for(k = 0; k < g->e; k++){            s = (edgenode*)malloc(sizeof(edgenode));            fscanf(fp, "%d %d", &i, &j);            s->adjvex = j;            s->next = g->adjlist[i].FirstEdge;            g->adjlist[i].FirstEdge = s;        }    }}void FindInDegree(AovGraph g, int indegree[M]){    for(int i = 0; i < g.n; i++){        int total = 0;        for(int j = 0; j < g.n; j++){            edgenode *p = g.adjlist[j].FirstEdge;            while(p){                if((p->adjvex + '0') == g.adjlist[i].vertex)  total++;  ///'0'                p = p->next;            }        }        indegree[i] = total;    }}void print(AovGraph g){    int i;    FindInDegree(g, indegree);    for(i = 0; i < g.n; i++){        printf("indegree(%d) %c",  indegree[i], g.adjlist[i].vertex);        edgenode *p = g.adjlist[i].FirstEdge;        while(p){            printf("-->%d", p->adjvex);            p = p->next;        }        printf("\n");    }}void Tsort(AovGraph g){    stack 
      
        S;    int i, k;    FindInDegree(g, indegree);    for(i = 0; i < g.n; i++)        if(!indegree[i])  S.push(g.adjlist[i].vertex - '0');  ///    int countv = 0;    while(!S.empty()){        i = S.top(), S.pop();        printf("%c", g.adjlist[i].vertex);        ++countv;        for(edgenode *p = g.adjlist[i].FirstEdge; p; p = p->next){            k = p->adjvex;            if(!(--indegree[k]))  S.push(k);        }    }    if(countv < g.n)  printf("failed\n");}int main(){    AovGraph g;    creat(&g, "topo.txt");    print(g), printf("\n");    Tsort(g), printf("\n");    return 0;}

方法二：

在邻接表头结点中增加一个存放顶点入度的域，在读图的同时计算各顶点的入度。

#include 
   
    #include 
    
     #include 
     
      using namespace std;#define M 20typedef char vertextype;typedef struct node{    int adjvex;    struct node *next;}edgenode;typedef struct de{    edgenode  *FirstEdge;    vertextype vertex;    int id;  //顶点的入度}vertexnode;typedef struct{    vertexnode adjlist[M];    int n,e;}AovGraph;void  creat(AovGraph *g, char *filename){    int i, j, k;    edgenode *s;    FILE *fp;    fp = fopen(filename, "r");    if(fp){        fscanf(fp, "%d %d", &g->n, &g->e);        for(i = 0; i < g->n; i++){            fscanf(fp, "%1s", &g->adjlist[i].vertex);            g->adjlist[i].FirstEdge = NULL;            g->adjlist[i].id = 0;  //入度初始化为0        }        for(k = 0; k < g->e; k++){            s = (edgenode*)malloc(sizeof(edgenode));            fscanf(fp, "%d %d", &i, &j);            s->adjvex = j;            g->adjlist[j].id++;  //顶点j的入度加1            s->next = g->adjlist[i].FirstEdge;            g->adjlist[i].FirstEdge = s;        }    }}void print(AovGraph g){    int i;    for(i = 0; i < g.n; i++){        printf("indegree(%d) %c",  g.adjlist[i].id, g.adjlist[i].vertex);        edgenode *p = g.adjlist[i].FirstEdge;        while(p){            printf("-->%d", p->adjvex);            p = p->next;        }        printf("\n");    }}void Tsort(AovGraph g){    stack 
      
        S;    int i, k;    for(i = 0; i < g.n; i++)        if(!g.adjlist[i].id)  S.push(g.adjlist[i].vertex - '0');  ///    int countv = 0;    while(!S.empty()){        i = S.top(), S.pop();        printf("%c", g.adjlist[i].vertex);        ++countv;        for(edgenode *p = g.adjlist[i].FirstEdge; p; p = p->next){            k = p->adjvex;            if(!(--g.adjlist[k].id))  S.push(k);        }    }    if(countv < g.n)  printf("failed\n");}int main(){    AovGraph g;    creat(&g, "topo.txt");    print(g), printf("\n");    Tsort(g), printf("\n");    return 0;}

数据文件：