數(shù)據(jù)庫(kù)怎么實(shí)現(xiàn)臨接矩陣

這篇文章主要介紹“數(shù)據(jù)庫(kù)怎么實(shí)現(xiàn)臨接矩陣”，在日常操作中，相信很多人在數(shù)據(jù)庫(kù)怎么實(shí)現(xiàn)臨接矩陣問題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”數(shù)據(jù)庫(kù)怎么實(shí)現(xiàn)臨接矩陣”的疑惑有所幫助！接下來(lái)，請(qǐng)跟著小編一起來(lái)學(xué)習(xí)吧！

       圖由頂點(diǎn)跟邊或者弧構(gòu)成  頂點(diǎn)不分大小主次  用一維數(shù)組表示頂點(diǎn)， 邊或弧 用二維數(shù)組存儲(chǔ)，二維數(shù)組就是鄰接矩陣

       G(V,E) 如果有N個(gè)頂點(diǎn) 則臨接矩陣為N*N 方陣

       維持一個(gè)二維數(shù)組，arr[i][j]表示i到j(luò)的邊，如果兩頂點(diǎn)之間存在邊，則為1，否則為0；  無(wú)向圖為對(duì)稱矩陣

       維持一個(gè)一維數(shù)組，存儲(chǔ)頂點(diǎn)信息，比如頂點(diǎn)的名字；

1. 鄰接矩陣（無(wú)向圖）的特點(diǎn)：

圖的鄰接矩陣存儲(chǔ)方式是用兩個(gè)數(shù)組來(lái)表示圖：

1.）一個(gè)一維數(shù)組存儲(chǔ)存儲(chǔ)圖中頂點(diǎn)信息。

2.）一個(gè)二維數(shù)組（稱為鄰接矩陣）存儲(chǔ)圖中邊或弧的信息。

上圖中我們?cè)O(shè)置兩個(gè)數(shù)組：

頂點(diǎn)數(shù)組：vertex[4] = {V0，V1，V2，V3}

邊數(shù)組：arc[4][4] 為對(duì)稱矩陣（0表示頂點(diǎn)間不存在邊，1表示頂點(diǎn)間存在邊）

2. 鄰接矩陣（有向圖）的特點(diǎn)：

無(wú)向圖的邊構(gòu)成了一個(gè)對(duì)稱矩陣，貌似浪費(fèi)了一半的空間，那如果是有向圖來(lái)存放，會(huì)不會(huì)把資源利用好呢？

頂點(diǎn)數(shù)組vertex[4] = {V0，V1，V2，V3}

弧數(shù)組arc[4][4]也是一個(gè)矩陣，但因?yàn)槭怯邢驁D，所以這個(gè)矩陣并不對(duì)稱。

如： V1到V0有弧，所以arc[1][0] = 1，而V0到V1沒有弧，所以arc[0][1] = 0 

3. 鄰接矩陣（網(wǎng)）的特點(diǎn)：

每條邊上帶有權(quán)的圖就叫網(wǎng)。通常權(quán)值表示兩點(diǎn)之間的距離。

這里∞表示一個(gè)計(jì)算機(jī)允許的，大于所有邊上權(quán)值的值。

定義臨接矩陣 圖結(jié)構(gòu)

typedef char Vtype;//頂點(diǎn)類型
typedef int   Etype;//邊或者弧上的權(quán)值 類型
#define MAXV 100 //最大頂點(diǎn)數(shù)
#define UNexist  65535 //不存在權(quán)值
typedef struct 
{
	Vtype VArr[MAXV];//頂點(diǎn)數(shù)組
	Etype EArr[MAXV][MAXV];//臨接矩陣
	int numV；//當(dāng)前頂點(diǎn)數(shù)
	int numE；//當(dāng)前邊數(shù)
}MGraph;

構(gòu)造一個(gè)圖  下面代碼為無(wú)向圖
void CreateMGraph(MGraph* G)
{
	int i,j,k,w;
	cout<<" 輸入頂點(diǎn)數(shù)";
	cin>> G->numV;
	cout<<" 輸入邊數(shù)";
	cin>> G->numE;
	for(i=0;i<G->numV;i++)
	{
		cin>> G->VArr[i];//輸入頂點(diǎn)的信息；
	}
	for(i=0;i<G->numV;i++)//將臨接矩陣初始化為空
	{
		for(j=0;j<G->numV;j++)
		{
			G->EArr[i][j] = UNexist;
		}
	}
	 for(k=0;k<G->numE;k++)
	 {
		cout<<"輸入邊的開始";
		cin>>i;
		cout<<"輸入邊的結(jié)尾";
		cin>>j;
		cout<<"輸入邊的權(quán)重";
		cin>>w;
		G->VArr[i][j]=W;
		G->VArr[i][j]=G->VArr[j][i]//無(wú)向圖 對(duì)稱
		//如果不是對(duì)稱的話 上面一行注釋點(diǎn)就好
	 }
}

V個(gè)頂點(diǎn) E個(gè)無(wú)向邊創(chuàng)建時(shí)時(shí)間復(fù)雜度為O( V^2)  鄰接矩陣是不錯(cuò)的圖存儲(chǔ)結(jié)構(gòu) 不過如果 頂點(diǎn)V之間相互存在的邊很少 那么就存在很多空間浪費(fèi)

到此，關(guān)于“數(shù)據(jù)庫(kù)怎么實(shí)現(xiàn)臨接矩陣”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)?lái)更多實(shí)用的文章！