小白BG.1 鄰接矩陣表示的圖結(jié)點(diǎn)的結(jié)構(gòu)

typedef struct GNode *PtrToGNode;//PtrToGNode是指向GNode的一個(gè)指針
struct GNode{
int Nv;//頂點(diǎn)數(shù)
int Ne;//邊數(shù)
WeightType G[MaxVertexNum][MaxVertexNum];
DataType Data[MaxVertexNum];//存頂點(diǎn)的數(shù)據(jù)
};
typedef PtrToGNode MGraph;//以鄰接矩陣存儲(chǔ)的圖類型。定義為指向節(jié)點(diǎn)的指針。因?yàn)橐玫降臅r(shí)候
一個(gè)指針遠(yuǎn)遠(yuǎn)比一整個(gè)圖來(lái)的快捷

小白BG.2 鄰接矩陣表示的圖——初始化

初始化一個(gè)有VertexNum個(gè)頂點(diǎn)但沒有邊的圖

興安網(wǎng)站制作公司哪家好，找創(chuàng)新互聯(lián)！從網(wǎng)頁(yè)設(shè)計(jì)、網(wǎng)站建設(shè)、微信開發(fā)、APP開發(fā)、響應(yīng)式網(wǎng)站開發(fā)等網(wǎng)站項(xiàng)目制作，到程序開發(fā)，運(yùn)營(yíng)維護(hù)。創(chuàng)新互聯(lián)成立于2013年到現(xiàn)在10年的時(shí)間，我們擁有了豐富的建站經(jīng)驗(yàn)和運(yùn)維經(jīng)驗(yàn)，來(lái)保證我們的工作的順利進(jìn)行。專注于網(wǎng)站建設(shè)就選創(chuàng)新互聯(lián)。

typedef int Vertex;//用頂點(diǎn)下標(biāo)表示頂點(diǎn)，為整型
MGraph CreateGraph(int VertexNum)//VertexNum這個(gè)頂點(diǎn)數(shù)真的是整數(shù)，
{
Vertex V , W;//我們?cè)谡f(shuō)V跟W的時(shí)候不是在說(shuō)整數(shù)，而是頂點(diǎn)
MGraph Graph;
Graph = (MGraph)malloc(sizeof(struct GNode));
Graph->Nv = VertexNum;
Graph->Ne = 0;
//注意：這里默認(rèn)頂點(diǎn)編號(hào)從0開始，到(Graph->Nv - 1)
for(V=0;VNv;V++)
for((W=0;WNv;W++))
Graph->G[V][M] = 0;//或者INFINITY，表示這兩個(gè)頂點(diǎn)之間是沒有邊的
return Graph
}

小白BG.3 鄰接矩陣表示的圖——插入邊

typedef struct ENode *PtrToENode;
struct ENode{
Vertex V1,V2;//有向邊，V1V2兩個(gè)頂點(diǎn)一個(gè)出發(fā)點(diǎn)一個(gè)終點(diǎn)
WeightType Weight;//權(quán)重，有權(quán)圖才需要。權(quán)重的類型是WeightType
};
typedef PtrToENode Edge;
void InsertEdge(MGraph Graph,Edge E)
{
//插入邊，這是一條邊
Graph->G[E->V1][E->V2] = E->Weight;
//無(wú)向圖的話還需要一條邊(一共兩條)，Graph->G[E->V2][E->V1] = E->Weight;
}

小白BG.4 鄰接矩陣表示的圖——建立圖 完整的建立一個(gè)MGraph

輸入格式

1. Nv Ne

2. V1 V2 Weight

3. ......

MGraph BuildGraph()
{
MGraph Graph;
scanf("%d",&Nv);
Graph = CreateGraph(Nv);
//讀入邊數(shù)
scanf("%d",&(Graph->Ne));
if(Graph ->Ne = 0){//有邊就還需要經(jīng)過(guò)這里，沒有邊直接結(jié)束
E = (Edge)malloc(sizeof(struct ENode));//臨時(shí)存一下邊
for(i = 0; i< Graph->Ne; i++){
scanf("%d %d %d",&E->V1,&E->V2,&E->Weight);
InsertEdge(Graph,E);
}
}
//如果頂點(diǎn)有數(shù)據(jù)的話，讀入數(shù)據(jù)
for(V=0;VNv;V++)
scanf("%c",&(Graph->Data[V]));
return Graph;
}

簡(jiǎn)易建法

int G[MAXN][MAXN],Nv,Ne;//聲明為全局變量
void BuildGraph()
{
int i,j,v1,v2,w;
scanf("%d",&Nv);
//CreateGraph
for(i=0;i 小白BG.5 鄰接表表示的圖結(jié)點(diǎn)的結(jié)構(gòu)

鄰接表：G[N]為指針數(shù)組，對(duì)應(yīng)矩陣每一行一個(gè)鏈表，只存非0元素

typedef struct GNode *PtrToGNode;
struct GNode {
int Nv;//頂點(diǎn)數(shù)
int Ne;//邊數(shù)
AdjList G;//鄰接表
};
typedef PtrToGNode LGraph;
//以鄰接表方式存儲(chǔ)的圖類型
//AdjList是自己定義的
typedef struct Vnode{
PtrToAdjVNode FirstEdge;
DataType Data;//存頂點(diǎn)的數(shù)據(jù)
}AdjList[MaxVertexNum];//AdjList是鄰接表類型
typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode{
Vertex AdjV;//鄰接點(diǎn)下標(biāo)，定義為整型
WeightType Weight;//邊權(quán)重
PtrToAdjVNode Next;
};

小白BG.6 鄰接表表示的圖——建立圖

初始化一個(gè)有VertexNum個(gè)頂點(diǎn)但沒有邊的圖

typedef int Vertex;//用頂點(diǎn)下標(biāo)表示頂點(diǎn)，為整型
LGraph CreateGraph(int VertexNum)
{
Vertex V,W;
LGraph Graph;
Graph = (LGraph)malloc(sizeof(struct GNode));
Graph->Nv = VertexNum;
Graph->Ne = 0;
//沒有邊的意思是每個(gè)頂點(diǎn)跟著的那個(gè)鏈表都是空的
//注意：這里默認(rèn)頂點(diǎn)編號(hào)從0開始，到(Graph->Nv - 1)
for(V=0;VNv;V++)
Graph->G[V].FirstEdge = NULL;
return Graph;
}

void InsertEdge(LGraph Graph,Edge E)
{
PtrToAdjVNode NewNode;
//-------------------插入邊------------------------------
//為V2建立新的鄰接點(diǎn)
NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjNode));
NewNode->AdjV = E->V2;
NewNode->Weight = E->Weight
//將V2插入到V1的表頭
NewNode->Next = Graph->G[E->V1].FirstEdge;
Graph->G[E->V1].FirstEdge = NewNode;
//-------------------若是無(wú)向圖，還需插入邊------------------
//為V1建立新的鄰接點(diǎn)
NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjNode));
NewNode->AdjV = E->V1;
NewNode->Weight = E->Weight
//將V2插入到V1的表頭
NewNode->Next = Graph->G[E->V2].FirstEdge;
Graph->G[E->V2].FirstEdge = NewNode;
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

本文標(biāo)題：數(shù)據(jù)結(jié)構(gòu)和算法之如何建立圖-創(chuàng)新互聯(lián)
鏈接地址：http://www.chinadenli.net/article18/despgp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站改版、微信公眾號(hào)、搜索引擎優(yōu)化、響應(yīng)式網(wǎng)站、品牌網(wǎng)站設(shè)計(jì)、網(wǎng)站策劃

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)