• 图中是否有环

  • 定义一个带权无向图的数据结构如下：

    ---

    
  
  typedef struct GraphStruct{
        int   vertex_num;
      int   edge_num;
        int **edges;
  }GraphStruct;
    typedef struct GraphStruct *Graph;
    typedef unsigned int Vertex;
    
    typedef struct {
      Vertex v;
    Vertex w;
      int    weight;
  } Edge;
  

  ---

  其中 edges 指向图的邻接矩阵，矩阵元素为对应边上的权重(权重为自然数)，请使用该数据结构，从标准输入读入一个图，并判断该图是否有环，如果有环，则输出yes，否则输出no。

  输入数据示例如下：

  ---

  
  
  15,7
  0,7,69
  1,10,68
  3,9,71
  3,12,92
  4,6,71
  4,8,6
  5,10,83
  

  ---

  其中第１行分别为图中结点的个数 15、图中边的个数 7；之后的7行分别是各边的信息，以第2行为例，其表示结点0和7之间有权重为69的无向边。

---

以下是个人的题解

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

typedef struct GraphStruct {
    int vertex_num;
    int edge_num;
    int **edges;
} GraphStruct;

typedef struct GraphStruct *Graph;
typedef unsigned int Vertex;


Graph create_graph(int vertex_num, int edge_num) {
    Graph g = (Graph)malloc(sizeof(GraphStruct));
    g->vertex_num = vertex_num;
    g->edge_num = edge_num;
    g->edges = (int **)malloc(vertex_num * sizeof(int *));
    for (int i = 0; i < vertex_num; i++) {
        g->edges[i] = (int *)calloc(vertex_num,sizeof(int));
    }
    return g;
}

bool dfs(Graph g, Vertex v, bool visited[], int parent) {
    visited[v] = true;
    for (int w = 0; w < g->vertex_num; w++) {
        if (g->edges[v][w] != 0) { 
            if (!visited[w]) {
                if (dfs(g, w, visited, v)) {
                    return true;
                }
            } else if (w != parent) {
                return true; 
            }
        }
    }
    return false;
}

bool has_cycle(Graph g) {
    bool *visited = (bool *)calloc(g->vertex_num, sizeof(bool));
    if (visited == NULL) return false;
    for (int v = 0; v < g->vertex_num; v++) {
        if (!visited[v]) {
            if (dfs(g, v, visited, -1)) {
                free(visited);
                return true;
            }
        }
    }
    free(visited);
    return false;
}

int main() {
    int vertex_num, edge_num;
    scanf("%d,%d", &vertex_num, &edge_num);
    if (vertex_num <= 0 || edge_num <= 0) {
        printf("no");
        return 0;}
    Graph g = create_graph(vertex_num, edge_num);

    for (int i = 0; i < edge_num; i++) {
        Vertex v, w;
        int weight;
        scanf("%u,%u,%d", &v, &w, &weight);
        if (v >= vertex_num || w >= vertex_num) return 0;
        g->edges[v][w] = weight;
        g->edges[w][v] = weight;
    }

    if (has_cycle(g)) {
        printf("yes\n");
    } else {
        printf("no\n");
    }
    return 0;
}