#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define MAX 20   //圖可以存儲(chǔ)的最大節(jié)點(diǎn)數(shù)為20；
struct tnode
{
    struct tnode * next;//指向下一個(gè)臨節(jié)點(diǎn)
    int data;//存放鄰節(jié)點(diǎn)在數(shù)組中的位置
};
struct node
{
    int valu;//存放節(jié)點(diǎn)的值
    struct tnode * link;//指向鄰節(jié)點(diǎn)
};
struct picture
{
    struct node nd[MAX];    //聲明一個(gè)節(jié)點(diǎn)數(shù)組
    int count;  //圖中的節(jié)點(diǎn)數(shù)
    char a; //建立的圖的類型
};
struct picture * createpicture();
int search(struct picture *p,int value);//查找value在nd數(shù)組中的位置
void bfs(struct picture * q,int i,int visit[]); //廣度優(yōu)先遍歷
void dfs(struct picture * q,int i,int visit[]);//深度優(yōu)先遍歷
void traversedfs(struct picture *p);
void traversebfs(struct picture *p);
int main()
{
    char a;
    struct picture *p;
    p=createpicture();
    while(1)
    {
        getchar();
        printf("現(xiàn)在將對圖進(jìn)行遍歷，若使用廣度優(yōu)先遍歷，請輸入a,若使用深度優(yōu)先遍歷請輸入b，清屏請輸入c,退出請輸入d:\n");
        scanf("%c",&a);
        if(a=='a')
        {
        printf("深度優(yōu)先遍歷如下：\n");
        traversebfs(p);
        }
        if(a=='b')
        {
        printf("廣度優(yōu)先遍歷如下：\n");
        traversedfs(p);
        }
        if(a=='c')
        system("cls");
        if(a=='d')
        exit(0);
    }
    return 0;
}
struct picture * createpicture()
{
    int i,j,k,l;//l中存放返回的節(jié)點(diǎn)在數(shù)組中的位置
    char a;
    struct picture *p;
    p=(struct picture *)malloc(sizeof(struct picture));
    struct tnode * t;
    printf("請輸入你要建立的圖中的節(jié)點(diǎn)數(shù)以及圖的類型(a表示無向圖b表示有向圖):\n");
    scanf("%d %c",&i,&a);
    p->count=i;
    p->a=a;
    printf("請依次輸入各節(jié)點(diǎn)的值(每輸完一個(gè)節(jié)點(diǎn)的值按回車結(jié)束)：\n");
    for(i=0;i<p->count;i++)
    {
        scanf("%d",&j);
        p->nd[i].valu=j;
        p->nd[i].link=NULL;
    }
    for(i=0;i<p->count;i++)
    {
        printf("輸入與數(shù)據(jù)值為%d的節(jié)點(diǎn)相鄰的節(jié)點(diǎn)的數(shù)據(jù)值(每輸完一個(gè)節(jié)點(diǎn)的值按回車結(jié)束),若不再含有相鄰的值請輸入-1\n",p->nd[i].valu);
        while(1)
        {
            scanf("%d",&k);
            if(k==-1)
                break;
            l=search(p,k);
            if(l!=-1)
            {
                t=(struct tnode *)malloc(sizeof(struct tnode));
                t->data=l;
                t->next=p->nd[i].link;
                p->nd[i].link=t;
            }
            else
                printf("無此數(shù)據(jù)值!\n");
            //getchar();
        }
    }
    return p;
}
int search(struct picture *p,int value)
{
    int i;
    for(i=0;i<p->count;i++)
    {
        if(value==p->nd[i].valu)
        {
            return i;
        }
    }
    return -1;
}
void traversedfs(struct picture *p)
{
    int i;
    int visit[MAX];//申明一個(gè)標(biāo)志數(shù)組,將其初始值置為0,0表示該節(jié)點(diǎn)未被訪問過，1表示該節(jié)點(diǎn)被訪問過
    for(i=0;i<p->count;i++)
    {
        visit[i]=0;
    }
    for(i=0;i<p->count;i++)
    {
        if(visit[i]==0)
        {
            dfs(p,i,visit);
        }
    }
    //getchar();
}
void dfs(struct picture * q,int i,int visit[])//i表示數(shù)組的下標(biāo)值visit的下標(biāo)與p中的下標(biāo)是一一對應(yīng)的關(guān)系
{
    struct tnode * w;
    printf("%d\n",q->nd[i].valu);
    visit[i]=1;
    w=q->nd[i].link;
    while(w!=NULL)
    {
        if(visit[w->data]==0)
        {
            dfs(q,w->data,visit);
        }
        else
        {
            w=w->next;
        }
    }  
}
void traversebfs(struct picture *p)
{
    int i;
    int visit[MAX];//申明一個(gè)標(biāo)志數(shù)組,將其初始值置為0,0表示該節(jié)點(diǎn)未被訪問過，1表示該節(jié)點(diǎn)被訪問過
    for(i=0;i<p->count;i++)
    {
        visit[i]=0;
    }
    for(i=0;i<p->count;i++)
    {
        if(visit[i]==0)
        {
            bfs(p,i,visit);
        }
    }
    //getchar();
}
void bfs(struct picture * q,int i,int visit[])
{
    struct tnode *w;
    int a[MAX];//聲明一個(gè)隊(duì)列
    int f,r;
    int v;
    f=r=0;
    visit[i]=1;
    printf("%d\n",q->nd[i].valu);
    a[r]=i;
    r++;//進(jìn)行入隊(duì)操作
    while(f!=r)
    {
        v=a[f];
        f++;//岀隊(duì)操作
        w=q->nd[v].link;
        while(w!=NULL)
        {
            if(visit[w->data]==0)
            {
            visit[w->data]=1;
            printf("%d\n",q->nd[w->data].valu);
            a[r]=w->data;
            r++;
            }
            w=w->next;
        }
    }
}

標(biāo)簽：

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請與原作者聯(lián)系。