第七章 圖論

一、數(shù)據(jù)結(jié)構(gòu)定義

1. 圖的鄰接矩陣存儲(chǔ)法

   #define MaxVertexNum 100 // 節(jié)點(diǎn)數(shù)目的最大值
   
   // 無(wú)邊權(quán)，只用0或1表示邊是否存在
   bool graph[MaxVertexNum][MaxVertexNum];
   
   // 有邊權(quán)
   int graph[MaxVertexNum][MaxVertexNum];
   

2. 圖的鄰接表存儲(chǔ)法
   把所有節(jié)點(diǎn)存儲(chǔ)為節(jié)點(diǎn)數(shù)組，每個(gè)節(jié)點(diǎn)里有自己的數(shù)據(jù)和一個(gè)邊指針，這個(gè)邊指針相當(dāng)于一個(gè)鏈表的頭指針，這個(gè)鏈表里存放所有與這個(gè)節(jié)點(diǎn)相連的邊，邊里存放該邊指向的節(jié)點(diǎn)編號(hào)和下一條邊指針
   
   

   #define MaxVertexNum 100 // 節(jié)點(diǎn)數(shù)目的最大值
   typedef struct EdgeNode{ // 邊表節(jié)點(diǎn)
   	int adjvex; // 該邊所指向的節(jié)點(diǎn)編號(hào)
   	struct EdgeNode *next; // 指向下一條邊的指針
   	// Infotype info; // 邊權(quán)值（如果有）
   }EdgeNode;
   
   typedef struct VNode{ //節(jié)點(diǎn)表節(jié)點(diǎn)
   	VertexType data; // 節(jié)點(diǎn)信息
   	EdgeNode *first; // 指向第一條依附該節(jié)點(diǎn)的邊的指針
   }VNode;
   
   typedef struct{
   	int verNum, edgeNum; // 節(jié)點(diǎn)數(shù)和邊數(shù)
   	VNode AdjList[MaxVertexNum]; // 節(jié)點(diǎn)數(shù)組
   } ALGraph; // 鄰接表
   

3. 圖的十字鏈表存儲(chǔ)法（有向圖）

   分為弧節(jié)點(diǎn)和頂點(diǎn)節(jié)點(diǎn)。一個(gè)弧指向兩個(gè)?。ㄊ撬膬蓚€(gè)下一接替者），一個(gè)頂點(diǎn)指向兩個(gè)?。ǘ际撬牡谝蝗危?br> 此外，十字鏈表還可用于存儲(chǔ)稀疏矩陣，矩陣的各行各列都各用一個(gè)鏈表存儲(chǔ)，同時(shí)將所有行鏈表的表頭rhead存儲(chǔ)到一個(gè)數(shù)組，所有列鏈表的表頭存儲(chǔ)到另一個(gè)數(shù)組chead中。
   可以將十字鏈表記憶為串起來(lái)的三元組，即一個(gè)邊節(jié)點(diǎn)記為（行，value，列）（即（弧尾，權(quán)值，弧頭）），多個(gè)三元組的行和列分別串成一個(gè)鏈表，代表相同行的元素以及相同列的元素（即弧尾相同和弧頭相同的元素）
   

   typedef struct edgeNode{
   	int headVer, tailVer; 
   	struct edgeNode *hLink, *tLink; // 分別指向弧頭和弧尾相同的下一條邊
   	infoType info;
   } edgeNode;
   
   typedef struct VNode{
   	VerType data;
   	edgeNode *firstIn, *firstOut; // 分別指向入邊表和出邊表中的第一個(gè)邊節(jié)點(diǎn)
   } VNode;
   
   typedef struct{
   	int verNum, edgeNum;
   	VNode XList[verNum]; // 頂點(diǎn)表
   } OLGraph;
   

4. 圖的鄰接多重表存儲(chǔ)法（無(wú)向圖）
   

   typedef struct edgeNode{
   	int iVer, jVer; // 邊的兩個(gè)頂點(diǎn)在頂點(diǎn)表（數(shù)組）里的下標(biāo)
   	struct edgeNode *iLink, *jLink; // 和頂點(diǎn)相連的下一條邊
   	infoType info; // 帶權(quán)圖可存儲(chǔ)邊的權(quán)值
   } edgeNode;
   
   typedef struct VNode{
   	VerType data;
   	edgeNode *firstEdge;
   } VNode;
   
   typedef struct{
   	int verNum, edgeNum; // 圖的頂點(diǎn)數(shù)和邊數(shù)
   	VNode adjMuList[verNum];
   } AMLGraph; 
   

二、代碼/算法

1. 遍歷/搜索
   • DFS實(shí)現(xiàn)

     #define MaxVertexNum 100  // 圖中節(jié)點(diǎn)數(shù)目的最大值
     bool visited[MaxVertexNum];  // 訪問(wèn)標(biāo)記數(shù)組
     vector<int> G[MaxVertexNum];  // 鄰接表
     int N;  // 節(jié)點(diǎn)個(gè)數(shù)
     
     // 對(duì)圖G進(jìn)行深度優(yōu)先遍歷，訪問(wèn)函數(shù)為visit()
     void DFSTraverse(){
     	for (int v=0; v<N; v++)  // 初始化
     		visited[v] = false;
     	for (int v=0; v<N; v++){
     		if (!visited[v])
     			DFS(v);
     	}
     }
     
     void DFS(int v){
     	visit(v);  // 訪問(wèn)節(jié)點(diǎn)v
     	visited[v] = true;  // 設(shè)訪問(wèn)標(biāo)記為真
     	for (int w:G[v])
     		if (!visited[w])  // w為u的尚未訪問(wèn)的鄰接節(jié)點(diǎn)
     			DFS(w);
     }
     

   • BFS實(shí)現(xiàn)（要用到隊(duì)列）

     #include <iostream>
     #include <queue>
     #include <vector>
     using namespace std;
     #define MaxVertexNum 100
     
     vector<int> graph[MaxVertexNum];
     bool visited[MaxVertexNum];
     
     void BFS(int start){
     	queue<int> q;
     	q.push(start);  // 將起點(diǎn)push進(jìn)隊(duì)列
     	visited[start] = true;  // 標(biāo)記起點(diǎn)已被訪問(wèn)
     
     	while (!q.empty()){   // 當(dāng)隊(duì)列不空時(shí)進(jìn)行循環(huán) 
     		int currNode = q.front();
     		q.pop();
     
     		visit(currNode);
     		for (auto adjNode : graph[currNode]){
     			if (!visited[adjNode]){
     				visited[adjNode] = true;
     				q.push(adjNode);  // 將未被訪問(wèn)的相鄰節(jié)點(diǎn)加入隊(duì)列中
     			}
     		}
     	}
     }
     

2. 最小生成樹(shù)
   • Prim算法（ACE：不要求記憶）
   • Kruskal算法（ACE：不要求掌握，理解并查集在Kruskal中的作用即可）
3. 最短路徑
   • Dijkstra算法
   • Floyd算法
4. 拓?fù)渑判蛩惴ǎˋCE：?？歼x擇題）
5. 關(guān)鍵路徑算法 （ACE：?？歼x擇題）
6. 并查集

三、一些題目

1）無(wú)向圖
2）

typedef struct{
	unsigned int ID, IP;
} LinkNode;

typedef struct{
	unsigned int Prefix, Mask;
} NetNode;

typedef struct ArcNode{
	int Flag;  // Flag=1為L(zhǎng)ink, Flag=2為Net
	union{
		LinkNode Lnode;
		NetNode Nnode;
	} LinkORNet;
	unsigned int Metric;
	struct ArcNode *next;
} ArcNode; 

typedef struct HNode{
	unsigned int RouterID;
	ArcNode *LN_link;
	sturct HNode *next;
}HNode; // 表頭節(jié)點(diǎn)

3）文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-631606.html

到了這里，關(guān)于第七章 圖論的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！