#include <stdio.h>

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