#include <stdio.h>
#include <stdlib.h>
/*定义图的最大顶点数，它要大于等于具体图的顶点数n*/
#define MaxVertexNum 15
/*定义图的最大边数，它要大于等于具体图的边数e*/
#define MaxEdgeNum 20
/*定义 MaxValue 为一个全局整型常量，其值要大于邻接矩阵中所有有效值之和*/
#define MaxValue 1000
/*定义图中顶点数据的类型 VertexType 为整型*/
typedef int VertexType;
/*定义 GV 为存储顶点信息的数组*/
VertexType GV[MaxVertexNum];
/*定义 GA 为存储邻接矩阵的数组*/
int GA[MaxVertexNum][MaxVertexNum];
/*定义保存图顶点访问标记的数组，每个元素的初值均为0 */
int visited[MaxVertexNum] = {0};
// 全局变量 sum 用来保存四边形数量
int sum = 0;
//i 是最开始出发的顶点，n 为图的顶点数
void findQuadrilateral(int i, int n)
{
int j, k, m;
// 标记第 i 个顶点已经访问
visited[i] = 1;
for(j=0; j<n; j++)
{
/* 当i与j相邻时，并且j未被访问,找出另外一个与i相邻的顶点 */
if(GA[i][j] == 1 && visited[j] == 0)
for(k=j+1; k<n; k++)
{
/* 当i与k相邻时，并且k未被访问,找出 j , k 的公共相邻的顶点 */
if(GA[i][k] == 1 && visited[k] == 0)
for(m=0; m<n; m++)
{
// m 与 j，k 相邻且未被访问过，则构成一个新的四边形 i j k m
if(GA[j][m] == 1 && GA[k][m] == 1 && visited[m] == 0)
{
sum += 1;
printf("存在四边形： %d %d %d %d \n", i, j, k, m);
}
}
}
}
}
void main()
{
int n, e;
int i, j, k;
int min = 1000;
/*输入一个图的顶点数和边数*/
printf("输入待处理图的顶点数和边数：");
scanf(" %d %d", &n, &e);
/*根据键盘输入建立图的邻接矩阵*/
/* 建立顶点数组 */
printf("输出 %d 个顶点数据\n", n);
for(i=0; i<n; i++)
{
GV[i] = i;
printf("%d ", i);
}
/* 初始化邻接矩阵数组 */
for(i=0; i<n; i++)
{
for(j=0; j<n; j++)
{
if(i == j)
GA[i][j] = 0;
// MaxValue 表示 i 与 j 不是直接相连的
else
GA[i][j] = MaxValue;
}
}
/* 建立邻接矩阵数组 */
printf("\n输入 %d 条无向边\n", e);
for(k=1; k<=e; k++) {
/*输入一条边的两端点序号i和j*/
scanf(" %d %d", &i, &j);
/*置数组中相应对称元素的值为 1, 这时候表示 i 与 j 相连*/
GA[i][j] = GA[j][i] = 1;
}
/* 打印邻接矩阵 */
for(i=0; i<n; i++)
{
for(j=0; j<n; j++)
printf("%4d ", GA[i][j]);
printf("\n");
}
for(i=0; i<n; i++)
{
findQuadrilateral(i, n);
}
printf("\总共有 %d 个四边形\n", sum);
}
