实现基于邻接表表示的深度优先遍历。 函数接口定义： void DFS(ALGraph G, int v); 其中 G 是基于邻接表存储表示的无向图，v表示遍历起点。 裁判测试程序样例： #include <stdio.h> #include <stdlib.h> #define MVNum 10 int visited[MVNum]; typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; int info; }ArcNode; typedef struct VNode{ char data; ArcNode *firstarc; }VNode, AdjList[MVNum]; typedef struct{ AdjList vertices; int vexnum, arcnum; }ALGraph; int CreateUDG(ALGraph &G);//实现细节隐藏 void DFS(ALGraph G, int v); void DFSTraverse(ALGraph G){ int v; for(v = 0; v < G.vexnum; ++v) visited[v] = 0; for(v = 0; v < G.vexnum; ++v) if(!visited[v]) DFS(G, v); } int main(){ ALGraph G; CreateUDG(G); DFSTraverse(G); return 0; } /* 请在这里填写答案 */ 输入样例： 输入第1行为结点数vexnum和边数arcnum。第2行为结点的值，依次输入arcnum行，每行输入两个结点的值表示该两个结点互为邻接点。 8 8 ABCDEFGH A B A C B D B E C F C G D H E H 输出样例： 遍历序列。 A C G F B E H D QQ截图20191125133700.png 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

#include <stdio.h>
#include <stdlib.h>
#define MVNum 10
int visited[MVNum];

typedef struct ArcNode{
    int adjvex;
    struct ArcNode *nextarc;
    int info;
}ArcNode;

typedef struct VNode{
    char data;
    ArcNode *firstarc;
}VNode, AdjList[MVNum];

typedef struct{
    AdjList vertices;
    int vexnum, arcnum;
}ALGraph;

int CreateUDG(ALGraph &G);//实现细节隐藏
void DFS(ALGraph G, int v);

void DFSTraverse(ALGraph G){
    int v;
    for(v = 0; v < G.vexnum; ++v)
        visited[v] = 0;
    for(v = 0; v < G.vexnum; ++v)
        if(!visited[v])
            DFS(G, v);
}

int main(){
    ALGraph G;
    CreateUDG(G);
    DFSTraverse(G);
    return 0;
}

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