當前位置:網站首頁>圖的著色問題

圖的著色問題

2022-01-27 15:44:07 是牛大春呀

問題1:
圖著色問題是一個著名的NP完全問題。給定無向圖G=(V,E),問可否用K種顏色為V中的每一個頂點分配一種顏色,使得不會有兩個相鄰頂點具有同一種顏色?
但本題並不是要你解决這個著色問題,而是對給定的一種顏色分配,請你判斷這是否是圖著色問題的一個解。
輸入格式:
輸入在第一行給出3個整數V(0<V≤500)、E(≥0)和K(0<K≤V),分別是無向圖的頂點數、邊數、以及顏色數。頂點和顏色都從1到V編號。隨後E行,每行給出一條邊的兩個端點的編號。在圖的信息給出之後,給出了一個正整數N(≤20),是待檢查的顏色分配方案的個數。隨後N行,每行順次給出V個頂點的顏色(第i個數字錶示第i個頂點的顏色),數字間以空格分隔。題目保證給定的無向圖是合法的(即不存在自回路和重邊)。
輸出格式:
對每種顏色分配方案,如果是圖著色問題的一個解則輸出Yes,否則輸出No,每句占一行。

問題2:
給定無向連通圖和m種不同的顏色。用這些顏色為圖G的各頂點著色,每個頂點著一種顏色。是否有一種著色法使G中每條邊的兩個頂點有不同的顏色。這個問題是圖的m可著色判定問題。若一個圖最少需要m種顏色才能使圖中每條邊相連接的兩個頂點著不同顏色,稱這個數m為這個圖的色數。求一個圖的色數m稱為圖的m可著色優化問題。 給定一個圖以及m種顏色,請計算出塗色方案數

問題3:
基於問題2,對問題2進行拓展,輸出最少需要的顏色數量;
問題4:
利用回溯法,對給定無向圖進行染色;

問題1 的實現代碼:

#include<iostream>
#include<cstring>
#include <set>
#include <map>
#include <ctime>
#include <bitset>
#include <sstream>
#include <algorithm>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>//getch()的頭文件
#include<vector>
#include<queue>
#include<stack>
using namespace std;
//
const int N=510;//二維數組的最大行列數 
int v,e,k,col[N],vis[N],g[N][N];//v為頂點數,e為邊數,k為顏色數 
bool dfs(int u ){
    //從某個頂點開始,進行深搜 
	for(int i =1;i<=v;i++){
    //這裏每一個頂點都是有順序的,是遞增的 
		if(!vis[i]&&g[u][i]==1){
    //如果沒有訪問過,而且頂點間是有邊的 
			vis[i]=true;//因為是無向圖,因此有環,為避免一直遞歸,應該加一個訪問比特vis (true==1) 
			if(col[u]==col[i]) return false;//如果兩個點的顏色是相同的,直接返回false 
			else return dfs(i);
		} 
	}
	return true;//如果循環遍曆完所有的頂點都沒有相鄰顏色相同的則返回true 
}
int main()
{
    
	memset(g,0x3f,sizeof g);//對數組進行初始化 
	scanf("%d %d %d",&v,&e,&k);//輸入頂點數v,邊數e,顏色數k 
	for(int i =0;i<e;i++){
    
		int a,b;//a,b都當作是一個頂點了;此代碼中N=510,則就有510x510條無向邊的可能 
		scanf("%d %d",&a,&b);//輸入哪兩個頂點,兩個頂點的值都設置為1,不過在二比特數組中,其圖的實際的相對比特置並沒有體現出來,而是以邏輯關系體現出來的
		//比如無向邊 (1,2),和(1,3),其邏輯意義是,它們的交界點是1,也就是頂點1,因此呢,我們的頂點,是可以用一個一維數組來體現的。 
		 
		g[a][b]=g[b][a]=1;//無向邊,因此需要兩個方向都賦值為1; 
	}
	int n;//這個是輸入判斷情况的個數 
	scanf("%d",&n);
	for(int i =1;i<=n;i++){
    
		set<int> s;//set的數據唯一,而且自動排序 
		for(int j=1,c;j<=v;j++){
    //從頂點1開始,分別讀取各個頂點的顏色 
			scanf("%d",&c);//讀取顏色記錄在c中 
			col[j]=c;//將c賦值給col數組,值得注意的是,這個數組的每一個下標都是一個頂點 
			s.insert(c);
		}
		if(s.size()!=k){
    //題目1,規定用k種顏色來染色如果染色數不等於k,則直接輸出"No" 
			puts("No");
			continue;// 循環次數<=n的話則繼續執行 
		}
		memset(vis,0,sizeof vis);//將vis數組全部初始化為0,即,全部都沒有被訪問過; 
		int flag=true;
		for(int j=1;j<=v;j++){
    
			if(!vis[j]){
    //沒有訪問過才能進行深搜 
				if(!dfs(j)){
    
					flag=false;//如果返回的結果是false,則標記為flag 設置為false,並且退出循環 
					break;//退出循環,不用繼續往下從別的頂點進行判定了//因為我們不知道那個點和此時的點有邊,因此呢,每一個點都需要遍曆所有的點
					//看其他點是否與當前點有邊,比如:i==1,V==6,就需要遍曆(1,2),(1,3),(1,4),(1,5),(1,6) 
				}
			}
		}
		if(flag) puts("Yes");//根據flag的標志比特進行輸出判定結果; 
		else puts("No");
	}
	
return 0;
}

調試結果:在這裏插入圖片描述

問題2實現代碼:

#include<stdio.h>
#include<iostream>
#define V 4//圖中的頂點數
/* 打印解决方案的實用函數 */
void printSolutions(int color[])//打印解决方案的函數 
{
    
    printf("以下染色方案是可行方案中的一種 \n");
    for (int i = 0; i < V; i++)
        printf(" %d ", color[i]);
    printf("\n");
}

//變量的含義:當前染色頂點v,無向圖graph,color數組(用來記錄當前每個頂點的染色狀况),c 當前嘗試染色的顏色 
bool Can_be_dyed(int v, bool graph[V][V], int color[], int c)用於檢查當前顏色分配的實用程序函數
{
    		//c是當前要給頂點染的顏色 
    for (int i = 0; i < V; i++)//這裏的頂點是從0開始的,因此變量取值也要從0開始 
    if (graph[v][i] && c == color[i])//graph[v][i]的意思是v-->i有邊,在此前提下增加一個並列條件c==color[i]的意思是,無向圖的兩個頂點的顏色不能相同
	//舉例說明:在graphColoring函數裏面,v是從0開始不斷增長的,因此,解决題目所描述的問題的方法是:
	//①檢測兩個頂點間是否有邊,比如題目中graph[0][1]是有邊的
	//②接著需要判斷:基於起始點v,更與之相關聯的頂點的顏色是否與當前染色的顏色沖突,比如問題描述中的無向圖,基於起始點0,與它相關聯的邊是
	//(0,1),(0,2),(0,3),因此,這個for循環就是從某個頂點出發,然後找出與這個頂點相關聯的邊,然後判斷,當前染的顏色c是否與這些邊的顏色沖突
	//比如:color[0]的顏色是1,此時與之相關聯的頂點 1,2,3都可以通過c==color[i] 直接判定出來是否可以染色了
	//總結:這個染色是針對當前點v的,結合與其他頂點是否與當前染色點有邊,遍曆與之相關聯頂點的顏色,看是否與當前染色的顏色相同,如果相同就返回false
	//否則返回true 
        return false;
    return true;
}
 
void Search_for_solutions(bool graph[V][V], int m, int color[], int v)//求解m著色問題的遞推效用函數
{
    
 
    if (v == V)//基本情况:如果所有頂點都指定了顏色,則返回真,並且值得注意的是v是從0開始的
	//也就是從頂點0開始遍曆的,或者說是從頂點0開始顏色
    {
    
        printSolutions(color);//如果都染色了就輸出結果,完成子遞歸 
        return;
    }
    /* 考慮這個頂點v並嘗試不同的顏色,因為此時嘗試染色的過程並未結束*/
    for (int c = 1; c <= m; c++)//c就是顏色集合m中的一種顏色,即m={1,2,3} 
    {
    
        /* 檢查顏色C到V的分配是否正確*/
        if (Can_be_dyed(v, graph, color, c))
        {
    
            color[v] = c;
            /* 遞歸為其餘頂點指定顏色 */
            Search_for_solutions(graph, m, color, v + 1);//遞歸為其他頂點也分配其染色方案 
            color[v] = 0; //遞歸回退的時候,將染的顏色都重新初始化 
        } 
    }//接著循環, 因為第一個頂點0的可行染色顏色取1,2,3然後到了第二個點進行染色的時候,
	//因為是遞歸,它會返回第二個頂點(這裏頂點是從小到大的,因此第二個頂點是頂點1)的染色顏色是2,在頂點1的染色是1
	//且符合題目要求所有情况 
	// 就如結果:1,2,3,2 和1,3,2,3 
}

int main()
{
    
    /* 給定以下無向圖,看是否三種顏色可以實現圖的著色 (3)---(2) | / | | / | | / | (0)---(1) */
    //五條無向邊,因此涉及的坐標有十個 
    bool graph[V][V] = {
     
	{
     0, 1, 1, 1 },//(0,1),(0,2),(0,3) 
    {
     1, 0, 1, 0 },//(1,0),(1,2)
    {
     1, 1, 0, 1 },//(2,0),(2,1),(2,3) 
    {
     1, 0, 1, 0 },//(3,0),(3,2)
};
    int m = 3; //m為顏色數,從1開始,分別有顏色1,顏色2,顏色3 
    int color[V];
    for (int i = 0; i < V; i++)
        color[i] = 0;//顏色數組,從0頂點開始,分別記錄每個頂點的顏色 
    Search_for_solutions(graph, m, color, 0);
    system("pause");
    return 0;
}

調試數據: 給定的無向圖:在這裏插入圖片描述

可視化為:在這裏插入圖片描述

調試結果:在這裏插入圖片描述

從問題2的實現代碼可以知道,我們給圖進行填充顏色是進行貪心填充的:即每次每個點都從顏色1開始進行遍曆,並且判定自己能否取得當前顏色,然後因為顏色它是從前面取得的顏色開始遞增的,那麼,第一個點如果染了顏色1,如果第二個點與該點沒有邊,那麼第二個點也能够染顏色1,所以,我們可以得出結論:以這種方式所使用的顏色數,輸出的符合結果,所使用的顏色數,必然是最少的,因此,基於問題2,實現問題3的代碼如下:

問題3實現代碼:

#include<stdio.h>
#include<iostream>

#include <algorithm>
#include<string.h>
#include<cstring>
#define V 4//圖中的頂點數
/* 輸出最小染色顏色數 */
using namespace std;
void print_Minimum_number_of_colors(int color[])//打印解决方案的函數 
{
    
    printf("所需要的最小染色數為: \n");
    int unique_color[V]; bool flag=false; int m =0; 
 // memset(unique_color,-1,sizeof unique_color);//初始化數組,染其全部為-1 
    for(int i =0;i<V;i++){
    
    	int j=0;
    	for(;j<m;j++){
    
    		if(unique_color[j]==color[i])//循環遍曆unique_color數組,看數組中是否有和原color中顏色相同的
				break;
		}
		if(j==m){
    
		// unique_color[m]=color[i];
			m++;
		}
	}
	cout<<m<<endl;
}
//可否染色的函數是不用改變的


//變量的含義:當前染色頂點v,無向圖graph,color數組(用來記錄當前每個頂點的染色狀况),c 當前嘗試染色的顏色 
bool Can_be_dyed(int v, bool graph[V][V], int color[], int c)用於檢查當前顏色分配的實用程序函數
{
    		//c是當前要給頂點染的顏色 
    for (int i = 0; i < V; i++)//這裏的頂點是從0開始的,因此變量取值也要從0開始 
    if (graph[v][i] && c == color[i])//graph[v][i]的意思是v-->i有邊,在此前提下增加一個並列條件c==color[i]的意思是,無向圖的兩個頂點的顏色不能相同
	//舉例說明:在graphColoring函數裏面,v是從0開始不斷增長的,因此,解决題目所描述的問題的方法是:
	//①檢測兩個頂點間是否有邊,比如題目中graph[0][1]是有邊的
	//②接著需要判斷:基於起始點v,更與之相關聯的頂點的顏色是否與當前染色的顏色沖突,比如問題描述中的無向圖,基於起始點0,與它相關聯的邊是
	//(0,1),(0,2),(0,3),因此,這個for循環就是從某個頂點出發,然後找出與這個頂點相關聯的邊,然後判斷,當前染的顏色c是否與這些邊的顏色沖突
	//比如:color[0]的顏色是1,此時與之相關聯的頂點 1,2,3都可以通過c==color[i] 直接判定出來是否可以染色了
	//總結:這個染色是針對當前點v的,結合與其他頂點是否與當前染色點有邊,遍曆與之相關聯頂點的顏色,看是否與當前染色的顏色相同,如果相同就返回false
	//否則返回true 
        return false;
    return true;
}
 bool flag=false;
void Search_for_solutions(bool graph[V][V], int m, int color[], int v)//求解m著色問題的遞推效用函數
{
    
 	
    if (v == V)//基本情况:如果所有頂點都指定了顏色,則返回真,並且值得注意的是v是從0開始的
	//也就是從頂點0開始遍曆的,或者說是從頂點0開始顏色
    {
    
        print_Minimum_number_of_colors(color);//如果都染色了就輸出結果,完成子遞歸 
        return;
    }
    /* 考慮這個頂點v並嘗試不同的顏色,因為此時嘗試染色的過程並未結束*/
    
	for (int c = 1; c <= m; c++)//c就是顏色集合m中的一種顏色,即m={1,2,3} 
    {
    	if(flag){
    
    	break;
	}
        /* 檢查顏色C到V的分配是否正確*/
        if (Can_be_dyed(v, graph, color, c))//值得注意的是,如果是遞歸的話,那麼,這個v=0會被公平的分配到外面的循環,也就是,外面的循環
		//c=1的時候對應一個v=0,c=2的時候也會對應一個v=0,同理,c=3的時候也會有v=0對應 
        {
    
            color[v] = c;
            /* 遞歸為其餘頂點指定顏色 */
            Search_for_solutions(graph, m, color, v + 1);//遞歸為其他頂點也分配其染色方案 
            color[v] = 0; //遞歸回退的時候,將染的顏色都重新初始化 
        } 
    }
	//接著循環, 因為第一個頂點0的可行染色顏色取1,2,3然後到了第二個點進行染色的時候,
	//因為是遞歸,它會返回第二個頂點(這裏頂點是從小到大的,因此第二個頂點是頂點1)的染色顏色是2,在頂點1的染色是1
	//且符合題目要求所有情况 
	// 就如結果:1,2,3,2 和1,3,2,3 
	flag=true;
}

int main()
{
    
    /* 給定以下無向圖,看是否三種顏色可以實現圖的著色 (3)---(2) | / | | / | | / | (0)---(1) */
    //五條無向邊,因此涉及的坐標有十個 
    bool graph[V][V] = {
     
	{
     0, 1, 1, 1 },//(0,1),(0,2),(0,3) 
    {
     1, 0, 1, 0 },//(1,0),(1,2)
    {
     1, 1, 0, 1 },//(2,0),(2,1),(2,3) 
    {
     1, 0, 1, 0 },//(3,0),(3,2)
};
    int m = 3; //m為顏色數,從1開始,分別有顏色1,顏色2,顏色3 
    int color[V];
// for (int i = 0; i < V; i++)
// color[i] = 0;//顏色數組,從0頂點開始,分別記錄每個頂點的顏色 
//不適用以上for循環,而是使用memset方法對color數組進行初始化; 
    memset(color,0,sizeof color); 
    Search_for_solutions(graph, m, color, 0);
    system("pause");
    return 0;
}

調試結果:在這裏插入圖片描述

問題4實現代碼:

#include<stdio.h>
  
int color[100];
bool ok(int k,int c[][100])//判斷頂點k的著色是否發生沖突
{
    
  int i,j;
  for(i=1;i<k;i++)
  {
    
    if(c[k][i]==1&&color[i]==color[k])
      return false;
  }
  return true;
}
  
void graphcolor(int n,int m,int c[][100])
{
    
  int i,k;
  for(i=1;i<=n;i++)
  color[i]=0;
  k=1;
  while(k>=1)
  {
    
    color[k]=color[k]+1;//顏色加一,為什麼呢?因為回溯的時候需要將顏色進行改變,從上一種的可能那裏繼續往下找! 
    while(color[k]<=m)//符合顏色取值範圍 
      if(ok(k,c))//如果說,我將回溯點的顏色進行改變的話,還可以符合的話,那麼,就跳出這個if else 循環,去下面的循環裏繼續判斷(這個循環主要是為了找顏色的) 
        break;
      else 
        color[k]=color[k]+1;//搜索下一個顏色
      if(color[k]<=m&&k==n)//如果所有點已經染上了顏色,就將所有點的顏色輸出 
      {
    
        for(i=1;i<=n;i++) 
          printf("%d",color[i]);
        printf("\n");
      }
      else if(color[k]<=m&&k<n)//如果還沒有染完色,在前面的染色基礎上繼續進行染色,因此對下一個點進行常識性的染色 
        k=k+1;//處理下一個頂點
      else
      {
    
        color[k]=0;//回溯的意思是:在原來的基礎上,繼續進行染色;
		//觸發回溯的條件有以下兩種:
		//①染色的情况已經不能够滿足了題目要求了,此時需要將當前點的顏色進行重置,也就是置0,然後進行回溯;(就是這個點已經
		//在前面幾個點選好顏色的時候,嘗試了m種顏色的可能,都符合題目要求(相鄰頂點有邊然後顏色取值相等了)),那麼這種情况下,我們就需要改變原先的點的顏色! 
		//然後將點進行回退到上一個狀態 
		//②所有的點進行輸出後k==4,並且此時的顏色已經越界了,超出顏色的取值範圍,因此需要回溯 
        k=k-1;//回溯
      }
  }
}
int  main()
{
    
    int i,j,n,m;
    int c[100][100];//存儲n個頂點的無向圖的數組
    printf("輸入頂點數n和著色數m:\n");
    scanf("%d%d",&n,&m);
    printf("輸入無向圖的鄰接矩陣:\n");
    for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
        scanf("%d",&c[i][j]);
    printf("著色所有可能的解:\n");
    graphcolor(n,m,c);
    return 0;
}

調試數據:
在這裏插入圖片描述

調試結果:
在這裏插入圖片描述

時間複雜度和空間複雜度(僅供參考)

問題1的算法時間複雜度:

問題1,對於給定變量,n(輸入的方案數),v(頂點數),因為循環裏還涉及到遞歸,因此對於給定代碼:
在這裏插入圖片描述
在這裏插入圖片描述

dfs遞歸函數:
在這裏插入圖片描述
因涉及到for循環,和for循環裏一些變量的賦值、變量的遞增,還有使用memset函數進行對vis數組的初始化等,而在遞歸函數中
遞歸算法的時間複雜度: 遞歸的次數 * 每次遞歸中的操作次數
因此,可計算出其算法複雜度為:
O((1+3n)* (1+5v) +(1+3n)*n+(1+3n)*v^2)
省略常數,即O(nv+n^2+nv ^2)
空間複雜度只涉及到分配的空間:
在這裏插入圖片描述
由於在算法中,並沒有使用new開辟新的空間,因此,其空間複雜度是固定不變的為O(1+1+1+N+N+N^2)
當N–>∞其空間複雜度為 O(N^2)

問題2的算法時間複雜度:

問題2,對於給定代碼
在這裏插入圖片描述

在這裏插入圖片描述

在這裏插入圖片描述

其算法涉及到了for循環和遞歸調用函數Search_for_solutions(),和判定函數Can_be_dyed()
因此其算法的時間複雜度是:
O( ((1+3v)+(m*(v*(1+(v-1) +1)))) +C)//這個變量C是最後打印符合的時候所需要的時間,若打印C次,則時間複雜度為C
省去常數,因此其算法的時間複雜度是:O(mv^2)
鑒於顏色變量m的取值是有限個數的,因此,如果m取值較小,不影響其算法的時間複雜度的話,那麼m可以省略,則算法複雜度可以取O(V^2)
問題2算法涉及的空間複雜度:
因為在for循環或者遞歸函數裏均沒有開辟新的空間給新的變量,因此,算法涉及的空間複雜度由前面定義的變量决定:
在這裏插入圖片描述
即其空間複雜度為:O(V ^2+1+V)=O (V^2)

問題3算法的時間複雜度:

由問題3涉及的代碼可知:
在這裏插入圖片描述

在這裏插入圖片描述在這裏插入圖片描述

因此可以根據循環和遞歸算出算法時間複雜度:
O=((V+1)V/2 +1V(V-1) )
//因為問題3我讓遞歸提前終止了,即輸出其中的一種方案就結束了遞歸,所以這裏的m取1,即1*V(V-1);
省去參數可得:O=V ^2+1 * V ^2= V^2
問題3的空間複雜度:
基於問題2的前提下進行拓展的,因此其空間複雜度都是
O(V^2+ (1+ V))=O(V^2)
問題4的算法事件複雜度:
根據問題4的代碼:在這裏插入圖片描述
在這裏插入圖片描述
在這裏插入圖片描述
因為涉及到回溯,時間複雜度的計算有點麻煩,不是簡單的暴力深搜可以得到想要的結果的,因此時間複雜度參考百度
其時間複雜度為:O(3^n)
問題4的空間複雜度:
O(n^2),其中n為頂點數

版權聲明
本文為[是牛大春呀]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/01/202201271544067580.html

隨機推薦