寻圈法编程用C语言实现

用C语言实现：面向查找并输出无向图中的一个圈，需要举例截图，要在VS能运行。

参考该博客修改：
https://blog.csdn.net/myRealization/article/details/107812221

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

// 定义邻接表中的边结构体
typedef struct Edge {
    int dest;  // 边的目标结点编号
    struct Edge* next;  // 指向下一个邻接边的指针
} Edge;

// 定义邻接表中的顶点结构体
typedef struct Vertex {
    int num;  // 顶点编号
    Edge* adj;  // 指向第一个邻接边的指针
} Vertex;

// 无向图邻接表
typedef struct Graph {
    int numVertexes;  // 顶点数
    Vertex* vertices;  // 指向顶点数组的指针
} Graph;

Graph* createGraph(int numVertexes) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertexes = numVertexes;
    graph->vertices = (Vertex*)malloc(numVertexes * sizeof(Vertex));
    for (int i = 0; i < numVertexes; ++i) {
        graph->vertices[i].num = i;
        graph->vertices[i].adj = NULL;
    }
    return graph;
}

void destroyGraph(Graph* graph) {
    for (int i = 0; i < graph->numVertexes; ++i) {
        Edge* p = graph->vertices[i].adj;
        while (p != NULL) { // 遍历当前顶点的所有邻接边
            Edge* temp = p;
            p = p->next;
            free(temp);
        }
    }
    free(graph->vertices);
    free(graph);
}

void addEdge(Graph* graph, int v, int w) {
    if (v == w) return; // 不允许自环

    // 新建一条边，将其插入到顶点v的邻接表中
    Edge* newEdge1 = (Edge*)malloc(sizeof(Edge));
    newEdge1->dest = w;
    newEdge1->next = graph->vertices[v].adj;
    graph->vertices[v].adj = newEdge1;

    // 新建一条边，将其插入到顶点w的邻接表中
    Edge* newEdge2 = (Edge*)malloc(sizeof(Edge));
    newEdge2->dest = v;
    newEdge2->next = graph->vertices[w].adj;
    graph->vertices[w].adj = newEdge2;
}

// 递归算法, 使用visited[]和parent判断
// 顶点v可达的子图(连通分量)中是否存在环,如果存在则输出所有环
int isCyclicUtilDFS(Graph* graph, int v, int visited[], int parent[], int path[]) {
    visited[v] = 1; // 标记当前结点访问过
    // 对当前顶点的所有邻接点进行迭代
    for (Edge* e = graph->vertices[v].adj; e != NULL; e = e->next) {
        int i = e->dest;
        if (!visited[i]) { // 如果邻接点没有被访问过,递归访问
            parent[i] = v;      //记录父节点
            // 在 path 数组添加当前结点，表示我们正在访问这个结点
            path[i] = v;
            if (isCyclicUtilDFS(graph, i, visited, parent, path)) { // 发现存在环,返回1
                return 1; //及时退出
            }
        }
        else if (i != parent[v]) { // 被访问过，但不是当前结点v的父节点，说明存在环
            printf("Cycle found: ");
            // 输出环路路径
            for (int j = v; j != -1; j = parent[j]) {
                printf("%d -> ", j);
            }
            printf("%d\n", v);
            return 1; // 返回1
        }
    }

    return 0;
}

// 如果无向图中含有环,返回1,否则返回0
int isCyclicDFS(Graph* graph) {
    // 标记所有顶点为未访问
    int* visited = (int*)calloc(graph->numVertexes, sizeof(int));
    int* parent = (int*)calloc(graph->numVertexes, sizeof(int));
    int* path = (int*)calloc(graph->numVertexes, sizeof(int));
    for (int i = 0; i < graph->numVertexes; ++i) {
        visited[i] = 0;
        parent[i] = -1;
        path[i] = -1; // 初始状态，-1 表示不在路径中
    }

    // 对每个未访问过的顶点,调用isCyclicUtil判断环是否存在
    for (int u = 0; u < graph->numVertexes; ++u) {
        if (!visited[u]) { // 不对已经访问过的顶点进行递归
            path[u] = u;
            if (isCyclicUtilDFS(graph, u, visited, parent, path)) {
                free(visited);
                free(parent);
                free(path);
                return 1;
            }
        }
    }

    free(visited);
    free(parent);
    free(path);
    return 0;
}

int main() {
    int numVertexes, numEdges;
    printf("请键入顶点的数量： ");
    scanf("%d", &numVertexes);
    printf("请键入边的数量：");
    scanf("%d", &numEdges);

    Graph* g = createGraph(numVertexes);

    printf("请依次输入每条边的起点和终点顶点编号：\n");
    for (int i = 0; i < numEdges; ++i) {
        int v, w;
        scanf("%d%d", &v, &w);
        addEdge(g, v, w);
    }

    if (isCyclicDFS(g)) {
        printf("Contains Cycle!\n");
    }
    else {
        printf("Doesn't Contain Cycle!\n");
    }

    destroyGraph(g);
    return 0;
}

基于new bing部分指引作答：
运行截图：

以下是使用C语言编写的一个寻找并输出无向图中一个圈的示例代码。请注意，由于图的输入是动态的，这里使用了邻接矩阵表示图结构，并在代码中提供了一个示例输入矩阵。你可以根据需要修改输入矩阵。

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

#define MAX_VERTICES 100

// 邻接矩阵表示的图结构
typedef struct {
    int vertices[MAX_VERTICES][MAX_VERTICES];
    int numVertices;
} Graph;

// 初始化图
void initGraph(Graph *graph, int numVertices) {
    graph->numVertices = numVertices;
    int i, j;
    for (i = 0; i < numVertices; i++) {
        for (j = 0; j < numVertices; j++) {
            graph->vertices[i][j] = 0;
        }
    }
}

// 添加边
void addEdge(Graph *graph, int startVertex, int endVertex) {
    graph->vertices[startVertex][endVertex] = 1;
    graph->vertices[endVertex][startVertex] = 1;
}

// 深度优先搜索，寻找圈
int dfs(Graph *graph, int v, int visited[], int parent) {
    visited[v] = 1;
    int i;
    for (i = 0; i < graph->numVertices; i++) {
        if (graph->vertices[v][i]) {
            if (!visited[i]) {
                if (dfs(graph, i, visited, v)) {
                    return 1;
                }
            } else if (i != parent) {
                return 1;
            }
        }
    }
    return 0;
}

// 寻找并输出一个圈
void findCycle(Graph *graph) {
    int visited[MAX_VERTICES] = {0};
    int i;
    for (i = 0; i < graph->numVertices; i++) {
        if (!visited[i]) {
            if (dfs(graph, i, visited, -1)) {
                printf("Found a cycle in the graph!\n");
                return;
            }
        }
    }
    printf("No cycle found in the graph.\n");
}

int main() {
    // 创建一个无向图
    Graph graph;
    int numVertices = 5;
    initGraph(&graph, numVertices);

    // 添加边
    addEdge(&graph, 0, 1);
    addEdge(&graph, 1, 2);
    addEdge(&graph, 2, 3);
    addEdge(&graph, 3, 4);
    addEdge(&graph, 4, 0);

    // 查找并输出圈
    findCycle(&graph);

    return 0;
}

你可以将以上代码复制到Visual Studio（或其他C语言编译环境）中，然后进行编译和运行。这个示例代码创建了一个包含5个顶点的无向图，并添加了一些边。然后它使用深度优先搜索算法来查找并输出图中的一个圈。根据上述代码提供的输入边，此图中存在一个圈。如果在你的环境中成功运行，它应该会输出"Found a cycle in the graph!"。

以下是使用 C 语言实现寻圈法的代码示例，并通过 Visual Studio 运行：

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

#define MAX_VERTICES 1000

typedef struct {
    int data[MAX_VERTICES][MAX_VERTICES];
    int n;
} Graph;

bool is_cycle_exists(Graph* g, int u, int v) {
    for (int i = u + 1; i < g->n; i++) {
        if (g->data[u][i] && g->data[i][v]) {
            return true;
        }
    }
    return false;
}

void find_cycle(Graph* g) {
    int n = g->n;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (is_cycle_exists(g, i, j)) {
                printf("Cycle found: ");
                for (int k = j; k != i; k = g->data[k][k == 0 ? n - 1 : k - 1]) {
                    printf("%d ", k);
                }
                printf("%d\n", j);
            }
        }
    }
}

int main() {
    Graph g = {{0, 1, 0, 0, 0},
               {1, 0, 1, 1, 0},
               {0, 1, 0, 1, 1},
               {0, 1, 1, 0, 1},
               {0, 0, 1, 1, 0}};
    g.n = 5;
    find_cycle(&g);
    return 0;
}

上述代码实现了一个简单的寻圈法，用于查找无向图中的圈。在代码中，使用一个结构体 Graph 表示无向图，其中 data 数组表示图中各个节点之间的边，n 表示节点数量。is_cycle_exists 函数用于判断是否存在从节点 u 到节点 v 的路径，find_cycle 函数用于查找图中是否存在环，并在控制台输出环的路径。在主函数中，定义了一个示例图 g，并调用 find_cycle 函数来查找环。

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


typedef struct link_list {
  int data;
  struct link_list *next;
}Data;

void print_list(Data *head) {
  while (head) {
    printf("%d ",head->data);
    head = head -> next;
  }
  printf("\n");
}

Data *insert_head(Data *head, int n) {
  head = (Data *)malloc (sizeof(Data));
  head -> next = NULL;
  int data;
  while(n --) {
    Data *p = (Data *)malloc(sizeof(Data));
    scanf("%d",&data);

    p -> data = data;
    p -> next = head -> next;
    head -> next = p;
  }
  return head;
}

Data *insert_tail(Data *head, int n) {
  head = (Data *)malloc(sizeof(Data));
  head -> next = NULL;
  Data *r = head;
  int data;
  while(n--) {
    Data *p = (Data *)malloc(sizeof(Data));
    scanf("%d", &data);

    p -> data = data;
    r -> next = p;
    r = p;
    p -> next = NULL;
  }
  return head;
}

Data *get_circle_list(Data *head) {
  Data *fast;
  Data *slow;
  fast  = head;
  slow = head;
  
  Data *meet = NULL;

  while (fast) {
    fast = fast -> next;
    slow = slow -> next;
    if (!fast) {
      return NULL;
    }

    fast = fast -> next;
    if(fast == slow) {
      meet = fast;
      break;
    }
  }
  
  if(meet == NULL) {
    return NULL;
  } else {
    while (!(head == meet)) {
      head = head -> next;
      meet = meet -> next;
    }
    return head;
  }
}

int main() {
  /*构造环形测试用例*/
  Data a1,a2,a3,a4,a5,a6,a7;
  a1.data = 1;
  a2.data = 2;
  a3.data = 3;
  a4.data = 4;
  a5.data = 5;
  a6.data = 6;
  a7.data = 7;

  a1.next = &a2;
  a2.next = &a3;
  a3.next = &a4;
  a4.next = &a5;
  a5.next = &a6;
  a6.next = &a7;
  /*构造环形，这里很明显环形的起点为5节点*/
  a7.next = &a5;

  printf("get circle node \n");
  Data *result = get_circle_list(&a1);
  printf("get circle node is %d\n",result -> data);
  return 0;
}

在图中找出一个环是比较基础的搜索算法。实现思路就是从每个未访问的节点运行 DFS深度优先遍历可用于检测图中的循环。具体程序可以参考:
https://blog.csdn.net/wat1r/article/details/119443596

用C语言实现的示例代码

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

#define MAX_VERTEX_NUM 100
#define ERROR -1

// 无向图结构体
typedef struct {
    int vertex[MAX_VERTEX_NUM]; // 存放图的顶点
    int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存放图的边
    int vertexNum; // 顶点数量
    int edgeNum; // 边数量
} Graph;

// 初始化无向图
void initGraph(Graph *g, int vertex[], int edge[][MAX_VERTEX_NUM], int vertexNum, int edgeNum) {
    g->vertexNum = vertexNum;
    g->edgeNum = edgeNum;
    for (int i = 0; i < vertexNum; i++) {
        g->vertex[i] = vertex[i];
        for (int j = 0; j < vertexNum; j++) {
            g->edge[i][j] = edge[i][j];
        }
    }
}

// 输出无向图
void printGraph(Graph *g) {
    printf("顶点：");
    for (int i = 0; i < g->vertexNum; i++) {
        printf("%d ", g->vertex[i]);
    }
    printf("\n");
    printf("边：\n");
    for (int i = 0; i < g->vertexNum; i++) {
        for (int j = 0; j < g->vertexNum; j++) {
            printf("%d ", g->edge[i][j]);
        }
        printf("\n");
    }
}

// DFS遍历无向图，找出一个圈
bool dfs(Graph *g, int v, int visited[], int parent) {
    visited[v] = true;
    for (int i = 0; i < g->vertexNum; i++) {
        if (g->edge[v][i] == 1) {
            if (!visited[i]) {
                if (dfs(g, i, visited, v)) {
                    return true;
                }
            }
            else if (i != parent) {
                return true;
            }
        }
    }
    return false;
}

// 查找无向图中的一个圈
void findCycle(Graph *g) {
    int visited[MAX_VERTEX_NUM] = { false };
    int parent[MAX_VERTEX_NUM] = { -1 };
    bool hasCycle = false;
    for (int i = 0; i < g->vertexNum; i++) {
        if (!visited[i]) {
            hasCycle = dfs(g, i, visited, -1);
            if (hasCycle) {
                break;
            }
        }
    }
    if (hasCycle) {
        printf("无向图中存在一个圈。\n");
    }
    else {
        printf("无向图中不存在圈。\n");
    }
}

int main() {
    int vertex[] = { 1, 2, 3, 4, 5 };
    int edge[][MAX_VERTEX_NUM] = {
        { 0, 1, 0, 0, 1 },
        { 1, 0, 1, 0, 0 },
        { 0, 1, 0, 1, 0 },
        { 0, 0, 1, 0, 1 },
        { 1, 0, 0, 1, 0 }
    };
    int vertexNum = sizeof(vertex) / sizeof(int);
    int edgeNum = vertexNum * (vertexNum - 1) / 2 - 1; // 计算边数量
    Graph g;
    initGraph(&g, vertex, edge, vertexNum, edgeNum);
    printGraph(&g);
    findCycle(&g);
    return 0;
}