//?eulargraph.cpp?:?Defines?the?entry?point?for?the?console?application.
//

#include?“stdafx.h“
#include?“stdio.h“
#include?“stdlib.h“
#include?“time.h“
#include?“malloc.h“
//#include?“stdbool.h“
#define?n?204
int?count;
//int?m=0;
//int?circuit[m];
int?g[n+1][n+1];//用來存儲(chǔ)節(jié)點(diǎn)之間關(guān)系的矩陣
int?edgecount[n+1];//存儲(chǔ)每個(gè)節(jié)點(diǎn)的度數(shù)
int?random（）?//用來隨機(jī)節(jié)點(diǎn)之間關(guān)系?0表示不相連，1表示相連
{
	int?k;
????
//????printf（“Ten?random?numbers?from?0?to?99nn\n“）;
????k=rand（）%2;
????return?k;
}
int?randomNode（）//用來隨機(jī)節(jié)點(diǎn)
{
	int?k;
????
//????printf（“Ten?random?numbers?from?0?to?99nn\n“）;
????k=rand（）%n+1;
????return?k;
}
void?adjacencyCount（）//計(jì)算每一個(gè)節(jié)點(diǎn)鄰接邊的個(gè)數(shù)
{
	int?ij;
	for（i=1;i<=n;i++）
		for（j=1;j<=n;j++）
			edgecount[i]+=g[i][j];
}
void?initGraph（）//隨機(jī)生成一個(gè)連通圖，然后再生成歐拉圖
{
	int?ij;
	int?s;
	for（i=1;i<=n;i++）//先構(gòu)造一個(gè)圖
	{
		g[i][i]=0;
		for（j=i+1;j<=n;j++）
		{
			s=random（）;
			g[i][j]=g[j][i]=s;
		}
	}
	adjacencyCount（）;
	for（i=1;i<=n;i++）//把圖變成連通圖
	{
		if（edgecount[i]==0）
			{
				s=i;
				while（s==i）
				?s=randomNode（）;//隨機(jī)圖中的節(jié)點(diǎn)????并相連
				g[i][s]?=?g[s][i]?=?1;
				edgecount[i]++;
				edgecount[s]++;
			}
//		adjacencyCount（）;
	}
	for（i=1;i<=n;i++）
		for（j=i;j<=n;j++）
			printf（“%d---->%d?:?%d\n“ijg[i][j]）;
}
/*
以下為構(gòu)造的歐拉圖
如果該點(diǎn)v1的度數(shù)為奇數(shù)，則在后面再找一個(gè)度數(shù)為奇數(shù)的點(diǎn)v2
（一）如果v1和v2相連，而且如果他們的度數(shù)都大于1，則去掉他們的連邊，否則繼續(xù)尋找度數(shù)為奇數(shù)的節(jié)點(diǎn)
?????如果v1和v2沒有相連，則相連v1和v2
（二）如果?（一）?失敗了，既沒有找到合適的點(diǎn)
??????1、則再找一度數(shù)為奇的點(diǎn)v3，和一個(gè)度數(shù)為偶的點(diǎn)v4，如果v4
????????和v1，v3沒有相連，則在v4和v1，v4和v3之間加邊。
??????2、（1）如果仍沒有找到，則將該點(diǎn)與任意不相連的節(jié)點(diǎn)之間加邊，重新執(zhí)行變偶操作
	?????（2）如果找不到與該點(diǎn)不相連的節(jié)點(diǎn)，在任意找度數(shù)大于2的節(jié)點(diǎn)，去掉他們的連邊
*/
void?eularGraph（）//
{
	
	int?ijklm;
	int?v;//浪費(fèi)了一部分空間
	int?retry?=?0;
	for（i=1;i<=n;i++）
	{
		printf（“%d%d\n“iedgecount[i]）;
		if（edgecount[i]%2!=0）//判斷該點(diǎn)的度數(shù)是否為偶數(shù)
		{
			j=1;
			for（j=i+1;j<=n;j++）//在相鄰的節(jié)點(diǎn)中尋找度數(shù)為奇數(shù)的節(jié)點(diǎn)
			{
				if（edgecount[j]%2!=0）//從相鄰的節(jié)點(diǎn)中找出度數(shù)為奇數(shù)的節(jié)點(diǎn)??（一）
				{
					if（g[i][j]）?//節(jié)點(diǎn)之間是否存在邊，不存在則連接這兩個(gè)節(jié)點(diǎn)
					{
						if（edgecount[i]!=1&&edgecount[j]!=1）//判斷i和j的節(jié)點(diǎn)的度數(shù)是否大于1，大于1則去掉鄰邊
						{
							g[i][j]=g[j][i]=0;
							edgecount[i]--;
							edgecount[j]--;
							break;
						}
						else
						{
							continue;
						}
					}
					else?//不相連則連上
					{
						g[i][j]?=?g[j][i]?=1;
						edgecount[i]++;
						edgecount[j]++;
						break;
					}
				}
			}
			if（j>n）???//沒有找到合適的鄰接點(diǎn)?（二）
			{
		//		m?=?0;
				for（k=i+1;k<=n;k++）???????//（二）?1、則再找一度數(shù)為奇的點(diǎn)v3，1、和一個(gè)度數(shù)為偶的點(diǎn)v4，如果v4
??????????????????????????????????????????//?和v1，v3沒有相連，則在v4和v1，v4和v3之間加邊。
				{
					if（edgecount[k]%2!=0）
						{
							v=k;
					//		m++;
							break;
						}
				}

			
		//	l=0;
		//	while（l		//	{
				for（k=1;k<=i;k++）//這個(gè)地方?（二）?1、
				{
					if（edgecount[k]%2==0）
						{
							if（!g[i][k]&&!g[k][v]）
								{
									g[i][k]?=?g[k][i]?=?1;
									g[k][v]?=?g[v][k]=1;
									edgecount[i]++;
									edgecount[k]+=2;
									edgecount[v]++;
								//	l=m;
									break;
								}
						}
				}
		//		l++;
		//	}
			

?屬性????????????大小?????日期????時(shí)間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2010-10-15?14:14??歐拉圖問題\
?????文件????????6052??2010-10-12?17:21??歐拉圖問題\eular.cpp
?????文件????????3603??2010-10-12?15:06??歐拉圖問題\eular.cpp.bak
?????目錄???????????0??2010-10-14?16:47??歐拉圖問題\eulargraph\
?????目錄???????????0??2010-10-13?16:06??歐拉圖問題\eulargraph\Debug\
?????文件??????188516??2010-10-13?15:56??歐拉圖問題\eulargraph\Debug\eulargraph.exe
?????文件??????212000??2010-10-13?15:56??歐拉圖問題\eulargraph\Debug\eulargraph.ilk
?????文件???????14093??2010-10-13?15:56??歐拉圖問題\eulargraph\Debug\eulargraph.obj
?????文件??????203788??2010-10-09?15:23??歐拉圖問題\eulargraph\Debug\eulargraph.pch
?????文件??????476160??2010-10-13?15:56??歐拉圖問題\eulargraph\Debug\eulargraph.pdb
?????文件????????2311??2010-10-09?15:23??歐拉圖問題\eulargraph\Debug\StdAfx.obj
?????文件???????41984??2010-10-13?15:56??歐拉圖問題\eulargraph\Debug\vc60.idb
?????文件???????53248??2010-10-13?15:56??歐拉圖問題\eulargraph\Debug\vc60.pdb
?????文件????????6939??2010-10-13?15:56??歐拉圖問題\eulargraph\eulargraph.cpp
?????文件????????4584??2010-10-09?14:27??歐拉圖問題\eulargraph\eulargraph.dsp
?????文件?????????528??2010-10-09?14:27??歐拉圖問題\eulargraph\eulargraph.dsw
?????文件???????50176??2010-10-14?16:47??歐拉圖問題\eulargraph\eulargraph.ncb
?????文件???????48640??2010-10-14?16:47??歐拉圖問題\eulargraph\eulargraph.opt
?????文件????????1778??2010-10-13?15:56??歐拉圖問題\eulargraph\eulargraph.plg
?????文件????????1232??2010-10-09?14:27??歐拉圖問題\eulargraph\ReadMe.txt
?????文件?????????297??2010-10-09?14:27??歐拉圖問題\eulargraph\StdAfx.cpp
?????文件?????????769??2010-10-09?14:27??歐拉圖問題\eulargraph\StdAfx.h
?????文件???????23552??2010-10-09?10:48??歐拉圖問題\歐拉回路.doc
?????文件???????27136??2010-10-09?11:02??歐拉圖問題\歐拉回路C++.doc
?????文件???????61952??2010-10-09?11:00??歐拉圖問題\隨機(jī)建立歐拉圖.doc