18 C语言实现深度优先搜索

#include "stdio.h"
#include "stdlib.h"
#include "stdbool.h"#define MaxVertex 10typedef char ElemType;typedef struct Node { //链表中的值int nextVertex;//指向的位置struct Node *next;
} Node;struct HeadNode {//链表头ElemType data;struct Node *next;
};typedef struct AdjacencyGraph {int vertexCount;//顶点数int edgeCount;//边数struct HeadNode vertex[MaxVertex];//顶点数组
} Graph;Graph *create_graph() {Graph *graph = (Graph *) malloc(sizeof(Graph));if (graph == NULL) {exit(-1);}graph->vertexCount = 0;graph->edgeCount = 0;return graph;
}void insert_vertex(Graph *graph, ElemType data) {if (graph->vertexCount >= MaxVertex) {return;}graph->vertex[graph->vertexCount].data = data;graph->vertex[graph->vertexCount].next = NULL;graph->vertexCount++;
}void insert_edge(Graph *graph, int a, int b) {Node *node = graph->vertex[a].next;Node *newNode = malloc(sizeof(struct Node));newNode->next = NULL;newNode->nextVertex = b;if (node == NULL) {graph->vertex[a].next = newNode;} else {do {if (node->nextVertex == b) {free(newNode);break;}if (node->next) {node = node->next;} else {break;}} while (1);node->next = newNode;}graph->edgeCount++;
}void printGraph(Graph *graph) {for (int i = 0; i < graph->vertexCount; ++i) {printf("%d | %c", i, graph->vertex[i].data);Node *node = graph->vertex[i].next;while (node) {printf(" -> %d", node->nextVertex);node = node->next;}putchar('\n');}
}/*** 深度优先搜索* @param graph 图* @param start 开始顶点* @param target 结束顶点* @param visited 已经访问过的内容* @return*/
bool dfs(Graph *graph, int start, int target, int *visited) {printf("%c -> ", graph->vertex[start].data);visited[start] = 1;if (start == target) {return true;}Node *node = graph->vertex[start].next;while (node) {if (visited[node->nextVertex] == 0) {if (dfs(graph, node->nextVertex, target, visited)) {return true;}}node = node->next;}return false;
}int main() {setbuf(stdout, NULL);Graph *graph = create_graph();for (int i = 'A'; i <= 'F'; ++i) {insert_vertex(graph, (char) i);}insert_edge(graph, 0, 1);//A->Binsert_edge(graph, 1, 2);//B->Cinsert_edge(graph, 1, 3);//B->Dinsert_edge(graph, 1, 4);//B->Einsert_edge(graph, 4, 5);//E->FprintGraph(graph);int arr[graph->vertexCount];for (int i = 0; i < graph->vertexCount; ++i) {arr[i] = 0;}printf("\n%d ", dfs(graph, 0, 5, arr));free(graph);return 0;
}

运行效果