到這里，收集到的吉林大學(xué)的5個(gè)研究生機(jī)試題目就已經(jīng)寫完了。接下來寫那個(gè)學(xué)校的好呢？看心情了！

題目描述

給定一個(gè)無向圖和其中的所有邊，判斷這個(gè)圖是否所有頂點(diǎn)都是連通的。

輸入

每組數(shù)據(jù)的第一行是兩個(gè)整數(shù) n 和 m（0<=n<=1000）。n表示圖的頂點(diǎn)數(shù)目，m 表示圖中邊的數(shù)目。如果 n 為 0 表示輸入結(jié)束。隨后有 m 行數(shù)據(jù)，每行有兩個(gè)值 x 和y（0<x, y <=n），表示頂點(diǎn) x 和 y 相連，頂點(diǎn)的編號從 1開始計(jì)算。輸入不保證這些邊是否重復(fù)。

輸出

對于每組輸入數(shù)據(jù)，如果所有頂點(diǎn)都是連通的，輸出"YES"，否則輸出"NO"。

樣例輸入

4 31 22 33 23 21 22 30 0

樣例輸出

NOYES

//首先，我覺得有必要溫習(xí)一下圖的連通性的相關(guān)概念
// I無向圖G的連通性：
//若無向圖G中的任何兩個(gè)結(jié)點(diǎn)都是可達(dá)的，則稱G是連通圖(connected graph)，
//否則稱G是非連通圖(unconnected graph)或分離圖(separated graph)
// II有向圖G的連通性：
//若將有向圖G所有邊的方向略去，得無向圖G'

//若G'是連通圖則成G是連通圖或弱連通圖(weakly connected graph),否則為非連通圖
//若G中任何一對結(jié)點(diǎn)間至少有一個(gè)結(jié)點(diǎn)是可達(dá)的，則成G是單向連通圖(unilaterally connected graph)
//若G中任何一對結(jié)點(diǎn)之間都是相互可達(dá)的，則稱G是強(qiáng)連通圖(strongly connected graph)
//G是強(qiáng)連通圖的充要條件是:G中存在一條經(jīng)過所有結(jié)點(diǎn)的回路
//

//Dijkstra算法可用于解決一個(gè)點(diǎn)與其他點(diǎn)之間的最短路徑問題,時(shí)間復(fù)雜度為O(n*n)
//Floyd算法是利用二維矩陣解決任意兩個(gè)節(jié)點(diǎn)間的最短路徑問題，時(shí)間復(fù)雜度為O(n*n*n)
// 鑒于Floyd算法中利用了二維矩陣，算法也相對而言易于實(shí)現(xiàn)，這里采用Floyd算法
//
// 實(shí)際上用Dijkstra算法就足夠了，我們只需要判定一個(gè)節(jié)點(diǎn)V0到其余各節(jié)點(diǎn)Vi是否可達(dá)
// 如果可達(dá)必然就是連通圖,因?yàn)榧热籚0可以達(dá)到各節(jié)點(diǎn)Vi

// 那么任何一個(gè)節(jié)點(diǎn)必然可以以V0為跳板到其他各節(jié)點(diǎn)
// 在用Floyd算法處理長度矩陣后，我們可以利用這個(gè)思想來檢驗(yàn)V0到其余節(jié)點(diǎn)是否可達(dá)來驗(yàn)證無向圖的連通性
// Dijkstra算法的實(shí)現(xiàn)方式

#include<iostream>
using namespace std;

#define MAX 50//圖的節(jié)點(diǎn)數(shù)最大值，懶得設(shè)成1000了，我才懶得輸入那么多數(shù)據(jù)呢
#define INFINITE 10000//設(shè)定兩點(diǎn)間不可達(dá)的標(biāo)識

//根據(jù)輸入的邊的信息更新長度矩陣數(shù)據(jù)
void Process(int d[][MAX],int v1,int v2);
//實(shí)現(xiàn)Floyd算法的函數(shù)了,d為長度矩陣，n為節(jié)點(diǎn)數(shù)目
void Floyd(int d[][MAX],int n);
//判斷無向圖G是否可達(dá)
bool Connected(int d[][MAX],int n);
//寫個(gè)Floyd的一部分就可以解決問題，實(shí)際復(fù)雜度為O(n*n)
void Floyd1(int d[][MAX],int n);

int main()
{
int d[MAX][MAX];//長度矩陣
// 二維矩陣實(shí)際上也是地址連續(xù)的,對其進(jìn)行初始化
memset(d,INFINITE,MAX*MAX);
int n;//節(jié)點(diǎn)數(shù)目
int m;//邊的數(shù)目
cout<<"Input thenumber of vertex and edges:";
cin>>n;
while(n)
{
//其實(shí)這里不設(shè)置對角線的值也可以判斷圖的連通性,只是求出的最短路徑是錯(cuò)的
for(intt=0;t<n;++t) d[t][t]=0;
cin>>m;
int v1,v2;//兩個(gè)節(jié)點(diǎn)
cout<<"Inputthe two vertexes of each edge:";
for(inti=0;i<m;++i)
{
cin>>v1>>v2;
Process(d,v1,v2);
}
//下面一行替換成Floyd1照樣可以正常運(yùn)行出結(jié)果
Floyd(d,n);//運(yùn)用Floyd算法處理長度矩陣
if(Connected(d,n))cout<<"Yes"<<endl;
elsecout<<"No"<<endl;
cout<<"Inputthe number of vertex:";
cin>>n;
}
return 0;
}

//根據(jù)輸入的邊的信息更新長度矩陣數(shù)據(jù)
void Process(int d[][MAX],int v1,int v2)
{
if(v1<=0||v2<=0)return;//節(jié)點(diǎn)數(shù)據(jù)必須大于0，否則不做任何處理
d[v1-1][v2-1]=d[v2-1][v1-1]=1;//1表示結(jié)點(diǎn)間可達(dá)
}

void Floyd(int d[][MAX],int n)
{
int tmp;
//時(shí)間復(fù)雜度為O(n*n*n)
for(int i=0;i<n;++i)
for(intj=0;j<n;++j)
for(intk=0;k<n;++k)
{
tmp=d[i][k]+d[k][j];
if(tmp<d[i][j])d[i][j]=tmp;
}
}

//判斷無向圖G是否可達(dá)
bool Connected(int d[][MAX],int n)
{
bool test=true;
for(inti=0;i<n&&test;++i)
if(d[0][i]>=INFINITE)test=false;
return test;
}

//Dijkstra算法我就不寫了，實(shí)際寫個(gè)Floyd的一部分就可以求出圖的連通性，反正不用求出最短路徑
void Floyd1(int d[][MAX],int n)
{
int tmp;
//時(shí)間復(fù)雜度為O(n*n)
for(int j=0;j<n;++j)
{
if(d[0][j]<INFINITE)continue;//節(jié)點(diǎn)間已經(jīng)可達(dá)
for(intk=0;k<n;++k)
{
tmp=d[0][k]+d[k][j];
if(tmp<d[0][j])d[0][j]=tmp;
}
}
}

愛華網(wǎng)本文地址 » http://www.klfzs.com/a/25101017/367423.html