《算法笔记》 第十章 提高篇（4）--- 图算法专题

图的存储：
①邻接矩阵
用一个二维数组来存放，不适合存放过多顶点（一般不超过1000）
②邻接表
可以用vector来存放邻接表
vector Adj[N];

以结构体存储节点

struct Node{
	int v,w;
	Node(int _v,int _w): v(_v),w(_w) { }//h构造函数 
};

Adj[1].push_back(Node(3,4));

图的访问：
DFS+邻接矩阵

#include 
#include 
using namespace std;
int n=0;
int maze[101][101]={0};
bool visited[101]={false};

void DFS(int u)
{
	visited[u]=true;
	cout<<"访问节点"< 
BFS+邻接矩阵
 
#include 
#include 
#include 
using namespace std;
int n=0;
int maze[101][101]={0};
bool visited[101]={false};

void BFS(int t)
{
	queue q;
	q.push(t);
	visited[t]=true;
	while(!q.empty())
	{
		int now=q.front();
		q.pop();
		printf("访问%d节点n",now);
		for(int i=0;i 
迪杰斯特拉算法：
 
#define MAXV 1000
#define INF 9999
using namespace std;
int n,G[MAXV][MAXV];
int d[MAXV];
bool vis[MAXV]={false};

void Dijkstra(int s)
{
	fill(d,d+MAXV,INF);
	d[s]=0;
	for(int i=0;i 
利用迪杰斯特拉算法求最短路径：
 
#define MAXV 1000
#define INF 9999
using namespace std;
int n,G[MAXV][MAXV];
int d[MAXV];
int pre[MAXV];
bool vis[MAXV]={false};

void Dijkstra(int s)
{
	fill(d,d+MAXV,INF);
	d[s]=0;
	for(int i=0;i 
考试中更多的会出现另一种情况，即从起点到终点最短距离最小的路不止一条，一般题目会给出一个第二标尺（一般第一标尺是距离，在第一标尺无法判断的情况下（距离相等），依靠第二标志来选择路径），常见的第二标尺有：
 ①给每条边再增加一个边权（比如说花费），然后要求在最短路径有多条时要求路径上的花费之和最小（如果边权是其他含义，也可以是最大）
 多了cost【】【】边权数组，c[]记录最小值边权数组
 初始化时，c[s]=0,其余都为INF
 
#define MAXV 1000
#define INF 9999
using namespace std;
int n,G[MAXV][MAXV],cost[MAXV][MAXV];
int d[MAXV];
int c[MAXV];
bool vis[MAXV]={false};

void Dijkstra(int s)
{
	fill(d,d+MAXV,INF);
	d[s]=0;
	for(int i=0;i 
②给每个点再增加一个点权（例如每个城市能收集到的物资或是该城市所对应字母的字母序），然后在最短路径有多条时要求路径上点权之和最大（如果点权是其他含义，也可以是最小）
 多了weight[]点权数组，w[]记录最大值点权数组
 初始化时，w[s]=weight[s],其余w[]均为0
 
#define MAXV 1000
#define INF 9999
using namespace std;
int n,G[MAXV][MAXV],weight[MAXV];
int d[MAXV];
int w[MAXV];
bool vis[MAXV]={false};

void Dijkstra(int s)
{
	fill(d,d+MAXV,INF);
	d[s]=0;
	for(int i=0;iw[v])
				{
					w[v]=w[u]+weight[v];
				}	
			}
		}
	}
}
 
③直接问有多少条最短路径
 多了一个num[]数组
 初始化时，num[s]=1,其余的num[]都为0
 
#define MAXV 1000
#define INF 9999
using namespace std;
int n,G[MAXV][MAXV],weight[MAXV];
int d[MAXV];
int num[MAXV]; 
bool vis[MAXV]={false};

void Dijkstra(int s)
{
	fill(d,d+MAXV,INF);
	d[s]=0;
	for(int i=0;iw[v])
				{
					num[v]+=num[u];
				}	
			}
		}
	}
}
 
迪杰斯特拉算法和DFS结合求解
 迪杰斯特拉算法只能解决非负权值边的题目，如果出现了负值就需要使用SPFA算法。
 弗洛伊德算法，求任意两点之间最短路径长度问题，dis【i】【j】表示顶点i到j的最短距离
 
#include 
#include 
#include 
using namespace std;
const int INF = 100000000;
const int MAXV=200;
int n,m;
int dis[MAXV][MAXV]={INF};

void Floyd()
{
	for(int k=0;k 
prim算法
 
const int MAXV=1000;//最大定点数 
const int INF=10000000;//一个最大值 

int n,G[MAXV][MAXV];
int d[MAXV]={INF};
bool vis[MAXV]={false};

int prim()
{
	d[0]=0;
	int ans=0;
	for(int i=0;i 
kruskal算法利用并查集实现
 拓扑排序：
 用了邻接链表，还可以用来判断是否有向图有环
 如果要求有多个入度为零的点，选择编号最小的点，那么把queue改成priority_queue即可
 
const int MAXV=1000;//最大定点数 
const int INF=10000000;//一个最大值 

int n,m,inDegree[MAXV];
vector G[MAXV];//采用邻接表 

bool topologicalSort()
{
	int num=0;
	queue q;
	for(int i=0;i 
关键路径（动态规划）
 若需要求最长路径，则可以将边的所有边权全部乘-1，再利用SPFA算法求最短路径，所得结果取反即可