그림 의 옮 겨 다 니 기--저장 구조의 옮 겨 다 니 기(DFS,BFS)C 언어 로 인접 표를 사용 합 니 다.

#include 
#include 
#include  
#define MAX_VERTEX_NUM 20 //       
typedef char VertexType;
typedef int VRType;
typedef int InfoType;    //          
typedef int QElemType;   //          

/*                 */
//      
typedef struct ArcNode
{
    int adjvex;        //            
    struct ArcNode *nextarc;   //          
    InfoType *info;           //          ，    
 }ArcNode;

 typedef struct VNode
 {
    VertexType data;     //     
    ArcNode *firstarc;   //                
 }VNode,AdjList[MAX_VERTEX_NUM];
 typedef struct
 {
    AdjList vertices;    
    int vexnum,arcnum;   //       
 }ALGraph;

//             
typedef struct QNode
{
    QElemType data;
    struct QNode *qnext;
}QNode,*PQNode;

typedef struct Queue
{
    PQNode front;
    PQNode rear;
}Queue,*PQueue;

//         
PQueue initQueue()
{
    PQueue pqueue = (PQueue)malloc(sizeof(Queue));
    PQNode pqnode = (PQNode)malloc(sizeof(QNode));
    if(pqnode==NULL)
    {
        printf("         ！
");
        exit(-1);
    }
    pqueue->front = pqueue->rear = pqnode;
    pqnode->qnext = NULL;
    return pqueue;
}

//    
void enQueue(PQueue pqueue,QElemType data)
{
    PQNode pqnode = (PQNode)malloc(sizeof(QNode));
    if(pqnode==NULL)
    {
        printf("        ！
");
        exit(-1);
    }
    pqnode->data = data;
    pqnode->qnext = NULL;
    pqueue->rear->qnext = pqnode;
    pqueue->rear = pqnode;
 } 
//        
bool isEmpty(PQueue pqueue)
{
    if(pqueue->front == pqueue->rear)
        return true;
    return false;
 } 
//    
QElemType deQueue(PQueue pqueue)
{
    if(isEmpty(pqueue))
    {
        printf("    
");
        exit(-1);
    }

    PQNode pqnode = pqueue->front->qnext;
    pqueue->front->qnext = pqnode->qnext;
    if(pqnode == pqueue->rear)
        pqueue->rear = pqueue->front;
    QElemType data = pqnode->data;
    free(pqnode);
    return data;

}

//           
int locateVex(ALGraph alg,char v)
{
    int i;
    for(i=0;iif(alg.vertices[i].data == v)
        return i;
    }
    return -1;
 } 

//     
void createALGraph(ALGraph *alg)
{
    int i,j,v,k;
    printf("          
");
    scanf("%d %d",&(*alg).vexnum,&(*alg).arcnum);
    printf("      
");
    //fflush(stdin); 
    getchar();
    for(i = 0;iprintf("   %d     :",i);
        scanf("%c",&(*alg).vertices[i].data); 
        (*alg).vertices[i].firstarc = NULL;
        // fflush(stdin);             //fflush(stdin)  getchar()          
        getchar();
    }

    printf("       
");
    char v1,v2;
    ArcNode *s,*p;
    for(k = 0;kprintf("   %d       v1 v2：",k);
        scanf("%c %c",&v1,&v2);
        i = locateVex((*alg),v1);
        j = locateVex((*alg),v2);
        //                    
        p = (ArcNode*)malloc(sizeof(ArcNode));
        p->adjvex = j;
        p->nextarc = NULL;
        if((*alg).vertices[i].firstarc==NULL)
        {
            (*alg).vertices[i].firstarc = p;
        }
        else
        {
            s = (*alg).vertices[i].firstarc;
            while(s->nextarc!=NULL)
                s = s->nextarc;
            s->nextarc = p;
        }

        p = (ArcNode*)malloc(sizeof(ArcNode));
        p->adjvex = i;
        p->nextarc = NULL;
        if((*alg).vertices[j].firstarc==NULL)
        {
            (*alg).vertices[j].firstarc = p;
        }
        else
        {
            s = (*alg).vertices[j].firstarc;
            while(s->nextarc!=NULL)
                s = s->nextarc;
            s->nextarc = p;
        }
        //fflush(stdin);
    getchar();
    } 
 } 

bool visited[MAX_VERTEX_NUM];  //          ，  flase,  true;

//          
void DFS(ALGraph alg,int v)
{
    //  v               alg
    ArcNode *p;
    visited[v] = true;
    printf("%c ",alg.vertices[v].data);
    for(p = alg.vertices[v].firstarc;p!=NULL;p = p->nextarc)
    {
        if(!visited[p->adjvex])
            DFS(alg,p->adjvex);
     } 
 } 

void DFSTraverse(ALGraph alg)
{
    //                  
    printf("        ：");
    int v;
    for(v=0;vfalse;
    for(v=0;vif(!visited[v])
            DFS(alg,v);
     } 
}

//      
void BFSTraverse(ALGraph alg)
{
    printf("        ：");
    PQueue pqueue = initQueue();
    ArcNode *p;
    int i;
    QElemType v;
    for(i=0;ifalse;
    for(i=0;iif(!visited[i])
        {
            visited[i] = true;
            printf("%c ",alg.vertices[i].data);
            enQueue(pqueue,i);
            while(!isEmpty(pqueue))
            {
                v = deQueue(pqueue);
                for(p = alg.vertices[v].firstarc;p!=NULL;p = p->nextarc)
                {
                    if(!visited[p->adjvex])
                    {
                        printf("%c ",alg.vertices[p->adjvex].data);
                        visited[p->adjvex] = true;
                        enQueue(pqueue,p->adjvex);
                    }
                }
            }
        }
    }

 } 
int main(int argc, char *argv[]) {
    ALGraph alg;
    createALGraph(&alg);   //      
    DFSTraverse(alg);
    printf("
"); 
    BFSTraverse(alg);
    printf("
"); 
    return 0;
}