8648 图的深度遍历

### 思路
1. **图的邻接表存储结构**：使用邻接表存储图的顶点和边信息。
2. **基本操作函数**：包括创建图、查找顶点、获取顶点值、获取第一个邻接顶点、获取下一个邻接顶点等。
3. **深度优先遍历（DFS）**：从某个顶点出发，递归地访问所有未访问的邻接顶点。

### 伪代码
1. **创建图**：
   - 读取图的类型、顶点数和边数。
   - 初始化顶点信息和邻接表。
   - 读取每条边的信息，更新邻接表。

2. **深度优先遍历（DFS）**：
   - 初始化访问标志数组。
   - 对每个未访问的顶点调用DFS函数。
   - 在DFS函数中，标记当前顶点为已访问，并递归访问所有未访问的邻接顶点。

### C++代码
 

#include "string.h"
#include "malloc.h"
#include "stdio.h"
#include "stdlib.h"

typedef int InfoType;
#define MAX_NAME 3
typedef char VertexType[MAX_NAME];
#define MAX_VERTEX_NUM 20
typedef enum { DG, DN, AG, AN } GraphKind;

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

typedef struct {
    VertexType data;
    ArcNode *firstarc;
} VNode, AdjList[MAX_VERTEX_NUM];

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

int LocateVex(ALGraph G, VertexType u) {
    for (int i = 0; i < G.vexnum; ++i)
        if (strcmp(u, G.vertices[i].data) == 0)
            return i;
    return -1;
}

void CreateGraph(ALGraph *G) {
    int i, j, k, w;
    VertexType va, vb;
    ArcNode *p;
    scanf("%d", &(*G).kind);
    scanf("%d%d", &(*G).vexnum, &(*G).arcnum);
    for (i = 0; i < (*G).vexnum; ++i) {
        scanf("%s", (*G).vertices[i].data);
        (*G).vertices[i].firstarc = NULL;
    }
    for (k = 0; k < (*G).arcnum; ++k) {
        if ((*G).kind == 1 || (*G).kind == 3)
            scanf("%d%s%s", &w, va, vb);
        else
            scanf("%s%s", va, vb);
        i = LocateVex(*G, va);
        j = LocateVex(*G, vb);
        p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex = j;
        if ((*G).kind == 1 || (*G).kind == 3) {
            p->info = (int *)malloc(sizeof(int));
            *(p->info) = w;
        } else {
            p->info = NULL;
        }
        p->nextarc = (*G).vertices[i].firstarc;
        (*G).vertices[i].firstarc = p;
        if ((*G).kind >= 2) {
            p = (ArcNode *)malloc(sizeof(ArcNode));
            p->adjvex = i;
            if ((*G).kind == 3) {
                p->info = (int *)malloc(sizeof(int));
                *(p->info) = w;
            } else {
                p->info = NULL;
            }
            p->nextarc = (*G).vertices[j].firstarc;
            (*G).vertices[j].firstarc = p;
        }
    }
}

VertexType *GetVex(ALGraph G, int v) {
    if (v >= G.vexnum || v < 0)
        exit(0);
    return &G.vertices[v].data;
}

int FirstAdjVex(ALGraph G, VertexType v) {
    int v1 = LocateVex(G, v);
    ArcNode *p = G.vertices[v1].firstarc;
    if (p)
        return p->adjvex;
    else
        return -1;
}

int NextAdjVex(ALGraph G, VertexType v, VertexType w) {
    int v1 = LocateVex(G, v);
    int w1 = LocateVex(G, w);
    ArcNode *p = G.vertices[v1].firstarc;
    while (p && p->adjvex != w1)
        p = p->nextarc;
    if (!p || !p->nextarc)
        return -1;
    else
        return p->nextarc->adjvex;
}

int visited[MAX_VERTEX_NUM];
void (*VisitFunc)(char *v);

void DFS(ALGraph G, int v) {
    visited[v] = 1;
    VisitFunc(G.vertices[v].data);
    for (int w = FirstAdjVex(G, G.vertices[v].data); w >= 0; w = NextAdjVex(G, G.vertices[v].data, G.vertices[w].data)) {
        if (!visited[w])
            DFS(G, w);
    }
}

void DFSTraverse(ALGraph G) {
    for (int i = 0; i < G.vexnum; i++)
        visited[i] = 0;
    VisitFunc = print;
    for (int i = 0; i < G.vexnum; i++) {
        if (!visited[i])
            DFS(G, i);
    }
    printf("\n");
}

void print(char *i) {
    printf("%s ", i);
}

int main() {
    ALGraph g;
    CreateGraph(&g);
    DFSTraverse(g);
    return 1;
}

### 总结
该代码实现了图的邻接表存储结构，并提供了基本操作函数和深度优先遍历算法。通过输入图的类型、顶点数、边数和边的信息，构建图的邻接表，并进行深度优先遍历，输出遍历结果。