//?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];//用來存儲節點之間關系的矩陣
int?edgecount[n+1];//存儲每個節點的度數
int?random（）?//用來隨機節點之間關系?0表示不相連，1表示相連
{
	int?k;
????
//????printf（“Ten?random?numbers?from?0?to?99nn\n“）;
????k=rand（）%2;
????return?k;
}
int?randomNode（）//用來隨機節點
{
	int?k;
????
//????printf（“Ten?random?numbers?from?0?to?99nn\n“）;
????k=rand（）%n+1;
????return?k;
}
void?adjacencyCount（）//計算每一個節點鄰接邊的個數
{
	int?ij;
	for（i=1;i<=n;i++）
		for（j=1;j<=n;j++）
			edgecount[i]+=g[i][j];
}
void?initGraph（）//隨機生成一個連通圖，然后再生成歐拉圖
{
	int?ij;
	int?s;
	for（i=1;i<=n;i++）//先構造一個圖
	{
		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（）;//隨機圖中的節點????并相連
				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]）;
}
/*
以下為構造的歐拉圖
如果該點v1的度數為奇數，則在后面再找一個度數為奇數的點v2
（一）如果v1和v2相連，而且如果他們的度數都大于1，則去掉他們的連邊，否則繼續尋找度數為奇數的節點
?????如果v1和v2沒有相連，則相連v1和v2
（二）如果?（一）?失敗了，既沒有找到合適的點
??????1、則再找一度數為奇的點v3，和一個度數為偶的點v4，如果v4
????????和v1，v3沒有相連，則在v4和v1，v4和v3之間加邊。
??????2、（1）如果仍沒有找到，則將該點與任意不相連的節點之間加邊，重新執行變偶操作
	?????（2）如果找不到與該點不相連的節點，在任意找度數大于2的節點，去掉他們的連邊
*/
void?eularGraph（）//
{
	
	int?ijklm;
	int?v;//浪費了一部分空間
	int?retry?=?0;
	for（i=1;i<=n;i++）
	{
		printf（“%d%d\n“iedgecount[i]）;
		if（edgecount[i]%2!=0）//判斷該點的度數是否為偶數
		{
			j=1;
			for（j=i+1;j<=n;j++）//在相鄰的節點中尋找度數為奇數的節點
			{
				if（edgecount[j]%2!=0）//從相鄰的節點中找出度數為奇數的節點??（一）
				{
					if（g[i][j]）?//節點之間是否存在邊，不存在則連接這兩個節點
					{
						if（edgecount[i]!=1&&edgecount[j]!=1）//判斷i和j的節點的度數是否大于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）???//沒有找到合適的鄰接點?（二）
			{
		//		m?=?0;
				for（k=i+1;k<=n;k++）???????//（二）?1、則再找一度數為奇的點v3，1、和一個度數為偶的點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++）//這個地方?（二）?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++;
		//	}
			

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????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??歐拉圖問題\隨機建立歐拉圖.doc