写一个图论深度优先算法的代码

图论深度优先算法的代码：def DFS(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
for next in graph[start] - visited:
DFS(graph, next, visited)
return visitedgraph = {'A': set(['B', 'C']),
'B': set(['A', 'D', 'E']),
'C': set(['A', 'F']),
'D': set(['B']),
'E': set(['B', 'F']),
'F': set(['C', 'E'])}DFS(graph, 'A') # {'E', 'D', 'F', 'A', 'C', 'B'}

相关问题

用c语言写一段关于图论、逻辑的代码

以下是一个简单的使用图论和逻辑运算的代码示例：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_VERTICES 100
#define MAX_EDGES 100

typedef struct {
    int start;
    int end;
} Edge;

typedef struct {
    int vertices[MAX_VERTICES];
    Edge edges[MAX_EDGES];
    int num_vertices;
    int num_edges;
} Graph;

void add_vertex(Graph* graph, int vertex) {
    if (graph->num_vertices >= MAX_VERTICES) {
        printf("Graph is full!");
        return;
    }
    graph->vertices[graph->num_vertices++] = vertex;
}

void add_edge(Graph* graph, int start, int end) {
    if (graph->num_edges >= MAX_EDGES) {
        printf("Graph is full!");
        return;
    }
    graph->edges[graph->num_edges].start = start;
    graph->edges[graph->num_edges++].end = end;
}

bool is_connected(Graph* graph, int vertex1, int vertex2) {
    for (int i = 0; i < graph->num_edges; i++) {
        if ((graph->edges[i].start == vertex1 && graph->edges[i].end == vertex2) ||
            (graph->edges[i].start == vertex2 && graph->edges[i].end == vertex1)) {
            return true;
        }
    }
    return false;
}

bool is_path(Graph* graph, int vertex1, int vertex2) {
    if (is_connected(graph, vertex1, vertex2)) {
        return true;
    }
    bool visited[MAX_VERTICES] = {false};
    visited[vertex1] = true;
    for (int i = 0; i < graph->num_vertices; i++) {
        if (is_connected(graph, vertex1, i) && !visited[i]) {
            visited[i] = true;
            if (is_path(graph, i, vertex2)) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    Graph graph = {0};
    add_vertex(&graph, 0);
    add_vertex(&graph, 1);
    add_vertex(&graph, 2);
    add_vertex(&graph, 3);
    add_edge(&graph, 0, 1);
    add_edge(&graph, 1, 2);
    add_edge(&graph, 2, 3);
    add_edge(&graph, 3, 0);

    int vertex1 = 0;
    int vertex2 = 2;
    if (is_path(&graph, vertex1, vertex2)) {
        printf("There is a path from vertex %d to vertex %d.\n", vertex1, vertex2);
    } else {
        printf("There is no path from vertex %d to vertex %d.\n", vertex1, vertex2);
    }
    return 0;
}

这段代码定义了一个简单的图，并使用深度优先搜索算法来查找两个给定顶点之间是否存在路径。可以通过添加更多的顶点和边来扩展图的规模，并尝试不同的顶点组合来测试算法的正确性。

C语言写关于图论的代码

图论是计算机科学中的一个重要分支，其研究对象是图，即由节点和边组成的数据结构。在C语言中，我们可以使用邻接矩阵或邻接表来表示图，并使用深度优先搜索或广度优先搜索等算法来遍历图。下面是一个使用邻接矩阵表示图，并使用深度优先搜索遍历图的C语言代码示例。

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTEX_NUM 100

typedef struct {
    int vertex[MAX_VERTEX_NUM];
    int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
    int vertex_num;
    int edge_num;
} Graph;

void init_graph(Graph* g) {
    g->vertex_num = 0;
    g->edge_num = 0;
    for (int i = 0; i < MAX_VERTEX_NUM; i++) {
        g->vertex[i] = 0;
        for (int j = 0; j < MAX_VERTEX_NUM; j++) {
            g->edge[i][j] = 0;
        }
    }
}

void add_vertex(Graph* g, int v) {
    g->vertex[g->vertex_num++] = v;
}

void add_edge(Graph* g, int v1, int v2) {
    g->edge[v1][v2] = 1;
    g->edge[v2][v1] = 1;
    g->edge_num++;
}

void dfs(Graph* g, int v, int visited[]) {
    visited[v] = 1;
    printf("%d ", g->vertex[v]);
    for (int i = 0; i < g->vertex_num; i++) {
        if (g->edge[v][i] && !visited[i]) {
            dfs(g, i, visited);
        }
    }
}

int main() {
    Graph g;
    init_graph(&g);

    add_vertex(&g, 0);
    add_vertex(&g, 1);
    add_vertex(&g, 2);
    add_vertex(&g, 3);
    add_vertex(&g, 4);

    add_edge(&g, 0, 1);
    add_edge(&g, 0, 2);
    add_edge(&g, 1, 2);
    add_edge(&g, 2, 3);
    add_edge(&g, 3, 4);

    int visited[MAX_VERTEX_NUM] = {0};
    dfs(&g, 0, visited);

    return 0;
}

上述代码中，我们定义了一个Graph结构体，包含了图的节点、边信息，以及节点数和边数。我们使用init_graph函数初始化图，使用add_vertex函数添加节点，使用add_edge函数添加边。在dfs函数中，我们使用递归的方式遍历图，并使用visited数组记录节点是否被访问过。在主函数中，我们构建了一个简单的图，并使用dfs函数遍历该图。

这只是一个简单的图论例子，实际上图论的应用非常广泛，例如最短路径算法、最小生成树算法等等。希望这个例子能够帮助您更好地理解图论的基本原理和C语言的实现。