c语言有向图自环怎么办

在C语言中，有向图自环的处理主要依赖于数据结构和算法的选择，自环是指从一个顶点出发，经过一些边后又返回到这个顶点的路径，在有向图中，自环的存在可能会导致一些问题，例如在计算最短路径时可能会产生无限循环，处理自环的方法主要是在数据结构设计和算法实现上进行优化。

（图片来源网络，侵删）

我们需要选择合适的数据结构来表示有向图，常用的有向图表示方法有邻接矩阵和邻接表，邻接矩阵是二维数组，其中每个元素表示两个顶点之间是否存在边，邻接表是链表，其中每个节点表示一个顶点，每个节点包含一个链表，表示与该顶点相邻的其他顶点，对于自环的处理，邻接矩阵更为简单直观。

1、邻接矩阵表示法

在邻接矩阵中，自环可以通过将对应的元素值设为负无穷大（或无穷大）来表示，这样，在计算最短路径时，可以忽略这些自环，以下是一个简单的示例：

#include <stdio.h>
#include <limits.h>
#define MAX_VERTEX_NUM 100
int main() {
    int vertex_num, edge_num;
    printf("请输入顶点数和边数：");
    scanf("%d%d", &vertex_num, &edge_num);
    int matrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM] = {0};
    printf("请输入边的连接关系（以空格分隔）：
");
    for (int i = 0; i < edge_num; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        matrix[u][v] = 1; // 自环，边的权重为1
    }
    // 输出邻接矩阵
    for (int i = 0; i < vertex_num; i++) {
        for (int j = 0; j < vertex_num; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("
");
    }
    return 0;
}

2、邻接表表示法

在邻接表中，自环的处理相对复杂一些，一种方法是在创建邻接表时，检查每个顶点的出度，如果出度大于1，则认为存在自环，另一种方法是在遍历邻接表时，检查每个顶点的出度，如果出度大于1，则删除多余的边，以下是一个简单的示例：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_VERTEX_NUM 100
#define INFINITY INT_MAX
typedef struct ArcNode {
    int adjvex; // 邻接点域，存储该顶点对应的下标
    int weight; // 权值域，存储该边的权值，可以为负无穷大表示自环
    struct ArcNode *nextarc; // 下一个邻接点域，指向下一个邻接点
} ArcNode;
typedef struct VNode {
    int data; // 顶点域，存储顶点信息
    ArcNode *firstarc; // 第一个邻接点域，指向第一个邻接点
} VNode, AdjList[MAX_VERTEX_NUM]; // 邻接表类型定义，使用数组存储顶点信息和邻接点信息
void CreateALGraph(AdjList *G, int vertex_num, int edge_num) {
    int i, j, k;
    for (i = 0; i < vertex_num; i++) { // 初始化所有顶点的firstarc域为空指针
        G[i].firstarc = NULL;
    }
    for (k = 0; k < edge_num; k++) { // 读取边信息并建立边表结点
        int start, end, weight;
        scanf("%d%d%d", &start, &end, &weight); // 输入边的两个端点和权重（可以为负无穷大表示自环）
        ArcNode *arc = (ArcNode *) malloc(sizeof(ArcNode)); // 申请边表结点空间并赋值，weight为1表示自环
        arc>adjvex = end; // 终点域为end（入边）或start（出边）
        arc>weight = weight == 1 ? INFINITY : weight; // 如果权重为1，则设置边权重为负无穷大（表示自环）
        arc>nextarc = G[start].firstarc; // 将此边表结点插入到start的边表头指针域指向的单链表中（即起点的出边）
        G[start].firstarc = arc; // 修改start的边表头指针域（即起点的出边）为新插入的边表结点（即起点的出边）
    }
}

3、算法优化

处理自环的关键在于选择合适的算法，在计算最短路径时，可以使用Dijkstra算法、Floyd算法等，这些算法在处理自环时需要注意权重的设置，在使用Dijkstra算法时，可以将自环的权重设置为正无穷大；在使用Floyd算法时，可以将自环的对角线元素设置为正无穷大，这样可以确保在计算过程中忽略自环的影响。