图的深度遍历

#include<stdlib.h>
#include<string.h>
#include<stdio.h>

#define MaxSize 20
typedef struct Node{
    char vex;
    int location;
    struct Node * next; 
}MapNode; 
int node_num;
int visited[MaxSize];

void createMap(MapNode **p ){
    char ch;
    int i=0;
    MapNode * q,* new_node;
    (*p) = (MapNode *)malloc(sizeof(MapNode)*MaxSize);
    printf("请输入图的节点:\n");
    scanf("%c",&ch);
    while(ch!='\n'){
        (*p)[i].vex = ch;
        (*p)[i].next = NULL;
        (*p)[i].location = i;
        i++;
        scanf("%c",&ch);
    }
    node_num = i;

    for(i=0;i<node_num;i++){
        q = (*p)+i;
        printf("请输入%c的邻接节点:\n",q->vex);
        scanf("%c",&ch);
        while(ch!='\n'){
             new_node = (MapNode *)malloc(sizeof(MapNode));
            new_node->vex = ch;
            new_node->next = NULL;
            q->next = new_node;
            q = new_node;
            scanf("%c",&ch);
        }
    }
}

int get_index(MapNode *p,char v){
    int i;
    for(i=0;i<node_num;i++){
        if(p[i].vex ==v){
            return i;
        }
    }
    return -1;

}

void depth(MapNode *p,int i){
    MapNode *q;
    q = p+i;
    printf("%c ",q->vex);
    visited[i] = 1;
    q= q->next;
    while(q){
        int index = get_index(p,q->vex);
        if(visited[index]==0){
            depth(p,index);
        }
        q = q->next;
    }
}


void print_depth(MapNode *p){
    int i;
    for(i=0;i<node_num;i++){
        visited[i] = 0; 
    }
    printf("图的深度遍历:\n");
    for(i=0;i<node_num;i++){
        if(visited[i]==0){
            depth(p,i);
        }
    }
}

void print(MapNode *p){
    printf("图的邻接表:\n");
    int i;
    MapNode *q;
    for(i=0;i<node_num;i++){
        printf("%c:",p[i].vex);
        q = p[i].next;
        while(q){
            printf("%c->",q->vex);
            q = q->next;
        }
        printf("\n");
    }
}

int main(){
    MapNode *p;
    createMap(&p);
    print(p);
    print_depth(p);
    return 0;
}

结果如下图

image.png