本文共 1231 字,大约阅读时间需要 4 分钟。
建图 与前面类似(邻接表)
图相关结构:
#define MAXVEX 100typedef char VertexType;typedef struct QNode { int front, rear; int data[MAXVEX]; int size;}Queue;typedef struct ENode { int ivex;//顶点 索引 struct ENode* next;}ENode;typedef struct VNode { VertexType data; // 顶点 信息 ENode* first_edge;}VNode;typedef struct Graph { VNode vex[MAXVEX]; int vex_num, edge_num;}Graph;
int has_circle(Graph g){ Queue q; init_queue(&q); int i, j, index; index = 0; int* ins;//记录 各顶点入度 char* topos;//记录排序结果 int num; num = g.vex_num; ENode* node; ins = (int*)malloc(sizeof(int)*num); topos = (char*)malloc(sizeof(char)*num); memset(ins, 0, sizeof(int)*num); memset(topos, 0, sizeof(char)); for (i = 0; i < g.vex_num; i++) {//算入度 过程 node = g.vex[i].first_edge; while (node != NULL) { ins[node->ivex]++; node = node->next; } } for (i = 0; i < g.vex_num; i++) { if (ins[i] == 0) //把所有入度为0的顶点入队 { enqueue(i, &q); } } while (!is_empty(q)) { j = q_front(q); topos[index++] = g.vex[j].data;//出队 记录进排序结果里 dequeue(&q); node = g.vex[j].first_edge; while (node != NULL) { ins[node->ivex]--; if (ins[node->ivex] == 0) { enqueue(node->ivex, &q); } node = node->next; } } if (index != g.vex_num)//索引 记录 入队顶点数目 如果无环 则应该相等 return 1; else return 0;}
转载地址:http://uximi.baihongyu.com/