一：圖的基本概念和術(shù)語

1.圖之間的關(guān)系可以是任意的，任意兩個數(shù)據(jù)元素之間都可能相關(guān)。

2.頂點：數(shù)據(jù)元素。

3.邊or弧：從一個頂點到另一個頂點的路徑。<V, W>表示弧，（V,W）表示邊，V是弧尾，W是弧頭，此時為有向圖，否則為無向圖。

4.對于無向圖，邊的取值范圍是0到1/2*n*(n-1)。有1/2*n*(n-1)條邊的無向圖為完全圖。對于有向圖，邊的取值范圍0到n*(n-1),n*(n-1)稱做有向完全圖。

5.多條邊的是稠密圖，少邊的是稀疏圖。

6.對于無向圖，頂點V的度是相連的邊數(shù)；頂點V的入度是以V為頭的弧數(shù)，出度是以V為尾的弧數(shù)。

7.連通圖：對于圖中任意頂點都能連通。

8.最小生成樹：極小連通子圖。

二：圖的存儲結(jié)構(gòu)

常見的圖的存儲結(jié)構(gòu)分為：鄰接表、鄰接多重表、十字鏈表。

?

?

?

能方便使用的是鄰接表，下面是其代碼實現(xiàn)：

在鄰接表中對圖中的每一個頂點建立一個單鏈表，每個結(jié)點的組成尾三部分，adjvex(指向鄰接點)-nextarc(指向下一結(jié)點)-info(頂點信息)，加一個頭結(jié)點，data(數(shù)據(jù)域)-firstarc(鄰接點)。

?

?

鄰接表存儲：

#include<string.h>#include<ctype.h>#include<malloc.h> /* malloc()等 */#include<limits.h> /* INT_MAX等 */#include<stdio.h> /* EOF(=^Z或F6),NULL */#include<stdlib.h> /* atoi() */#include<io.h> /* eof() */#include<math.h> /* floor(),ceil(),abs() */#include<process.h> /* exit() *//* 函數(shù)結(jié)果狀態(tài)代碼 */#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1typedef int Status; /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 */typedef int Boolean; /* Boolean是布爾類型,其值是TRUE或FALSE */#define MAX_NAME 5 /* 頂點字符串的最大長度 */typedef int InfoType;typedef char VertexType[MAX_NAME]; /* 字符串類型 *//* c7-2.h 圖的鄰接表存儲表示 */#define MAX_VERTEX_NUM 20typedef enum{DG,DN,AG,AN}GraphKind; /* {有向圖,有向網(wǎng),無向圖,無向網(wǎng)} */typedef struct ArcNode{int adjvex; /* 該弧所指向的頂點的位置 */struct ArcNode *nextarc; /* 指向下一條弧的指針 */InfoType *info; /* 網(wǎng)的權(quán)值指針） */}ArcNode; /* 表結(jié)點 */typedef struct{VertexType data; /* 頂點信息 */ArcNode *firstarc; /* 第一個表結(jié)點的地址,指向第一條依附該頂點的弧的指針 */}VNode,AdjList[MAX_VERTEX_NUM]; /* 頭結(jié)點 */typedef struct{AdjList vertices;int vexnum,arcnum; /* 圖的當(dāng)前頂點數(shù)和弧數(shù) */int kind; /* 圖的種類標(biāo)志 */}ALGraph;

?

三：圖的遍歷

從圖的某一頂點出發(fā)訪問圖的其它結(jié)點，且只訪問一次，叫圖的遍歷。

1.圖的深度優(yōu)先遍歷(DFS)

2.圖的廣度優(yōu)先遍歷(BFS)

?

四：圖的最小生成樹

求最小生成樹算法：普里姆算法、克魯斯卡爾算法。

?

?

五：拓?fù)渑判?/h1>

簡單的說，就是由某個集合上的偏序求全序。用AOV-網(wǎng)中頂點來表示活動，多應(yīng)用于求工程能否進(jìn)行。

?

六：關(guān)鍵路徑

?

用到AOE-網(wǎng)中弧表示活動，頂點表示事件，從源點到終點的最長路徑為關(guān)鍵路徑。

?

七：最短路徑

?

求單源點到其他頂點的最短路徑：迪杰斯特拉算法。

求每一對頂點的最短路徑:弗洛伊德算法。

?

?

?

總結(jié)

以上是生活随笔為你收集整理的图的知识点总结-数据结构的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。