Problem Description

本实验实现邻接表表示下无向图的广度优先遍历。
程序的输入是图的顶点序列和边序列(顶点序列以*为结束标志，边序列以-1,-1为结束标志)。程序的输出为图的邻接表和广度优先遍历序列。例如：

程序输入为：

a
b
c
d
e
f
*
0,1
0,4
1,4
1,5
2,3
2,5
3,5
-1,-1

程序的输出为：

the ALGraph is
a 4 1
b 5 4 0
c 5 3
d 5 2
e 1 0
f 3 2 1
the Breadth-First-Seacrh list:aebfdc

AcCode

//
//  main.cpp
//  图的广度优先遍历
//
//  Created by jetviper on 2017/3/26.
//  Copyright © 2017年 jetviper. All rights reserved.
//

#include <stdio.h>
#include<string.h>
int n=0,x,y;
struct {
    char nd[3];
    int bnum=0;
    int vsed =0;
    int linkto[100];
}node[100];
void search(int now){
    int temp[100],count=0;
    if(node[now].vsed==0){
        printf("%s",node[now].nd);
        node[now].vsed =1;
    }
    for(int i=node[now].bnum-1;i>=0;i--){
        if(node[node[now].linkto[i]].vsed==0){
            printf("%s",node[node[now].linkto[i]].nd);
            node[node[now].linkto[i]].vsed=1;
            temp[count]=node[now].linkto[i];
            count++;
        }
        
    }
    for(int i=0;i<count;i++)search(temp[i]);
    
}





int main() {
    
    while(1){
        scanf("%s",&node[n].nd);
        if(strcmp(node[n].nd,"*")==0){
            break;
        }
        n++;
    }
    while(1){
        scanf("%d,%d",&x,&y);
        if(x==-1)break;
        node[x].linkto[node[x].bnum] = y;
        node[x].bnum++;
        node[y].linkto[node[y].bnum] = x;
        node[y].bnum++;
    }
    
    printf("the ALGraph is\n");
    
    for(int i=0;i<n;i++){
        printf("%s",node[i].nd);
        for(int j=node[i].bnum-1;j>=0;j--){
            printf(" %d",node[i].linkto[j]);
        }
        printf("\n");
    }
    printf("the Breadth-First-Seacrh list:");
    for(int i=0;i<n;i++){
        if(node[i].vsed==0){
            search(i);
        }
    }
    printf("\n");
    
    
    
    
    return 0;
}