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);elsescanf("%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;elsereturn -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;elsereturn 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;
}

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