一些基础算法

俞晨曦

#include <STDIO.H>
int visited[5] = {0};

int graph[5][5] =
{
        0,1,1,0,0,
        1,0,0,1,1,
        0,0,0,0,1,
        0,1,0,0,1,
        0,1,1,1,0
};

void DFS(int x)
{
        printf("%d\n",x);
        visited[x] = 1;
        int y;
        
        for(y = 0;y < 5;++y)
                if(graph[x][y] && !visited[y])
                        DFS(y);
}

#define MAX_SIZE 0x40

typedef struct
{
        int queue[MAX_SIZE];
        int front,rear;
}Queue,*PQueue;

void InitQueue(PQueue PQ)
{
        PQ->rear = PQ->front = 0;
}

void InQueue(PQueue PQ,int data)
{
        PQ->queue[PQ->rear] = data;
        PQ->rear = (PQ->rear + 1)%MAX_SIZE;
}

int OutQueue(PQueue PQ)
{
        int data = PQ->queue[PQ->front];
        PQ->front = (PQ->front + 1)%MAX_SIZE;
        return data;
}

int IsQueueEmpty(PQueue PQ)
{
        if(PQ->rear == PQ->front)
                return 1;
        return 0;
}

void BFS(int x)
{
        Queue q;
        int i;
        
        InitQueue(&q);
        
        InQueue(&q,x);
        visited[x] = 1;                

        while(!IsQueueEmpty(&q))
        {
                x = OutQueue(&q);
                printf("%d\n",x);
        
                for (i = 0;i < 5;++i)
                {
                        if(!visited[i] && graph[x][i])
                        {
                                InQueue(&q,i);
                                visited[i] = 1;        //标记访问
                        }
                }
                
        }
}

int main()
{
        return 0;
}

知表不言