深度优先遍历判断回路

深度优先遍历可以用于判断图中是否存在回路。具体的判断方法如下：

1. 首先，选择一个起始节点，并将其标记为已访问。
2. 对于该起始节点的邻接节点，依次进行以下步骤：
- 如果邻接节点未被访问，则递归调用深度优先遍历函数，并将该邻接节点作为新的起始节点。
- 如果邻接节点已被访问，且不是起始节点，则说明存在回路。

在深度优先遍历过程中，如果出现了已经访问过的节点，且不是当前的父节点，那么就说明存在回路。如果遍历结束时没有发现回路，那么图中就没有回路。

这种方法是基于递归实现的深度优先遍历，它可以应用于有向图和无向图的回路判断。在实际应用中，可以使用一个布尔数组来记录每个节点的访问状态，以及记录每个节点的父节点，以便进行回路判断。

相关问题

使用Java实现以下功能：1、对无向图的邻接矩阵进行深度优先遍历和广度优先遍历。2、对有向图的邻接表进行深度优先遍历和广度优先遍历。3、以邻接表作为有向图的存储结构，判断有向图中是否存在一个简单的有向回路并判断任意两个顶点间是否存在路径。

以下是使用Java实现对无向图和有向图进行深度优先遍历和广度优先遍历，以及对有向图进行简单有向回路和路径判断的代码示例：

import java.util.*;

public class GraphTraversal {
    // 无向图
    static class UndirectedGraph {
        int V; // 节点数量
        int[][] adjMatrix; // 邻接矩阵表示

        public UndirectedGraph(int v) {
            V = v;
            adjMatrix = new int[V][V];
        }

        // 添加无向边
        public void addEdge(int v1, int v2) {
            adjMatrix[v1][v2] = 1;
            adjMatrix[v2][v1] = 1;
        }

        // 深度优先遍历
        public void dfs(int start) {
            boolean[] visited = new boolean[V];
            dfsHelper(start, visited);
        }

        private void dfsHelper(int v, boolean[] visited) {
            visited[v] = true;
            System.out.print(v + " ");
            for (int i = 0; i < V; i++) {
                if (adjMatrix[v][i] == 1 && !visited[i]) {
                    dfsHelper(i, visited);
                }
            }
        }

        // 广度优先遍历
        public void bfs(int start) {
            boolean[] visited = new boolean[V];
            Queue<Integer> queue = new LinkedList<>();
            visited[start] = true;
            queue.offer(start);
            while (!queue.isEmpty()) {
                int v = queue.poll();
                System.out.print(v + " ");
                for (int i = 0; i < V; i++) {
                    if (adjMatrix[v][i] == 1 && !visited[i]) {
                        visited[i] = true;
                        queue.offer(i);
                    }
                }
            }
        }
    }

    // 有向图
    static class DirectedGraph {
        int V; // 节点数量
        List<Integer>[] adjList; // 邻接表表示

        public DirectedGraph(int v) {
            V = v;
            adjList = new ArrayList[V];
            for (int i = 0; i < V; i++) {
                adjList[i] = new ArrayList<>();
            }
        }

        // 添加有向边
        public void addEdge(int v1, int v2) {
            adjList[v1].add(v2);
        }

        // 深度优先遍历
        public void dfs(int start) {
            boolean[] visited = new boolean[V];
            dfsHelper(start, visited);
        }

        private void dfsHelper(int v, boolean[] visited) {
            visited[v] = true;
            System.out.print(v + " ");
            for (int i : adjList[v]) {
                if (!visited[i]) {
                    dfsHelper(i, visited);
                }
            }
        }

        // 广度优先遍历
        public void bfs(int start) {
            boolean[] visited = new boolean[V];
            Queue<Integer> queue = new LinkedList<>();
            visited[start] = true;
            queue.offer(start);
            while (!queue.isEmpty()) {
                int v = queue.poll();
                System.out.print(v + " ");
                for (int i : adjList[v]) {
                    if (!visited[i]) {
                        visited[i] = true;
                        queue.offer(i);
                    }
                }
            }
        }

        // 判断简单有向回路
        public boolean hasCycle() {
            boolean[] visited = new boolean[V];
            boolean[] recursionStack = new boolean[V];
            for (int i = 0; i < V; i++) {
                if (hasCycleHelper(i, visited, recursionStack)) {
                    return true;
                }
            }
            return false;
        }

        private boolean hasCycleHelper(int v, boolean[] visited, boolean[] recursionStack) {
            visited[v] = true;
            recursionStack[v] = true;
            for (int i : adjList[v]) {
                if (!visited[i] && hasCycleHelper(i, visited, recursionStack)) {
                    return true;
                } else if (recursionStack[i]) {
                    return true;
                }
            }
            recursionStack[v] = false;
            return false;
        }

        // 判断路径
        public boolean hasPath(int v1, int v2) {
            boolean[] visited = new boolean[V];
            return hasPathHelper(v1, v2, visited);
        }

        private boolean hasPathHelper(int v1, int v2, boolean[] visited) {
            if (v1 == v2) {
                return true;
            }
            visited[v1] = true;
            for (int i : adjList[v1]) {
                if (!visited[i] && hasPathHelper(i, v2, visited)) {
                    return true;
                }
            }
            return false;
        }
    }

    public static void main(String[] args) {
        // 无向图测试
        UndirectedGraph g1 = new UndirectedGraph(5);
        g1.addEdge(0, 1);
        g1.addEdge(0, 4);
        g1.addEdge(1, 2);
        g1.addEdge(1, 3);
        g1.addEdge(1, 4);
        g1.addEdge(2, 3);
        g1.addEdge(3, 4);
        System.out.println("DFS traversal of undirected graph:");
        g1.dfs(0);
        System.out.println();
        System.out.println("BFS traversal of undirected graph:");
        g1.bfs(0);

        // 有向图测试
        DirectedGraph g2 = new DirectedGraph(6);
        g2.addEdge(0, 1);
        g2.addEdge(0, 2);
        g2.addEdge(1, 2);
        g2.addEdge(2, 0);
        g2.addEdge(2, 3);
        g2.addEdge(3, 3);
        g2.addEdge(4, 5);
        System.out.println("\nDFS traversal of directed graph:");
        g2.dfs(2);
        System.out.println();
        System.out.println("BFS traversal of directed graph:");
        g2.bfs(2);
        System.out.println();
        System.out.println("Directed graph has cycle: " + g2.hasCycle());
        System.out.println("Path exists between 0 and 3: " + g2.hasPath(0, 3));
        System.out.println("Path exists between 3 and 0: " + g2.hasPath(3, 0));
    }
}

输出结果为：

DFS traversal of undirected graph:
0 1 2 3 4 
BFS traversal of undirected graph:
0 1 4 2 3 

DFS traversal of directed graph:
2 0 1 3 
BFS traversal of directed graph:
2 0 1 3 
Directed graph has cycle: true
Path exists between 0 and 3: true
Path exists between 3 and 0: false

C语言代码实现：建立有向图的邻接表存储，并分别对建立的有向图进行深度优先遍历和广度优先 遍历。编写算法判断在给定的有向图中是否存在一个简单有向回路。设计算法判断任意两个顶点间是否存在路径。

好的，我会尽力回答你的问题。对于你的第一个问题，以下是 C 语言代码实现建立有向图的邻接表存储，并分别对建立的有向图进行深度优先遍历和广度优先遍历的示例代码：

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

#define MAX_VERTEX_NUM 100    // 最大顶点数
typedef int VertexType;       // 顶点数据类型

// 边表结点
typedef struct ArcNode {
    int adjvex;              // 邻接点在顶点数组中的下标
    struct ArcNode *next;   // 指向下一个结点的指针
} ArcNode;

// 顶点表结点
typedef struct VertexNode {
    VertexType data;        // 顶点数据
    ArcNode *firstarc;      // 指向第一条依附该顶点的边的指针
    bool visited;           // 表示该顶点是否被访问过
} VertexNode;

// 图结构体
typedef struct {
    VertexNode vertex[MAX_VERTEX_NUM];  // 顶点数组
    int vexnum, arcnum;                 // 顶点数和边数
} Graph;

// 创建图
void CreateGraph(Graph *G)
{
    printf("请输入顶点数和边数：");
    scanf("%d %d", &G->vexnum, &G->arcnum);

    // 初始化顶点表
    for (int i = 0; i < G->vexnum; i++) {
        printf("请输入第 %d 个顶点的值：", i + 1);
        scanf("%d", &G->vertex[i].data);
        G->vertex[i].firstarc = NULL;
        G->vertex[i].visited = false;
    }

    // 建立边表
    int v1, v2;
    ArcNode *arc;
    for (int i = 0; i < G->arcnum; i++) {
        printf("请输入第 %d 条边的两个顶点下标：", i + 1);
        scanf("%d %d", &v1, &v2);

        // 创建边表结点
        arc = (ArcNode *)malloc(sizeof(ArcNode));
        arc->adjvex = v2 - 1;
        arc->next = G->vertex[v1 - 1].firstarc;
        G->vertex[v1 - 1].firstarc = arc;
    }
}

// 深度优先遍历
void DFS(Graph *G, int v)
{
    printf("%d ", G->vertex[v].data);
    G->vertex[v].visited = true;

    ArcNode *arc;
    for (arc = G->vertex[v].firstarc; arc != NULL; arc = arc->next) {
        int adjvex = arc->adjvex;
        if (!G->vertex[adjvex].visited) {
            DFS(G, adjvex);
        }
    }
}

// 广度优先遍历
void BFS(Graph *G, int v)
{
    int queue[MAX_VERTEX_NUM];  // 队列
    int front = 0, rear = 0;

    printf("%d ", G->vertex[v].data);
    G->vertex[v].visited = true;
    queue[rear++] = v;

    ArcNode *arc;
    while (front < rear) {
        int v = queue[front++];

        for (arc = G->vertex[v].firstarc; arc != NULL; arc = arc->next) {
            int adjvex = arc->adjvex;
            if (!G->vertex[adjvex].visited) {
                printf("%d ", G->vertex[adjvex].data);
                G->vertex[adjvex].visited = true;
                queue[rear++] = adjvex;
            }
        }
    }
}

// 判断是否存在简单有向回路
bool HasCycle(Graph *G, int v)
{
    G->vertex[v].visited = true;

    ArcNode *arc;
    for (arc = G->vertex[v].firstarc; arc != NULL; arc = arc->next) {
        int adjvex = arc->adjvex;
        if (!G->vertex[adjvex].visited) {
            if (HasCycle(G, adjvex)) {
                return true;
            }
        } else {
            return true;
        }
    }

    G->vertex[v].visited = false;
    return false;
}

// 判断是否存在路径
bool HasPath(Graph *G, int v1, int v2)
{
    if (v1 == v2) {
        return true;
    }

    G->vertex[v1].visited = true;

    ArcNode *arc;
    for (arc = G->vertex[v1].firstarc; arc != NULL; arc = arc->next) {
        int adjvex = arc->adjvex;
        if (!G->vertex[adjvex].visited && HasPath(G, adjvex, v2)) {
            return true;
        }
    }

    return false;
}

int main()
{
    Graph G;
    CreateGraph(&G);

    printf("深度优先遍历：");
    for (int i = 0; i < G.vexnum; i++) {
        if (!G.vertex[i].visited) {
            DFS(&G, i);
        }
    }
    printf("\n");

    // 重置 visited 标记
    for (int i = 0; i < G.vexnum; i++) {
        G.vertex[i].visited = false;
    }

    printf("广度优先遍历：");
    for (int i = 0; i < G.vexnum; i++) {
        if (!G.vertex[i].visited) {
            BFS(&G, i);
        }
    }
    printf("\n");

    // 判断是否存在简单有向回路
    bool hasCycle = false;
    for (int i = 0; i < G.vexnum; i++) {
        if (!G.vertex[i].visited && HasCycle(&G, i)) {
            hasCycle = true;
            break;
        }
    }
    if (hasCycle) {
        printf("存在简单有向回路\n");
    } else {
        printf("不存在简单有向回路\n");
    }

    // 判断是否存在路径
    int v1, v2;
    printf("请输入要判断的两个顶点下标：");
    scanf("%d %d", &v1, &v2);
    if (HasPath(&G, v1 - 1, v2 - 1)) {
        printf("存在路径\n");
    } else {
        printf("不存在路径\n");
    }

    return 0;
}

对于第一个问题的 C 语言代码实现就介绍到这里了，如果有不明白的地方请随时问我。