13週目、プロジェクト-検証アルゴリズム(5)

1880 ワード

問題およびコード:
(プログラム内graph.hは図ストレージ構造の「アルゴリズムライブラリ」のヘッダファイルです.詳細はリンクをクリックしてください...)
(3)テスト関数:main.cpp、関連するテスト作業を完成する;
/*
 *Copyright(c) 2015,              
 *All rights reserved.
 *    :test.cpp
 *      :   
 *    :2015 11 25 
 *     ;v1.0
 *
 *    :        
 *    :
 *    :
 */
#include <stdio.h>
#include <malloc.h>
#include "graph.h"

void TopSort(ALGraph *G)
{
    int i,j;
    int St[MAXV],top=-1;            // St    top
    ArcNode *p;
    for (i=0; i<G->n; i++)          //     0
        G->adjlist[i].count=0;
    for (i=0; i<G->n; i++)          //        
    {
        p=G->adjlist[i].firstarc;
        while (p!=NULL)
        {
            G->adjlist[p->adjvex].count++;
            p=p->nextarc;
        }
    }
    for (i=0; i<G->n; i++)
        if (G->adjlist[i].count==0)  //   0     
        {
            top++;
            St[top]=i;
        }
    while (top>-1)                  //       
    {
        i=St[top];
        top--;              //  
        printf("%d ",i);            //    
        p=G->adjlist[i].firstarc;   //        
        while (p!=NULL)
        {
            j=p->adjvex;
            G->adjlist[j].count--;
            if (G->adjlist[j].count==0)//   0       
            {
                top++;
                St[top]=j;
            }
            p=p->nextarc;       //        
        }
    }
}

int main()
{
    ALGraph *G;
    int A[7][7]=
    {
        {0,0,1,0,0,0,0},
        {0,0,0,1,1,0,1},
        {0,0,0,1,0,0,0},
        {0,0,0,0,1,1,0},
        {0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0},
        {0,0,0,0,0,1,0}
    };
    ArrayToList(A[0], 7, G);
    DispAdj(G);
    printf("
"); printf(" :"); TopSort(G); printf("
"); return 0; }

実行結果: