數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告-資料下載頁(yè)
2025-04-14 04:41本頁(yè)面
【正文】 1；否則num=0 if(num!=1) { printf(不存在歐拉圖！\n)。 getchar()。 exit(0)。 } m=dfs_trave(mg)。//判斷圖是否為連通圖 if(m!=1) printf(不存在歐拉圖！\n)。 else printf(存在歐拉圖！\n)。 getch()。}MGraph *creat_MGraph()//建立鄰接矩陣{ int i,j,k,n,e。 MGraph *mg=malloc(sizeof(MGraph))。 printf(請(qǐng)輸入頂點(diǎn)的個(gè)數(shù)：)。 scanf(%d,amp。n)。 printf(請(qǐng)輸入邊的條數(shù)：)。 scanf(%d,amp。e)。 mgn=n。 mge=e。 getchar()。 for(i=1。i=n。i++) for(j=1。j=n。j++) mgedges[i][j]=0。//初始化鄰接矩陣表示的所有邊 printf(請(qǐng)輸入邊的信息:\n)。 for(i=1。i=e。i++) { scanf(%d%d,amp。j,amp。k)。 mgedges[j][k]=1。mgedges[k][j]=1。//標(biāo)記存在的邊 } return mg。//返回鄰接矩陣的首地址}int Euleriancycle(MGraph *mg)//判斷是否存在歐拉回路{ int i,j,num。 for(i=1。i=mgn。i++)//從第一個(gè)頂點(diǎn)開(kāi)始，判斷頂點(diǎn)的度數(shù) { num=0。//初始化每個(gè)頂點(diǎn)的度數(shù)為0 for(j=1。j=mgn。j++) { If((mgedges[i][j]!=0)amp。amp。(i!=j))//如果頂點(diǎn)i到j(luò)的邊存在度數(shù)加1 num=num+1。 } if(num%2==1)//如果有哪個(gè)頂點(diǎn)的度數(shù)為奇數(shù)，直接退出循環(huán)，返回0 return 0。 } return 1。//當(dāng)所有的頂點(diǎn)都判斷完成還沒(méi)有退出本函數(shù)說(shuō)明所有頂點(diǎn)度數(shù)均為偶數(shù)，返回1}int dfs_trave(MGraph *mg)//深度優(yōu)先搜索遍歷{ int i,m=0。 for(i=1。i=mgn。i++)//將輔助變量全部初始化為0，表明頂點(diǎn)沒(méi)有被訪問(wèn)過(guò) visited[i]=0。 for(i=1。i=mgn。i++) if(visited[i]==0)//對(duì)沒(méi)有訪問(wèn)過(guò)的頂點(diǎn)，調(diào)用深度優(yōu)先搜索函數(shù) { dfs(mg,i)。//深度優(yōu)先搜索 m=m+1。//如果是非連通圖，要調(diào)用1次以上，m用來(lái)記錄調(diào)用dfs函數(shù)的次數(shù) } return m。//返回調(diào)用dfs函數(shù)的次數(shù)}void dfs(MGraph *mg,int i)//深度優(yōu)先搜索{ int j。 visited[i]=1。//訪問(wèn)該頂點(diǎn) for(j=1。j=mgn。j++) if((visited[j]==0)amp。amp。(mgedges[i][j]==1))//當(dāng)頂點(diǎn)沒(méi)有被訪問(wèn)過(guò)并且兩頂點(diǎn)存在邊 dfs(mg,j)。//對(duì)該頂點(diǎn)深度優(yōu)先搜索}
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1