5-3 本题要求实现对图的深度优先遍历。 本题中图的表示采用邻接表表示

5-3 本题要求实现对图的深度优先遍历。 本题中图的表示采用邻接表表示

程序填空题
5-3
本题要求实现对图的深度优先遍历。 本题中图的表示采用邻接表表示

#include 
#include 

typedef struct    GRAPHLISTNODE_STRU
{
    int nodeno;  
    struct    GRAPHLISTNODE_STRU* next;  
}GraphListNode;

typedef struct    GRAPHLIST_STRU
{
    int size; 
    GraphListNode* graphListArray; 
}GraphList;

GraphList* InitGraph(int num)
{
    int i;
    GraphList *graphList = (GraphList *)malloc(sizeof(GraphList));
    graphList->size = num;
    graphList->graphListArray = (GraphListNode*)malloc(sizeof(GraphListNode)*num);
    for (i = 0; igraphListArray[i].next = NULL;
        graphList->graphListArray[i].nodeno = i;
    }
    return graphList;
}

void ReadGraph(GraphList* graphList)
{
    int vex1, vex2;
    GraphListNode *tempNode = NULL;

    
    scanf("%d %d", &vex1, &vex2);
    while (vex1 >= 0 && vex2 >= 0)
    {
        tempNode = (GraphListNode*)malloc(sizeof(GraphListNode));
        tempNode->nodeno = vex2;
        //tempNode->next = NULL;
        
        tempNode->next=graphList->graphListArray[vex1].next;
        graphList->graphListArray[vex1].next=tempNode;
        scanf("%d %d", &vex1, &vex2);
    }
}


void DFS(GraphList* graphList, int * visited, int i)
{
    int j;
    GraphListNode *tempNode = NULL;
    visited[i] = 1;
    printf("%d ", i);
    tempNode = graphList->graphListArray[i].next;
    while (tempNode != NULL)
    {
        if (!visited[tempNode->nodeno])
        DFS(graphList,visited,tempNode->nodeno);
        tempNode=tempNode->next;
         }
}


void DFSGraphList(GraphList* graphList)
{
    int i;
    
    int *visited = (int*)malloc(sizeof(int)* graphList->size);

    
    for (i = 0; i < graphList->size; i++)
        visited[i] = 0;

    for (i = 0; i < graphList->size; i++)
    if (!visited[i]) 
        DFS(graphList, visited, i);
}


int main()
{
    GraphList *graphList = NULL;
    graphList = InitGraph(6);
    ReadGraph(graphList);
    DFSGraphList(graphList);
    return 0;
}