离散数学实验4 平面图判定及对偶图的求解 c++

• 离散数学实验报告3
• • 一、实验题目
  • 二、实验目的
  • 三、实验要求
  • • 需求分析：
    • • 输入形式与输入范围
    • 概要设计：
    • • 使用的数据结构与算法：
      • 程序流程：
    • 详细代码

实验题目：平面图判定及对偶图的求解

实验时间: 2021.12.23

1、掌握最⼤匹配,交错路径的定义；

2、掌握最⼤匹配的求解⽅法。

1. 输⼊：⽆向简单连通图的关联矩阵

   （例如：）。

   输出：此图的最⼤匹配数，和⼀个最⼤匹配

   例如:M={e1,e3}

   *说明：

   要求学⽣设计的程序不仅对给定相邻矩阵得出正确结果，还要对教师测试数据集得出正确结果。

根据关联矩阵求出相邻矩阵，在根据匹配的定义找到⼀个最⼤匹配。

预设输入边范围 : 0 < m < 999 0

深度优先搜索、相邻矩阵

1、read()函数读⼊⼀个关联矩阵，这⾥⽤到了sstream，不需要⼿动输⼊矩阵的⾏数和列数。根据这个关联矩阵可

以得出相邻矩阵。

2、因为要求最⼤匹配，所以我们从⼤到⼩枚举，soso()函数是基于深度优先搜索来进⾏枚举每⼀种情况，然后在

ck()函数中判断这种情况是否是⼀个匹配。因为是从⼤到⼩枚举的，所以说第⼀次得到那个匹配⼀定是最⼤匹配，

它的边集的数⽬就是匹配数。

#include 
#include 
#include 
#include 
#include
#include 
using namespace std;
int sq[1000][1000]; //关联矩阵
int sq2[1000][1000];//邻接矩阵
int edge[1000][1000],edx=0;
vector> edges;
vector choose;
int r,c;
int ans=0;
int pnubs[1000];
bool vis[1000];
void read(){
 cout<<"请输⼊关联矩阵:n";
 string str;
 getline(cin,str);
 while(str!=""){
 stringstream ss(str);
 r++;
 for(int j=1;!ss.eof();j++){
 ss>>sq[r][j];
 c=max(c,j);
 }
 getline(cin,str);
 }
 int a=-1,b=-1;
 for(int i=1;i<=c;i++){
 for(int j=1;j<=r;j++){
 if(sq[j][i]==1){
 if(a==-1){
 a=j;
 }else{
 b=j;
 }
 }
 }
 if(b==-1) b=a;
 edge[b][a]=edge[a][b]=++edx;
 edges.push_back(make_pair(a,b));
 sq2[a][b]=1;
 sq2[b][a]=1;
 a=-1;
 b=-1;
 }
}
bool ck(){
 memset(pnubs,0,sizeof pnubs);
 for(int i : choose){
 auto temp=edges[i-1];
 pnubs[temp.first]++;
   pnubs[temp.second]++;
 }
 for(int i=1;i<=r;i++){
 if(pnubs[i]>=2) return false;
 }
 return true; }
bool soso(int x){
 if(x==0){
 if(ck()){
 cout<<"匹配数="<
 cout<<"e"<
 if(!vis[i]){
 choose.push_back(i);
 vis[i]= true;
 bool rt=soso(x-1);
 vis[i]= false;
 choose.pop_back();
 if(rt) return rt;
 }
 }
}
int main()
{
 read();
 for(int i=edx;i>=1;i--){
 ans=i;
 if(soso(i)) break;
 }
}