判定是否二分图
测试用例：
(此算例是二分图，所以应该返回 true.)
4 4
0 1
0 3
1 2
2 3
判定函数：
// C
bool __isBipartite( adjMatrix *G, int *colors, int i )
{
for (int j = 0; j < G->n; j++) { // 遍历顶点 i 所有相邻的点
if ( G->matrix[i][j] != 0 && colors[G->matrix[i][j]] == 0 ) { // 如果当前邻点没有访问过
colors[G->matrix[i][j]] = (colors[i]== 'r' ? 'b' : 'r');
// 若当前邻点的颜色是 'r'(红色)，改为 'b'(蓝色)，否则 'r'(红色) --> 保证顶点 v 和顶点 v 所有相邻点的颜色不同
if ( !__isBipartite(G, colors, G->matrix[i][j]) )
// 如果 __isBipartite 值为false，就不是二分图
return false;
} else if ( G->matrix[i][j] != 0 && colors[G->matrix[i][j]] == colors[i] )
return false;
// 颜色相同，出现矛盾
}
return true;
}
bool isBipartite( adjMatrix *G )
{
int *colors = malloc(sizeof(int) * MAX_vertex);
memset(colors, 0, sizeof(int) * MAX_vertex);
for (int i = 0; i < G->n; i++) {
if (colors[i] == 0) { // colors 当做标记数组 visited，等于0 表示还没访问
colors[i] = 'r'; // 标记为已访问，并标记为 'r'(红色)
if ( !__isBipartite(G, colors, i) ) {
// 如果 __isBipartite 值为false，就不是二分图
free(colors); colors = NULL; // 防止野指针
return false;
}
}
}
free(colors); colors = NULL; // 防止野指针
return true;
}
测试部分：
// 测试函数 main，还有创建图的函数
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef enum
{ // 枚举图类型
DG = 1, // 有向无权图
DN = 2, // 无向无权图
UDG = 3, // 有向有权图
UDN = 4 // 无向无权图
} graph_kind;
/* 邻接矩阵 */
typedef int T;
typedef struct graph_adj_matrix
{
T *list; // 顶点表，存储顶点本身的数据，如顶点1的信息是[北京]
int **matrix; // 二维数组
int n; // 顶点数
int m; // 弧数
graph_kind kind; // 图的类型
} adjMatrix;
#define MAX_vertex 256 // 最大顶点数
#define MAX_edge MAX_vertex * MAX_vertex
// 最大弧数，邻接矩阵的空间是
// n*n
/* 获取顶点的位置 */
int vertices_pos(adjMatrix * G, T v)
{
for (int i = 0; i < G->n; i++)
if (G->list[i] == v)
return i;
return -1; // 找不到，v不存在
}
void create_graph(adjMatrix * G)
{
/* 存储顶点信息 */
G->list = (T *) malloc(sizeof(T) * MAX_vertex);
assert(G->list != NULL);
G->matrix = (int **)malloc(sizeof(int) * MAX_vertex);
// 先开辟行
for (int i = 0; i < MAX_vertex; i++) // 再开辟列
G->matrix[i] = (int *)malloc(sizeof(int) * MAX_edge);
/* 初始化矩阵 */
for (int i = 0; i < MAX_vertex; i++)
for (int j = 0; j < MAX_edge; j++)
G->matrix[i][j] = 0;
/* 顶点、弧的数据，从文件里读出来 */
puts("请输入测试文件:> ");
char file_name[128] = "";
scanf("%127[^\n]", file_name);
FILE *fp = fopen(file_name, "r");
assert(fp);
fscanf(fp, "%d%*c%d", &(G->n), &(G->m));
scanf("%*[^\n]"), scanf("%*c"); // 清空缓冲区
G->list[0] = '0';
G->list[1] = '1';
G->list[2] = '2';
G->list[3] = '3';
G->kind = 2;
T v1, v2;
int w;
switch (G->kind)
{
case DG:
for (int i = 0; i < G->m; i++)
{
while (fgetc(fp) != '\n'); // 文件指针移动到下一行
fscanf(fp, "%c %c", &v1, &v2);
int n = vertices_pos(G, v1);
int m = vertices_pos(G, v2);
assert(m != -1); // 顶点 v1 不存在
assert(n != -1);
G->matrix[n][m] = 1;
}
break;
case DN:
for (int i = 0; i < G->m; i++)
{
while (fgetc(fp) != '\n'); // 文件指针移动到下一行
fscanf(fp, "%c %c", &v1, &v2);
int n = vertices_pos(G, v1);
int m = vertices_pos(G, v2);
assert(m != -1);
assert(n != -1);
G->matrix[n][m] = 1;
G->matrix[m][n] = 1; // 无向图的二阶矩阵沿主对角线对称
}
break;
case UDG:
for (int i = 0; i < G->m; i++)
{
while (fgetc(fp) != '\n'); // 文件指针移动到下一行
fscanf(fp, "%c %c %d", &v1, &v2, &w);
int n = vertices_pos(G, v1);
int m = vertices_pos(G, v2);
assert(m != -1);
assert(n != -1);
G->matrix[n][m] = w;
}
break;
case UDN:
for (int i = 0; i < G->m; i++)
{
while (fgetc(fp) != '\n'); // 文件指针移动到下一行
fscanf(fp, "%c %c %d", &v1, &v2, &w);
int n = vertices_pos(G, v1);
int m = vertices_pos(G, v2);
assert(m != -1);
assert(n != -1);
G->matrix[n][m] = w;
G->matrix[m][n] = w;
}
break;
default:
break;
}
}
int main()
{
adjMatrix G;
// 建模图：邻接矩阵
create_graph(&G);
// 构造图：图建模[邻接矩阵]、初始化矩阵、构造某种类型图、读入测试数据
isBipartite(&G)?puts("\n判定：此图是二分图\n") : puts("\n判定：此图不是二分图");
// 测试二分图的函数
return 0;
}
P.S. 太麻烦老师啦，下不为例。
622
收起
正在回答
2回答
如果我没有理解错，matrix 是一个邻接矩阵，而不是邻接表；
bool __isBipartite( adjMatrix *G, int *colors, int i ){
for (int j = 0; j < G->n; j++) { // 遍历顶点 i 所有相邻的点
if ( G->matrix[i][j] != 0 && colors[G->matrix[i][j]] == 0 ) { // 如果当前邻点没有访问过
colors[G->matrix[i][j]] = (colors[i]== 'r' ? 'b' : 'r');
// 若当前邻点的颜色是 'r'(红色)，改为 'b'(蓝色)，否则 'r'(红色) --> 保证顶点 v 和顶点 v 所有相邻点的颜色不同
if ( !__isBipartite(G, colors, G->matrix[i][j]) )
// 如果 __isBipartite 值为false，就不是二分图
return false;
} else if ( G->matrix[i][j] != 0 && colors[G->matrix[i][j]] == colors[i] )
return false;
// 颜色相同，出现矛盾
}
return true;
}这个函数里，该表达顶点 j 的地方，你都写成了 G->matrix[i][j]。
2
有任何疑惑可以回复我~
慕用0058068
2020-12-31 20:25:59
相似问题
关于通过colors数组信息划分二分图的Bug
568
5
3
分享一个自己写的二分图检测算法
628
0
3
关于bst<二分搜索树的问题>
694
0
3
对于updateChildren里最后一个情况判断不理解
716
0
3
为什么需要特殊判断
736
0
10
登录后可查看更多问答，登录/注册
