【数据结构】图论算法笔记整理

图的遍历

  • 有两种存储方式:邻接矩阵和邻接表
  • 在一些顶点数目比较大(一般顶点个数在1000以上)的情况下,使用邻接表而不是邻接矩阵来存储图。如果是稀疏图,用邻接表,如果是稠密图,用邻接矩阵。

深度优先搜索dfs遍历图

  • 按深度优先的方式访问所有未被访问的结点,在结点被访问过后标记为已访问

广度优先搜索bfs遍历图

  • 建立一个队列,把初始定点加入队列,然后每次都取出队首元素进行访问,并把该定点除法可以到达的未曾加入过队列(而不是未访问)的定点全部加入队列,直到队列为空

最短路径

  • 单源最短路径:计算源点到其他各顶点的最短路径的长度
  • 全局最短路径:图中任意两点的最短路径
  • Dijkstra、Bellman-Ford、SPFA求单源最短路径
  • Floyed可以求全局最短路径,但是效率比较低
  • SPFA算法是Bellman-Ford算法的队列优化
  • Dijkstra算法不能求带负权边的最短路径,而SPFA算法、Bellman-Ford算法、Floyd-Warshall可以求带负权边的最短路径。
  • Bellman-Ford算法的核心代码只有4行,Floyd-Warshall算法的核心代码只有5行。
  • 深度优先遍历可以求一个点到另一个点的最短路径的长度

Dijkstra算法

  • 三种附加考法:第一标尺是距离,如果距离相等的时候,新增第二标尺
    • 新增边权(第二标尺),要求在最短路径有多条时要求路径上的花费之和最小

    • 给定每个点的点权(第二标尺),要求在最短路径上有多条时要求路径上的点权之和最大

    • 直接问有多少条最短路径

    增加一个数组num[],num[s] = 1,其余num[u] = 0,表示从起点s到达顶点u的最短路径的条数为num[u]

  • 例子:比如说又要路径最短,又要点权权值最大,而且还要输出个数,而且还要输出路径

  • of course, 可以不用这么麻烦,用Dijkstra求最短路径和pre数组,然后用深度优先遍历来获取想知道的一切,包括点权最大,边权最大,路径个数,路径
  • 因为可能有多条路径,所以Dijkstra部分的pre数组使用vector<int> pre[maxv];
  • 既然已经求得pre数组,就知道了所有的最短路径,然后要做的就是用dfs遍历所有最短路径,找出一条使第二标尺最优的路径
  • 解释:
    • 对于递归边界而言,如果当前访问的结点是叶子结点(就是路径的开始结点),那么说明到达了递归边界,把v压入temppath,temppath里面就保存了一条完整的路径。如果计算得到的当前的value大于最大值,就path = temppath,然后把temppath的最后一个结点弹出,return ;
    • 对于递归式而言,每一次都是把当前访问的结点压入,然后找他的pre[v][i],进行递归,递归完毕后弹出最后一个结点
  • 计算当前temppath边权或者点权之和的代码:
  • 计算路径直接在Dijkstra部分写就可以
  • 例子:计算最短距离的路径和最小花费
  • 关于初始化:除了weight和cost(点权和边权)都要初始化,pre初始化为它自己本身,e和dis初始化为inf,visit因为开了全局变量,自动初始化为了false。在dijkstra循环开始之前,要把dis[start] = 0;

L3-007. 天梯地图-PAT团体程序设计天梯赛GPLT

L3-007. 天梯地图
本题要求你实现一个天梯赛专属在线地图,队员输入自己学校所在地和赛场地点后,该地图应该推荐两条路线:一条是最快到达路线;一条是最短距离的路线。题目保证对任意的查询请求,地图上都至少存在一条可达路线。

输入格式:

输入在第一行给出两个正整数N(2 <= N <=500)和M,分别为地图中所有标记地点的个数和连接地点的道路条数。随后M行,每行按如下格式给出一条道路的信息:

V1 V2 one-way length time

其中V1和V2是道路的两个端点的编号(从0到N-1);如果该道路是从V1到V2的单行线,则one-way为1,否则为0;length是道路的长度;time是通过该路所需要的时间。最后给出一对起点和终点的编号。

输出格式:

首先按下列格式输出最快到达的时间T和用节点编号表示的路线:

Time = T: 起点 => 节点1 => … => 终点

然后在下一行按下列格式输出最短距离D和用节点编号表示的路线:

Distance = D: 起点 => 节点1 => … => 终点

如果最快到达路线不唯一,则输出几条最快路线中最短的那条,题目保证这条路线是唯一的。而如果最短距离的路线不唯一,则输出途径节点数最少的那条,题目保证这条路线是唯一的。

如果这两条路线是完全一样的,则按下列格式输出:

Time = T; Distance = D: 起点 => 节点1 => … => 终点

输入样例1:
10 15
0 1 0 1 1
8 0 0 1 1
4 8 1 1 1
5 4 0 2 3
5 9 1 1 4
0 6 0 1 1
7 3 1 1 2
8 3 1 1 2
2 5 0 2 2
2 1 1 1 1
1 5 0 1 3
1 4 0 1 1
9 7 1 1 3
3 1 0 2 5
6 3 1 2 1
5 3
输出样例1:
Time = 6: 5 => 4 => 8 => 3
Distance = 3: 5 => 1 => 3
输入样例2:
7 9
0 4 1 1 1
1 6 1 3 1
2 6 1 1 1
2 5 1 2 2
3 0 0 1 1
3 1 1 3 1
3 2 1 2 1
4 5 0 2 2
6 5 1 2 1
3 5
输出样例2:
Time = 3; Distance = 4: 3 => 2 => 5

分析:用两个Dijkstra + DFS。一个求最快路径(如果相同求路径的那条),一个求最短路径(如果相同求结点数最小的那条)~~~求最快路径可以直接在Dijkstra里面求前驱结点Timepre数组~~~求最短路径因为要求结点数最小的那条,所以要用dispre的二维数组存储所有结点的最短路径,然后用DFS求出满足条件的结点数最小的那条~~~~
注意:
1.一开始最后一个测试用例“答案错误”,后来发现是自己在求最短路径(第二个答案distance)的时候忘记了temppath每一次深搜结束后的pop_back();
2.如果直接使用DFS的话,会导致最后一个测试用例“运行超时”~~~

 

1111. Online Map (30)-PAT甲级真题(Dijkstra + DFS)

1111. Online Map (30)
Input our current position and a destination, an online map can recommend several paths. Now your job is to recommend two paths to your user: one is the shortest, and the other is the fastest. It is guaranteed that a path exists for any request.

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers N (2 <= N <= 500), and M, being the total number of streets intersections on a map, and the number of streets, respectively. Then M lines follow, each describes a street in the format:

V1 V2 one-way length time

where V1 and V2 are the indices (from 0 to N-1) of the two ends of the street; one-way is 1 if the street is one-way from V1 to V2, or 0 if not; length is the length of the street; and time is the time taken to pass the street.

Finally a pair of source and destination is given.

Output Specification:

For each case, first print the shortest path from the source to the destination with distance D in the format:

Distance = D: source -> v1 -> … -> destination

Then in the next line print the fastest path with total time T:

Time = T: source -> w1 -> … -> destination

In case the shortest path is not unique, output the fastest one among the shortest paths, which is guaranteed to be unique. In case the fastest path is not unique, output the one that passes through the fewest intersections, which is guaranteed to be unique.

In case the shortest and the fastest paths are identical, print them in one line in the format:

Distance = D; Time = T: source -> u1 -> … -> destination

Sample Input 1:
10 15
0 1 0 1 1
8 0 0 1 1
4 8 1 1 1
3 4 0 3 2
3 9 1 4 1
0 6 0 1 1
7 5 1 2 1
8 5 1 2 1
2 3 0 2 2
2 1 1 1 1
1 3 0 3 1
1 4 0 1 1
9 7 1 3 1
5 1 0 5 2
6 5 1 1 2
3 5
Sample Output 1:
Distance = 6: 3 -> 4 -> 8 -> 5
Time = 3: 3 -> 1 -> 5
Sample Input 2:
7 9
0 4 1 1 1
1 6 1 1 3
2 6 1 1 1
2 5 1 2 2
3 0 0 1 1
3 1 1 1 3
3 2 1 1 2
4 5 0 2 2
6 5 1 1 2
3 5
Sample Output 2:
Distance = 3; Time = 4: 3 -> 2 -> 5

题目大意:给一张地图,两个结点中既有距离也有时间,有的单行有的双向,要求根据地图推荐两条路线:一条是最快到达路线,一条是最短距离的路线。
第一行给出两个整数N和M,表示地图中地点的个数和路径的条数。接下来的M行每一行给出:道路结点编号V1 道路结点编号V2 是否单行线 道路长度 所需时间
要求第一行输出最快到达时间Time和路径,第二行输出最短距离Distance和路径

分析:用两个Dijkstra + DFS。一个求最短路径(如果相同求时间最短的那条),一个求最快路径(如果相同求结点数最小的那条)~~~求最短路径可以直接在Dijkstra里面求前驱结点pre数组~~~求最快路径因为要求结点数最小的那条,所以要用pre的二维数组存储所有结点的最快路径,然后用DFS求出满足条件的结点数最小的那条~~~~
注意:
1.一开始最后一个测试用例“答案错误”,后来发现是自己在求最快路径的时候忘记了temppath每一次深搜结束后的pop_back();
2.如果直接使用DFS的话,会导致最后一个测试用例“运行超时”~~~

 

1087. All Roads Lead to Rome (30)-PAT甲级真题(Dijkstra + DFS)

1087. All Roads Lead to Rome (30)
Indeed there are many different tourist routes from our city to Rome. You are supposed to find your clients the route with the least cost while gaining the most happiness.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive integers N (2<=N<=200), the number of cities, and K, the total number of routes between pairs of cities; followed by the name of the starting city. The next N-1 lines each gives the name of a city and an integer that represents the happiness one can gain from that city, except the starting city. Then K lines follow, each describes a route between two cities in the format “City1 City2 Cost”. Here the name of a city is a string of 3 capital English letters, and the destination is always ROM which represents Rome.

Output Specification:

For each test case, we are supposed to find the route with the least cost. If such a route is not unique, the one with the maximum happiness will be recommended. If such a route is still not unique, then we output the one with the maximum average happiness — it is guaranteed by the judge that such a solution exists and is unique.

Hence in the first line of output, you must print 4 numbers: the number of different routes with the least cost, the cost, the happiness, and the average happiness (take the integer part only) of the recommended route. Then in the next line, you are supposed to print the route in the format “City1->City2->…->ROM”.

Sample Input:
6 7 HZH
ROM 100
PKN 40
GDN 55
PRS 95
BLN 80
ROM GDN 1
BLN ROM 1
HZH PKN 1
PRS ROM 2
BLN HZH 2
PKN GDN 1
HZH PRS 1
Sample Output:
3 3 195 97
HZH->PRS->ROM

题目大意:有N个城市,M条无向边,从某个给定的起始城市出发,前往名为ROM的城市。每个城市(除了起始城市)都有一个点权(称为幸福值),和边权(每条边所需的花费)。求从起点到ROM所需要的最少花费,并输出其路径。如果路径有多条,给出幸福值最大的那条。如果仍然不唯一,选择路径上的城市平均幸福值最大的那条路径。

分析:Dijkstra+DFS。Dijkstra算出所有最短路径的路线pre二维数组,DFS求最大happiness的路径path,并求出路径条数,最大happiness,最大average。
注意:average是除去起点的average。城市名称可以用m存储字符串所对应的数字,用m2存储数字对应的字符串。

 

LeetCode上Tag为深度优先搜索(Depth-frist Search)的题目整理

101. Symmetric Tree
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:
1
/ \
2 2
/ \ / \
3 4 4 3
But the following is not:
1
/ \
2 2
\ \
3 3
Note:
Bonus points if you could solve it both recursively and iteratively.
分析:这道题既可以用深度优先搜索DFS,也可以用广度优先搜索BFS。深度优先搜索的思路为:
传入root的左子树和右子树。如果两个都为NULL,则是对称的。如果两边都不为NULL并且两边的所对应的val相等,那就判断root->left->left和root->left->right是否对称,且判断root->left->right和root->right->left是否对称。。。
其余情况下return false;

257. Binary Tree Paths
Given a binary tree, return all root-to-leaf paths.
For example, given the following binary tree:

1
/ \
2 3
\
5
All root-to-leaf paths are:
[“1->2->5”, “1->3”]
分析:典型的深度优先搜索,dfs函数思路为:
dfs函数中参数传入一个string,该String将每次结点的值连接起来,直到递归出口的时候返回;
当该结点有左孩子的时候,将左孩子的值连接到字符串尾部;
当该结点有右孩子的时候,将右孩子的值连接到字符串尾部;
当该结点无左右孩子的时候,将字符串push入数组后return;

100. Same Tree
Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
分析:递归函数每次传入两棵树中的各一个结点。先传入两个树的root结点。若root结点均不为空,则判断这两个结点的值是否相等,和这两个结点的左孩子、右孩子是否相等~如果都满足则return true,否则return false~若传入的结点不是都不空的,判断是否同时都空~如果一个空一个不空那么是false~所以最后要加上一句return p == NULL && q == NULL;~~~~

104. Maximum Depth of Binary Tree
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
分析:分类讨论,设当前结点为root,如果root->left 和 root->right都为NULL,则返回1;
如果root->left不为NULL但是root->right为NULL,返回root->left为根节点的子树的最大层数+1;
如果root->right不为NULL但是root->left为NULL,返回root->right为根节点的子树的最大层数+1;
如果root->right和root->right都不为NULL,则返回以root->left为根节点的子树的层数和以root->right为根节点的子树的层数中的较大的那个值+1。

110. Balanced Binary Tree
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
分析:判断一棵二叉树是否为平衡二叉树~设当前结点为root,设两个变量l和r分别表示以root为根节点的子树的左边的高度和右边的高度。如果root结点没有左孩子,那么l = 0;否则l = dfs(root->left);如果root结点没有右孩子,那么r = 0;否则r = dfs(root->right);以root为根节点的子树的高度为它的左边的高度l和右边的高度r两个中较大的那一个+1;当root根节点为空的时候,说明它的父结点的高度为1。如果l和r的绝对值大于等于2则返回false(在这里将标志flag置为0)。

111. Minimum Depth of Binary Tree
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
分析:这道题即可以用深度优先,又可以用广度优先来做。这里用深度优先:
分析:分类讨论,设当前结点为root,如果root->left 和 root->right都为NULL,则返回1;
如果root->left不为NULL但是root->right为NULL,返回root->left为根节点的子树的最小层数+1;
如果root->right不为NULL但是root->left为NULL,返回root->right为根节点的子树的最小层数+1;
如果root->right和root->right都不为NULL,则返回以root->left为根节点的子树的层数和以root->right为根节点的子树的层数中的较小的那个值+1。

112. Path Sum
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
分析:如果当前结点root没有左孩子left并且没有右孩子right,并且sum == root->val则return true;否则的话将root的左孩子left和sum-root->val的剩余需要的值传入函数作为参数进一步检验~如果当前root == NULL 则return false;说明没有达到该路径和为sum的要求。

还有几道深度优先:

POJ 1321-棋盘问题-简单搜索
在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放k个棋子的所有可行的摆放方案C。
Input 输入含有多组测试数据。
每组数据的第一行是两个正整数,n k,用一个空格隔开,表示了将在一个n*n的矩阵内描述棋盘,以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状:每行有n个字符,其中 # 表示棋盘区域, . 表示空白区域(数据保证不出现多余的空白行或者空白列)。
Output

对于每一组数据,给出一行输出,输出摆放的方案数目C (数据保证C<2^31)。
Sample Input

2 1
#.
.#
4 4
…#
..#.
.#..
#…
-1 -1
Sample Output

2
1

POJ 1426-Find The Multiple-深度优先搜索dfs
Description
Given a positive integer n, write a program to find out a nonzero multiple m of n whose decimal representation contains only the digits 0 and 1. You may assume that n is not greater than 200 and there is a corresponding m containing no more than 100 decimal digits.
Input
The input file may contain multiple test cases. Each line contains a value of n (1 <= n <= 200). A line containing a zero terminates the input.
Output
For each value of n in the input print a line containing the corresponding value of m. The decimal representation of m must not contain more than 100 digits. If there are multiple solutions for a given value of n, any one of them is acceptable.
Sample Input
2
6
19
0
Sample Output
10
100100100100100100
111111111111111111

POJ-2488 A Knights Journey-深度优先搜索
The knight is getting bored of seeing the same black and white squares again and again and has decided to make a journey
around the world. Whenever a knight moves, it is two squares in one direction and one square perpendicular to this. The world of a knight is the chessboard he is living on. Our knight lives on a chessboard that has a smaller area than a regular 8 * 8 board, but it is still rectangular. Can you help this adventurous knight to make travel plans?

Problem
Find a path such that the knight visits every square once. The knight can start and end on any square of the board.
Input

The input begins with a positive integer n in the first line. The following lines contain n test cases. Each test case consists of a single line with two positive integers p and q, such that 1 <= p * q <= 26. This represents a p * q chessboard, where p describes how many different square numbers 1, . . . , p exist, q describes how many different square letters exist. These are the first q letters of the Latin alphabet: A, . . .
Output

The output for every scenario begins with a line containing “Scenario #i:”, where i is the number of the scenario starting at 1. Then print a single line containing the lexicographically first path that visits all squares of the chessboard with knight moves followed by an empty line. The path should be given on a single line by concatenating the names of the visited squares. Each square name consists of a capital letter followed by a number.
If no such path exist, you should output impossible on a single line.
Sample Input

3
1 1
2 3
4 3
Sample Output
Scenario #1:
A1
Scenario #2:
impossible
Scenario #3:
A1B3C1A2B4C2A3B1C3A4B2C4
Source
TUD Programming Contest 2005, Darmstadt, Germany

4.1 深度优先搜索
全排列 123456789 数字,输出第n个

4.1深度优先搜索-xxx + xxx = xxx