??專欄【數(shù)據(jù)結構】
??喜歡的詩句：更喜岷山千里雪 三軍過后盡開顏。
??音樂分享【Dream It Possible】
大一同學小吉，歡迎并且感謝大家指出我的問題??
目錄
??前言
??圖的定義?
???????有向完全圖
??????無向完全圖
??存儲結構
??????鄰接矩陣?
??代碼
??????采用鄰接矩陣表示法創(chuàng)建無向? 網(wǎng)
??算法步驟
??算法描述
???????采用鄰接矩陣表示法創(chuàng)建無向? 網(wǎng)
??圖的遍歷
???????深度優(yōu)先遍歷
??算法步驟
??算法描述
??廣度優(yōu)先遍歷
??算法步驟
??算法描述
??附加?
??????實驗題目
??????代碼
??????運行結果?
?文章來源地址http://www.zghlxwxcb.cn/news/detail-457249.html
??前言
????????圖是一種比線性表和樹更為復雜的數(shù)據(jù)結構。在線性表中，數(shù)據(jù)元素之間僅有線性關系，每個數(shù)據(jù)元素只有一個直接前驅和一個直接后繼；在樹結構中，數(shù)據(jù)元素之間有著明顯的層次關系，并且每一層中的數(shù)據(jù)元素可能和下一層中的多個元素(其孩子結點)相關，但只能和上一層中一個元素(其雙親結點)相關；而在圖結構中，結點之間的關系可以是任意的，圖中任意兩個數(shù)據(jù)元素都可能相關。由此，圖的應用極為廣泛，已滲入諸如物理、化學、通信、計算機，以及數(shù)學等領域。在離散數(shù)學中，圖論是專門研究圖的性質的數(shù)學分支，而在數(shù)據(jù)結構中，則應用圖論的知識討論如何在計算機上實現(xiàn)圖的操作，因此本章主要介紹圖的存儲結構，以及若干圖的操作的實現(xiàn)。
??圖的定義?
????????圖(Graph)G由兩個集合V和E組成，記為G=(V，E)，其中V是頂點的有窮非空集合，E是V中頂點偶對的有窮集合，這些頂點偶對稱為邊。V(G)和E(G)通常分別表示圖G的頂點集合和邊集合，E(G)可以為空集。若E(G)為空，則圖G只有頂點而沒有邊。
????????對于圖G，若邊集E(G)為有向邊的集合，則稱該圖為有向圖；若邊集E(G)為無向邊的集合，則稱該圖為無向圖。
????????在有向圖中，頂點對<x，y>是有序的，它稱為從頂點x到頂點y的一條有向邊。因此，<x，y>與1是不同的兩條邊。頂點對用尖括號括起來，對<x，y>而言，x是有向邊的始點，y是有向邊的終點。<x，y>也稱作一條弧，則x為弧尾，y為弧頭。
????????在無向圖中，頂點對(x，y)是無序的，它稱為與頂點x和頂點y相關聯(lián)的一條邊。這條邊沒有特定的方向，(x，y)與(y，x)是同一條邊。為了有別于有向圖，無向圖的頂點對用一對圓括號括起來。
???????有向完全圖
有n(n-1)條弧? 的圖
??????無向完全圖
有n(n-1)/2條邊? 的圖
??存儲結構
??????鄰接矩陣?
表示頂點之間相鄰關系的矩陣，設G(V，E)是具有n個頂點的圖，那么G的鄰接矩陣有如下性質
（矩陣實在是畫不好，繪圖能力欠佳，也請大家多多包容??）?
?使用鄰接矩陣表示圖，除了一個用于存儲鄰接矩陣的二維數(shù)組外，還需要一個一維數(shù)組來存儲頂點信息
??代碼
//圖的 鄰接矩陣 存儲表示
#define MaxInt 32767 //表示極大值，即 ∞
#define MVNum 100 //最大頂點數(shù)
typedef int VerTexType; //設頂點的數(shù)據(jù)類型為字符型
typedef int ArcType; //假設邊的權值類型為整型
typedef struct{
VerTexType vexs[MVNum]; //頂點表
ArcType arcs[MVNum][MVNum]; //鄰接矩陣
int vexnum,arcnum; //圖的當前點數(shù)和邊數(shù)
}AMGraph; ??????采用鄰接矩陣表示法創(chuàng)建無向? 網(wǎng)
??算法步驟
1.輸入總頂點數(shù)和總邊數(shù)
2.依次輸入點的信息并將其存入頂點表中
3.初始化鄰接矩陣，每個權值初始化為最大值
4.構造鄰接矩陣，依次輸入每條邊依附的頂點以及其權值，確定兩個頂點在圖中的位置之后，使相應邊賦予相應的權值，同時使其對稱邊賦予相同的權值
??算法描述
int located(AMGraph &G, VerTexType v)
{
for (int i = 0; i < G.vexnum; i++) {
if (G.vexs[i] == v) {
return i;
}
}
return -1; // 未找到，返回 -1
}
int Create(AMGraph &G)
{
cin>>G.vexnum>>G.arcnum;
for(i=0;i<G.vexnum;i++)
{
cin>>G.vexs[i];
}
for(i=0;i<G.vexnum;i++)
{
for(j=0;j<G.vexnum;j++)
{
G.arcs[i][j]=MaxInt;
}
}
for(int k=0;k<G.arcnum;k++)
{
cin>>v1>>v2>>w;
i=located(G,v1);
j=located(G,v2);
G.arcs[i][j]=w;
G.arcs[j][i]=G.arcs[i][j];
}
return 1;
}???????采用鄰接矩陣表示法創(chuàng)建無向? 網(wǎng)
進行兩處改動即可
1.初始化鄰接矩陣時，把邊的權值初始化為0
2.構造鄰接矩陣時，把權值w修改為1即可
??圖的遍歷
圖的遍歷也是從圖的某一頂點出發(fā)，按照某種方法對圖的所有頂點進行訪問且訪問一次
實質：找每個節(jié)點的鄰接點
???????深度優(yōu)先遍歷
??算法步驟
?
??算法描述
void DFS(AMGraph G, int v)
{
printf("%d ", G.vexs[v]); // 訪問頂點 v
visited[v] = true; // 標記為已訪問
for (int w = 0; w < G.vexnum; w++)
{
if (G.arcs[v][w] != MaxInt && !visited[w])
{
DFS(G, w); // 對未訪問的鄰接頂點遞歸調用DFS
}
}
}??廣度優(yōu)先遍歷
??算法步驟
?
??算法描述
void BFS(AMGraph G, int v)
{
int front = 0, rear = 0;
int queue[MVNum]; // 定義隊列
printf("%d ", G.vexs[v]);
visited[v] = true;
queue[rear++] = v; // 將頂點 v 入隊
while (front != rear)
{
int k = queue[front++]; // 出隊一個頂點 k
for (int w = 0; w < G.vexnum; w++)
{
if (G.arcs[k][w] != MaxInt && !visited[w])
{
printf("%d ", G.vexs[w]); // 訪問頂點 w
visited[w] = true;
queue[rear++] = w; // 將頂點 w 入隊
}
}
}
}??附加?
??????實驗題目
?
1.使用鄰接矩陣的方式存儲上邊無向圖；
2.以矩陣的形式輸出無向圖
3.在鄰接矩陣的基礎上實現(xiàn)深度優(yōu)先遍歷和廣度優(yōu)先遍歷。
??????代碼
/*
6 6
1 2 3 4 5 6
1 2 1
2 5 1
5 3 1
3 1 1
1 4 1
4 6 1
*/
#include<iostream>
using namespace std;
#define MaxInt 32767 //表示極大值，即 ∞
#define MVNum 100 //最大頂點數(shù)
typedef int VerTexType; //設頂點的數(shù)據(jù)類型為字符型
typedef int ArcType; //假設邊的權值類型為整型
typedef struct{
VerTexType vexs[MVNum]; //頂點表
ArcType arcs[MVNum][MVNum]; //鄰接矩陣
int vexnum,arcnum; //圖的當前點數(shù)和邊數(shù)
}AMGraph; //Adjacency Matrix Graph
int v1,v2,i,j,k,w;
int located(AMGraph &G, VerTexType v)
{
for (int i = 0; i < G.vexnum; i++) {
if (G.vexs[i] == v) {
return i;
}
}
return -1; // 未找到，返回 -1
}
int Create(AMGraph &G)
{
cin>>G.vexnum>>G.arcnum;
for(i=0;i<G.vexnum;i++)
{
cin>>G.vexs[i];
}
for(i=0;i<G.vexnum;i++)
{
for(j=0;j<G.vexnum;j++)
{
G.arcs[i][j]=MaxInt;
}
}
for(int k=0;k<G.arcnum;k++)
{
cin>>v1>>v2>>w;
i=located(G,v1);
j=located(G,v2);
G.arcs[i][j]=w;
G.arcs[j][i]=G.arcs[i][j];
}
return 1;
}
bool visited[MVNum];
// 深度優(yōu)先遍歷
void DFS(AMGraph G, int v)
{
printf("%d ", G.vexs[v]); // 訪問頂點 v
visited[v] = true; // 標記為已訪問
for (int w = 0; w < G.vexnum; w++)
{
if (G.arcs[v][w] != MaxInt && !visited[w])
{
DFS(G, w); // 對未訪問的鄰接頂點遞歸調用DFS
}
}
}
// 廣度優(yōu)先遍歷
void BFS(AMGraph G, int v)
{
int front = 0, rear = 0;
int queue[MVNum]; // 定義隊列
printf("%d ", G.vexs[v]);
visited[v] = true;
queue[rear++] = v; // 將頂點 v 入隊
while (front != rear)
{
int k = queue[front++]; // 出隊一個頂點 k
for (int w = 0; w < G.vexnum; w++)
{
if (G.arcs[k][w] != MaxInt && !visited[w])
{
printf("%d ", G.vexs[w]); // 訪問頂點 w
visited[w] = true;
queue[rear++] = w; // 將頂點 w 入隊
}
}
}
}
int main()
{
AMGraph G;
Create(G);
printf("存儲成功\n");
// 輸出鄰接矩陣
for (int i = 0; i < G.vexnum; i++)
{
for (int j = 0; j < G.vexnum; j++)
{
if (G.arcs[i][j] == MaxInt)
{
printf("∞ ");
}
else
{
printf("%d ", G.arcs[i][j]);
}
}
printf("\n");
}
// 初始化訪問標記數(shù)組
for (int i = 0; i < G.vexnum; i++)
{
visited[i] = false;
}
printf("深度優(yōu)先遍歷: ");
for (int i = 0; i < G.vexnum; i++)
{
if (!visited[i])
{
DFS(G, i);
}
}
printf("\n");
// 重置訪問標記數(shù)組
for (int i = 0; i < G.vexnum; i++)
{
visited[i] = false;
}
printf("廣度優(yōu)先遍歷: ");
for (int i = 0; i < G.vexnum; i++)
{
if (!visited[i])
{
BFS(G, i);
}
}
printf("\n");
return 0;
}??????運行結果?
??如果大家有不明白的地方，或者文章有問題，歡迎大家在評論區(qū)討論，指正?????文章來源：http://www.zghlxwxcb.cn/news/detail-457249.html
?
到了這里，關于【數(shù)據(jù)結構】圖的定義，存儲，遍歷的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
