#include运行结果 邻接表法#include #define Inf 32767 //定义∞ #define MaxVertenNum 20 //顶点数目的最大值 typedef char VertexType; //顶点的数据类型 typedef int EdgeType; //存放顶点信息 typedef struct { VertexType Vex[MaxVertenNum]; //顶点表 EdgeType Edge[MaxVertenNum][MaxVertenNum]; //邻接矩阵 int vexnum, edgenum; //图的当前顶点数和边数 }MGraph; void InitG(MGraph& g) //初始化 { int i, j; for (i = 0; i < MaxVertenNum; i++) g.Vex[i] = ' '; for (i = 0; i < MaxVertenNum; i++) for (j = 0; j < MaxVertenNum; j++) g.Edge[i][j] = 0; g.vexnum = 0; g.edgenum = 0; } void CreateVex(MGraph& g) //创建顶点信息 { int i = 0, count = 0; printf("输入图的顶点："); VertexType ch = getchar(); while (ch != '#') { g.Vex[i++] = ch; ch = getchar(); count++; //统计顶点个数 } g.vexnum = count; } void CreateEdge(MGraph& g) //创建邻接矩阵信息 { EdgeType b; printf("输入邻接矩阵信息：n"); for (int i = 0; i < g.vexnum; i++) for (int j = 0; j < g.vexnum; j++) { scanf("%d", &b); g.Edge[i][j] = b; } } void Info(MGraph& g) //图的顶点数和边数 { int count = 0; for (int i = 0; i < g.vexnum; i++) for (int j = 0; j < g.vexnum; j++) if (g.Edge[i][j] > 0) count++; g.edgenum = count / 2; } void PrintG(MGraph g) { int i, j; for (i = 0; i < g.vexnum; i++) { for (j = 0; j < g.vexnum; j++) if (g.Edge[i][j] > 0 && g.Edge[i][j] < Inf) printf("%c->%c(权值为：%d) ", g.Vex[i], g.Vex[j], g.Edge[i][j]); printf("n"); } } void PrintMatrix(MGraph g) //输出邻接矩阵 { int i, j; printf("输出邻接矩阵：n"); for (i = 0; i < g.vexnum; i++) printf("t%c", g.Vex[i]); printf("n"); for (i = 0; i < g.vexnum; i++) { printf("%c", g.Vex[i]); for (j = 0; j < g.vexnum; j++) printf("t%d", g.Edge[i][j]); printf("n"); } printf("n"); } //-----并查集部分----- typedef struct { VertexType data; //数据域 int parent; //双亲结点域 }UFSets[MaxVertenNum]; //并查集类型 void Initial(MGraph g, UFSets S[]) //初始化 { for (int i = 0; i < MaxVertenNum; i++) { S[i]->data = g.Vex[i]; //对应图中各顶点的数据 S[i]->parent = -1; //每个自成单个元素集合，初始时父结点全部设为-1 } } int Find(UFSets S[], VertexType x, int num) //Find优化(即路径压缩) { int i = 0, j; while (S[i]->data != x) i++; //这里传入的是数据结点信息，不是数组下标，因此需要遍历一次 if (i >= num) return -999; //不存在值为x的数据结点 j = i; while (S[j]->parent >= 0) j = S[j]->parent; //通过双亲结点不断向上找树的根 while (S[i]->parent >= 0) { int t = S[i]->parent; S[i]->parent = j; i = t; } return j; //返回根结点信息 } bool Union(UFSets S[], VertexType x, VertexType y, int num) //Union优化(即将小集合并入大集合中) { int Root1 = Find(S, x, num); //查找子集x的根结点 int Root2 = Find(S, y, num);; //查找子集y的根结点 if (Root1 == Root2) return false; //根结点相同则不进行合并 if (abs(S[Root1]->parent) > abs(S[Root2]->parent)) { S[Root1]->parent += S[Root2]->parent; //集合中总结点数增加 S[Root2]->parent = Root1; } else { S[Root2]->parent += S[Root1]->parent; //集合中总结点数增加 S[Root1]->parent = Root2; } return true; } bool CountConnect(MGraph g, UFSets S[],int &count) { int i, j; count = 0; //用来统计图中的连通分量数 bool flag = false; //用来判断图中是否存在环 for (i = 0; i < g.vexnum; i++) //遍历邻接矩阵的上三角区域 for (j = i + 1; j < g.vexnum; j++) if (g.Edge[i][j] > 0) //如果两个顶点之间有路径 { if (Find(S, g.Vex[i], g.vexnum) != Find(S, g.Vex[j], g.vexnum)) //如果两个顶点不属于同一个集合 Union(S, g.Vex[i], g.Vex[j], g.vexnum); //将两个顶点并入同一个集合 else flag = true; } for (i = 0; i < g.vexnum; i++) if (S[i]->parent < 0) count++; return flag; } void Print(UFSets S[], int num) //打印数组中结点的信息 { for (int i = 0; i < num; i++) printf("n%c(%d)", S[i]->data, S[i]->parent); //打印数据信息以及双亲结点信息 } int main() { MGraph g; VertexType Vex[MaxVertenNum]; EdgeType Edge[MaxVertenNum][MaxVertenNum]; InitG(g); CreateVex(g); CreateEdge(g); Info(g); printf("n无向图G中共有：%d个顶点，%d条边n", g.vexnum, g.edgenum); PrintMatrix(g); printf("输出无向图G中各顶点的连接情况：n"); PrintG(g); UFSets S[MaxVertenNum]; int count; Initial(g, S); bool flag = CountConnect(g, S, count); printf("n该图的连通分量数为：%d", count); printf("n图中存在环吗？—%d(0代表不存在，1代表存在)",flag); printf("n输出并查集中数组的信息："); Print(S, g.vexnum); return 0; }
#include运行结果#include #include #define MaxVertexNum 100 typedef char VertexType; typedef struct ArcNode { int adjvex; //该边的邻接点编号 struct ArcNode* nextarc; //指向下条边的指针 //int weight; //该边的相关信息，如权值 }ArcNode; //边结点的类型 typedef struct VNode { VertexType data; //顶点信息 ArcNode* firstarc; //指向第一个边结点 }VNode; typedef struct { VNode adjlist[MaxVertexNum]; //邻接表的头结点数组 int vexnum, edgenum; //图中的顶点数和边数 }AdjGraph; //完整的图邻接表类型 void InitG(AdjGraph& g) { int i; for (i = 0; i < MaxVertexNum; i++) { g.adjlist[i].data = ' '; g.adjlist[i].firstarc = NULL; } g.vexnum = 0; g.edgenum = 0; } void CreateVNde(AdjGraph& g) { int i = 0, count = 0; printf("输入图的顶点："); VertexType ch = getchar(); while (ch != '#') //#表示结束输入 { g.adjlist[i].data = ch; i++; count++; //统计顶点个数 ch = getchar(); } g.vexnum = count; } void CreateANode(AdjGraph& g, VertexType ch, int num) { ArcNode* p, * r = g.adjlist[0].firstarc; int i, j, k; while (num--) { p = (ArcNode*)malloc(sizeof(ArcNode)); p->nextarc = NULL; printf("输入顶点的编号："); scanf("%d", &i); for (j = 0; j < g.vexnum; j++) if (g.adjlist[j].data == ch) k = j; if (i != k) { p->adjvex = i; if (g.adjlist[k].firstarc == NULL) { g.adjlist[k].firstarc = p; r = p; } else { r->nextarc = p; r = p; } } } } //-----并查集部分----- typedef struct { VertexType data; //数据域 int parent; //双亲结点域 }UFSets[MaxVertexNum]; //并查集类型 void Initial(AdjGraph g, UFSets S[]) //初始化 { for (int i = 0; i < MaxVertexNum; i++) { S[i]->data = g.adjlist[i].data; //对应图中各顶点的数据 S[i]->parent = -1; //每个自成单个元素集合，初始时父结点全部设为-1 } } int Find(UFSets S[], VertexType x, int num) //Find优化(即路径压缩) { int i = 0, j; while (S[i]->data != x) i++; //这里传入的是数据结点信息，不是数组下标，因此需要遍历一次 if (i >= num) return -999; //不存在值为x的数据结点 j = i; while (S[j]->parent >= 0) j = S[j]->parent; //通过双亲结点不断向上找树的根 while (S[i]->parent >= 0) { int t = S[i]->parent; S[i]->parent = j; i = t; } return j; //返回根结点信息 } bool Union(UFSets S[], VertexType x, VertexType y, int num) //Union优化(即将小集合并入大集合中) { int Root1 = Find(S, x, num); //查找子集x的根结点 int Root2 = Find(S, y, num);; //查找子集y的根结点 if (Root1 == Root2) return false; //根结点相同则不进行合并 if (abs(S[Root1]->parent) > abs(S[Root2]->parent)) { S[Root1]->parent += S[Root2]->parent; //集合中总结点数增加 S[Root2]->parent = Root1; } else { S[Root2]->parent += S[Root1]->parent; //集合中总结点数增加 S[Root1]->parent = Root2; } return true; } void CountConnect(AdjGraph g, UFSets S[],int &count) { int i; count = 0; //用来统计图中的连通分量数 for (i = 0; i < g.vexnum; i++) { ArcNode* p = g.adjlist[i].firstarc; while (p != NULL) { if (Find(S, g.adjlist[i].data, g.vexnum) != Find(S, g.adjlist[p->adjvex].data, g.vexnum)) Union(S, g.adjlist[i].data, g.adjlist[p->adjvex].data, g.vexnum); p = p->nextarc; } } for (i = 0; i < g.vexnum; i++) if (S[i]->parent < 0) count++; } void Print(UFSets S[], int num) //打印数组中结点的信息 { for (int i = 0; i < num; i++) printf("n%c(%d)", S[i]->data, S[i]->parent); //打印数据信息以及双亲结点信息 } int main() { AdjGraph g; InitG(g); CreateVNde(g); printf("n"); int i, num; for (i = 0; i < g.vexnum; i++) { printf("创建顶点%c的边结点n", g.adjlist[i].data); printf("输入要创建的边结点的个数："); scanf("%d", &num); CreateANode(g, g.adjlist[i].data, num); printf("n"); } ArcNode* p; printf("输出各顶点的连接情况：n"); for (i = 0; i < g.vexnum; i++) { p = g.adjlist[i].firstarc; printf("%d(%c) ", i, g.adjlist[i].data); while (p != NULL) { printf("->%d(%c) ", p->adjvex, g.adjlist[p->adjvex].data); p = p->nextarc; } printf("n"); } printf("n"); UFSets S[MaxVertexNum]; int count; Initial(g, S); CountConnect(g, S, count); printf("该图的连通分量数为：%d", count); printf("n输出并查集中数组的信息："); Print(S, g.vexnum); return 0; }
说明： 利用并查集来判断图中的连通分量数时，有向图和无向图都适用，但是要判断图中是否存在环路时，此时只适合无向图的适用。
如果此时要判断一个图是否存在回路，可以使用DFS(深度优先遍历算法)或拓扑排序。
使用DFS判断图是否有环从顶点v出发，对每个访问的顶点w做标记(visited[w]=1)。若顶点w(先访问)和i(后访问)均已访问过，表示从顶点w到顶点i存在一条路径。当从顶点i出发遍历，发现顶点i到顶点w有一条边时，表示存在一个回路(该回路上包含顶点w和i)。算法Cycle(G,v,has)从顶点v出发判断图G中是否存在回路，has是布尔值，初始调用时置为false，执行后若为true表示有回路，否则表示图G中没有回路。
邻接表法bool visited[MaxVertexNum]; //全局变量，访问标记数组
void Cycle(AdjGraph g, int v, bool& has)
{ //调用时has置初值false
ArcNode* p;
int w;
visited[v] = 1; //置已访问标记
p = g.adjlist[v].firstarc; //p指向顶点v的第一个邻接点
while (p != NULL)
{
w = p->adjvex;
if (visited[w] == 0) //若顶点w未访问,递归访问它
Cycle(g, w, has);
else has = true; //又找到了已访问过的顶点说明有回路
p = p->nextarc; //找下一个邻接点
}
}
运行结果
