2024年5月11日发(作者：电脑壁纸高清全屏简约)

深度优先搜索算法—DFS

深度优先搜索算法—DFS

图的遍历方法主要有两种：深度优先搜索遍历（DFS）和广度优先搜索

遍历

深度优先搜索遍历类似于树的先序遍历，尽可能从纵深方向进行搜索，

简单来说，DFS就是想找到最长的路径，基本思想是从图某个顶点V0V_0

开始，访问此顶点，然后依次从V0V_0的各个没有访问的邻接点出发深度

优先搜索遍历图，直至图中所有和V0V_0有路径连通的顶点都被访问到，

若图是连通图，则遍历结束，否则，图中还有顶点未被访问，则另选图中

一个未被访问的顶点作为新的出发点，重复此过程，直至图中所有顶点都

被访问到。

首先看一下邻接表的数据结构：

typedef struct Node {

int vertex;

struct Node* next;

}Node; --存放链表中的结点信息

typedef struct head {

char data;

Node *first;

}Head, *Graph; --Graph是一个指向邻接表的指针（指向了一个数据

类型为Head的数组）

下图是一个邻接表的图示：

下面就需要建立这样一个邻接表：

Graph createGraph() {

Graph h = (Graph)malloc(sizeof(Head) * Num); --建立数组部分

for(i = 0; i Num; i++) {

h[i].data = i + 65;

h[i].first = createLink();

return h;

Node* createLink() { --建立右边的链表部分

Node *nod = NULL;

int index;

Node *node;

printf("请输入结点的个数: ");

scanf("%d", n);

printf("请输入结点的下标: ");

scanf("%d", index);

nod = (Node *)malloc(sizeof(Node));

nod-next = NULL;

nod-vertex = index;

while(--n) {

printf("请输入结点的下标: ");

scanf("%d", index);