第七章图论-Toy模板网

这篇具有很好参考价值的文章主要介绍了第七章图论。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

第七章图论

一、数据结构定义

图的邻接矩阵存储法

#define MaxVertexNum 100 // 节点数目的最大值

// 无边权，只用0或1表示边是否存在
bool graph[MaxVertexNum][MaxVertexNum];

// 有边权
int graph[MaxVertexNum][MaxVertexNum];

图的邻接表存储法
把所有节点存储为节点数组，每个节点里有自己的数据和一个边指针，这个边指针相当于一个链表的头指针，这个链表里存放所有与这个节点相连的边，边里存放该边指向的节点编号和下一条边指针
第七章图论,数据结构代码相关,图论

#define MaxVertexNum 100 // 节点数目的最大值
typedef struct EdgeNode{ // 边表节点
	int adjvex; // 该边所指向的节点编号
	struct EdgeNode *next; // 指向下一条边的指针
	// Infotype info; // 边权值（如果有）
}EdgeNode;

typedef struct VNode{ //节点表节点
	VertexType data; // 节点信息
	EdgeNode *first; // 指向第一条依附该节点的边的指针
}VNode;

typedef struct{
	int verNum, edgeNum; // 节点数和边数
	VNode AdjList[MaxVertexNum]; // 节点数组
} ALGraph; // 邻接表

图的十字链表存储法（有向图）

分为弧节点和顶点节点。一个弧指向两个弧（是它的两个下一接替者），一个顶点指向两个弧（都是它的第一任）
此外，十字链表还可用于存储稀疏矩阵，矩阵的各行各列都各用一个链表存储，同时将所有行链表的表头rhead存储到一个数组，所有列链表的表头存储到另一个数组chead中。
可以将十字链表记忆为串起来的三元组，即一个边节点记为（行，value，列）（即（弧尾，权值，弧头）），多个三元组的行和列分别串成一个链表，代表相同行的元素以及相同列的元素（即弧尾相同和弧头相同的元素）
```
typedef struct edgeNode{
	int headVer, tailVer; 
	struct edgeNode *hLink, *tLink; // 分别指向弧头和弧尾相同的下一条边
	infoType info;
} edgeNode;

typedef struct VNode{
	VerType data;
	edgeNode *firstIn, *firstOut; // 分别指向入边表和出边表中的第一个边节点
} VNode;

typedef struct{
	int verNum, edgeNum;
	VNode XList[verNum]; // 顶点表
} OLGraph;
```

图的邻接多重表存储法（无向图）
第七章图论,数据结构代码相关,图论

typedef struct edgeNode{
	int iVer, jVer; // 边的两个顶点在顶点表（数组）里的下标
	struct edgeNode *iLink, *jLink; // 和顶点相连的下一条边
	infoType info; // 带权图可存储边的权值
} edgeNode;

typedef struct VNode{
	VerType data;
	edgeNode *firstEdge;
} VNode;

typedef struct{
	int verNum, edgeNum; // 图的顶点数和边数
	VNode adjMuList[verNum];
} AMLGraph;

二、代码/算法

遍历/搜索

DFS实现

#define MaxVertexNum 100  // 图中节点数目的最大值
bool visited[MaxVertexNum];  // 访问标记数组
vector<int> G[MaxVertexNum];  // 邻接表
int N;  // 节点个数

// 对图G进行深度优先遍历，访问函数为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);  // 访问节点v
	visited[v] = true;  // 设访问标记为真
	for (int w:G[v])
		if (!visited[w])  // w为u的尚未访问的邻接节点
			DFS(w);
}

BFS实现（要用到队列）

#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);  // 将起点push进队列
	visited[start] = true;  // 标记起点已被访问

	while (!q.empty()){   // 当队列不空时进行循环 
		int currNode = q.front();
		q.pop();

		visit(currNode);
		for (auto adjNode : graph[currNode]){
			if (!visited[adjNode]){
				visited[adjNode] = true;
				q.push(adjNode);  // 将未被访问的相邻节点加入队列中
			}
		}
	}
}

最小生成树
- Prim算法（ACE：不要求记忆）
- Kruskal算法（ACE：不要求掌握，理解并查集在Kruskal中的作用即可）
最短路径
- Dijkstra算法
- Floyd算法
拓扑排序算法（ACE：常考选择题）
~~关键路径算法~~ （ACE：常考选择题）
并查集

三、一些题目

第七章图论,数据结构代码相关,图论
1）无向图
2）

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

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

typedef struct ArcNode{
	int Flag;  // Flag=1为Link, 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; // 表头节点