12주 프로젝트 검증 알고리즘(2)

3341 단어
Dijkstra 알고리즘 검증
#include 
#include 
#include "graph.h"
#define MaxSize 100
void Ppath(int path[],int i,int v)  // 
{
    int k;
    k=path[i];
    if (k==v)  return;          // 
    Ppath(path,k,v);            // k 
    printf("%d,",k);            // k
}
void Dispath(int dist[],int path[],int s[],int n,int v)
{
    int i;
    for (i=0; i

Floyd 알고리즘 검증
#include 
#include 
#include "graph.h"
#define MaxSize 100
void Ppath(int path[][MAXV],int i,int j)  // 
{
    int k;
    k=path[i][j];
    if (k==-1) return;  // 
    Ppath(path,i,k);    // i k
    printf("%d,",k);
    Ppath(path,k,j);    // k j
}
void Dispath(int A[][MAXV],int path[][MAXV],int n)
{
    int i,j;
    for (i=0; i :%d  :",i,j,A[i][j]);
                printf("%d,",i);    // 
                Ppath(path,i,j);    // 
                printf("%d
",j); // } } } void Floyd(MGraph g) { int A[MAXV][MAXV],path[MAXV][MAXV]; int i,j,k; for (i=0; iA[i][k]+A[k][j]) { A[i][j]=A[i][k]+A[k][j]; path[i][j]=k; } } Dispath(A,path,g.n); // } int main() { MGraph g; int A[4][4]= { {0, 5,INF,7}, {INF,0, 4,2}, {3, 3, 0,2}, {INF,INF,1,0} }; ArrayToMat(A[0], 4, g); Floyd(g); return 0; }

토폴로지 정렬 알고리즘 검증
#include 
#include 
#include "graph.h"

void TopSort(ALGraph *G)
{
    int i,j;
    int St[MAXV],top=-1;            // St top
    ArcNode *p;
    for (i=0; in; i++)          // 0
        G->adjlist[i].count=0;
    for (i=0; in; i++)          // 
    {
        p=G->adjlist[i].firstarc;
        while (p!=NULL)
        {
            G->adjlist[p->adjvex].count++;
            p=p->nextarc;
        }
    }
    for (i=0; in; 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; }

좋은 웹페이지 즐겨찾기