一、图介绍
1、定义
图由结点的有穷集合V和边的集合E组成。其中，结点也称为顶点。一对结点（x， y）称为边（edge），表示顶点x连接到顶点y。边可以包含权重/成本，显示从顶点x到y所需的成本。若两个顶点之前存在一条边，就表示这两个顶点具有相邻关系。
2、类型
（1）无向图
（2）有向图
3、表示方法
（1）邻接矩阵
邻接矩阵存储结构就是用矩阵表示图中各顶点之间的邻接关系，两个顶点有邻接关系，就记录为1，否则为0。
（2）邻接表
邻接表是图的一种顺序存储与链式存储相结合的存储方式。
4、遍历方法
（1）广度优先搜索
（2）深度优先搜索
二、面试常考的算法
1、实现深度优先搜索
题目：如下无向图，从节点A开始遍历，其深度优先搜索为：A B D E F C。
思路：深度优先搜索，创建visited数组，用于记录所有被访问过的顶点。
（1）从A出发，访问A。
（2）找出A的第一个没有被访问的邻接点，访问该点。以该顶点为新顶点，重复此步骤，直至刚访问过的顶点没有未被访问的邻接点为止。
（3）返回前一个访问过的仍有未被访问邻接点的顶点,继续访问该顶点的下一个未被访问邻接点。
（4）重复2,3步骤，直至所有顶点均被访问，搜索结束。
#include<iostream>
using namespace std;
#include<vector>
#include<set>
#include<unordered_set>
#include<map>
class Graph{
private:
map<char, vector<char>> graph; //创建图，graph记录图的节点及邻接关系
public:
void add_edge(char node, vector<char> neibors){
graph[node] = neibors;
}
void dfs_helper(char node, map<char, int>& visited){
visited[node] = 1;
cout << node << " ";
for(auto n: graph[node]){
// 判断当前节点的邻接节点有无被访问
if(visited[n] != 1)
dfs_helper(n, visited);
}
}
void dfs(char start_node){
map<char,int> visited; // visited数组用来记录所有被访问过的顶点，被访问过，就记为1
dfs_helper(start_node, visited);
}
};
int main(){
Graph graph;
graph.add_edge('A', {'B', 'C'});
graph.add_edge('B', {'A', 'D', 'E'});
graph.add_edge('C', {'A', 'F'});
graph.add_edge('D', {'B'});
graph.add_edge('E', {'B', 'F'});
graph.add_edge('F', {'C', 'E'});
graph.dfs('A');
}
2、实现广度优先搜索
题目：如下无向图，从节点A开始遍历，其广度优先搜索为：A B D C E，从节点B开始遍历，其广度优先搜索为：B A C D E。
思路：广度优先搜索，利用队列来实现。把访问到的顶点入队，再访问该顶点的所有相邻的顶点，等访问完了该顶点的邻接点，再出队顶点和其相邻的顶点，每出队一个，就入队该顶点的未访问过的邻接顶点，重复上述步骤，直到队列为空。
#include<iostream>
#include<queue>
#include<map>
using namespace std;
class Graph{
private:
map<char, vector<char>> graph; //创建图，graph记录图的节点及邻接关系
public:
void add_edge(char node, vector<char> neibors){
graph[node] = neibors;
}
// 层次（广度）遍历
void bfs(char node){
map<char, int> visited; // visited数组用来记录所有被访问过的顶点，被访问过，就记为1
queue<char> que;
que.push(node);
visited[node] = 1;
while(!que.empty()){
char temp = que.front(); //出队
que.pop();
cout << temp << " ";
node = temp; //记录出队的点
for(auto neibor: graph[node]){
if(visited[neibor] != 1)
que.push(neibor); //访问出队点的邻接点，并入队
visited[neibor] = 1; //已访问的顶点标记为1
}
}
}
};
int main(){
Graph graph;
graph.add_edge('A', {'B', 'D'});
graph.add_edge('B', {'A', 'C', 'D'});
graph.add_edge('C', {'B', 'D', 'E'});
graph.add_edge('D', {'A', 'B', 'C', 'E'});
graph.add_edge('E', {'C', 'D'});
graph.bfs('B');
}
3、利用拓扑排序判断图是否有环路。
题目：如下有向图，判断是否存在环路。如果不为树，输出其拓扑排序。
思路：通过BFS实现拓扑排序。
（1）首先计算每个节点的入度，将所有入度为0的节点放入队列中
（2）开始执行BFS，我们取队首的节点u，放入结果中；移除u的所有出边，即将u的所有相邻节点的入度减少1，判断如果某个相邻的节点v的入度变为0，就将v放入队列中。
（3）当BFS结束后，如果答案中包含的节点数和图中的节点数相等，那么就得到了图G的拓扑排序，否则说明图中存在环，不存在拓扑排序。
// 利用拓扑排序判断有向图是否存在回路
#include<iostream>
#include<map>
#include<vector>
#include<queue>
using namespace std;
class Graph{
private:
map<char, vector<char>> graph;
public:
void add_edge(char node, vector<char> neibors){
graph[node] = neibors;
}
// 广度优先搜索+队列判断
void has_cycle(){
map<char, int> indegree; //记录每个顶点的入度，默认为0
for(auto g: graph){
indegree[g.first] = 0;
}
//计算每个顶点的入度
for(auto g: graph){
char n = g.first;
for(auto nei: graph[n]){
indegree[nei] += 1;
}
}
// 1、将所有入度为0的顶点入队
queue<char> que;
for(auto in: indegree){
char c = in.first;
if(in.second == 0)
que.push(c);
}
// 2、开始执行BFS，每出队一个顶点，就将该顶点的所有边移除，
// 即将该顶点所有相邻节点的入度减1，如果某个相邻节点的入度变为0，就将该节点放入队列中
vector<char> tuopu;
while(!que.empty()){
char temp = que.front();
que.pop();
tuopu.push_back(temp);
for(auto neibor: graph[temp]){
indegree[neibor] -= 1;
if(indegree[neibor] == 0)
que.push(neibor);
}
}
// 3.判断拓扑排序结果里的顶点个数，如果和图的个数相等，则没有环
if(tuopu.size() == graph.size()){
cout << "该图没有环，为树" << endl << "拓扑排序为：";
for(auto t: tuopu){
cout << t << " ";
}
}
else
cout << "该图有环，不为树";
}
};
int main(){
// 没有环
Graph graph;
graph.add_edge('A', {'B', 'C'});
graph.add_edge('B',{});
graph.add_edge('C',{'D','E'});
graph.add_edge('D', {'B'});
graph.add_edge('E', {});
graph.has_cycle();
// 有环
Graph graph2;
graph2.add_edge('A', {'B', 'C'});
graph2.add_edge('B', {'C'});
graph2.add_edge('C',{'D','E'});
graph2.add_edge('D', {'B'});
graph2.add_edge('E', {});
graph2.has_cycle();
return 0;
}
4、计算图的边数
题目：给定如下无向图，输出该图的边数7。
思路：遍历图中的节点，若该节点的邻接节点没有被访问，则边数count+1。
#include<iostream>
#include<queue>
#include<map>
using namespace std;
class Graph{
private:
map<char, vector<char>> graph; //创建图，graph记录图的节点及邻接关系
public:
void add_edge(char node, vector<char> neibors){
graph[node] = neibors;
}
// 计算图的边数
void getNumsofEdge(){
map<char, int> visited; //记录节点是否访问
int count = 0;
// 遍历graph中的节点与邻接节点
for(auto g: graph){
char n = g.first;
for(auto neibor: graph[n]){
if(visited[neibor] != 1){
count += 1;
}
// 每遍历一个节点，就将该节点标记为1
visited[n] = 1;
}
}
cout << count;
}
};
int main(){
Graph graph;
graph.add_edge('A', {'B', 'D'});
graph.add_edge('B', {'A', 'C', 'D'});
graph.add_edge('C', {'B', 'D', 'E'});
graph.add_edge('D', {'A', 'B', 'C', 'E'});
graph.add_edge('E', {'C', 'D'});
graph.getNumsofEdge();
}
5、找到两个顶点之间的最短路径
题目：如下无向图，A到F的路径有A->B->C->E->F，A->B->C->F，A->D->E->F，输出最短路径A->D->E->F。
思路：广度优先搜索（BFS）+ 队列实现。
（1）准备queue和map，queue用于BFS，map<char, vector<char>>用于存储当前最短距离。
（2）BFS，将顶点node1入队，并向Map中添加键值对。
（3）当队列非空时，进行循环。现将队首元素x出队，当前路径等x的当前路径，然后遍历x的邻接节点，如果邻接点中的某个节点tmp不在map键值对中（相当于未访问过）， 就向Map中加入键值对<tmp，当前路径>，并将tmp入队，如果tmp为node2，就返回Map中tmp对应的路径。
#include<iostream>
#include<queue>
#include<map>
using namespace std;
class Graph{
private:
map<char, vector<char>> graph; //创建图，graph记录图的节点及邻接关系
public:
void add_edge(char node, vector<char> neibors){
graph[node] = neibors;
}
// 计算两个顶点的最短路径：A->B->D->F
vector<char> getShortPath(char node1, char node2){
map<char, vector<char>> ShortPath; //用于存储当前最短路径
queue<char> q; //用于广度优先搜索
// 如果求自身到自身的最短路径，返回node1->node2
if(node1 == node2){
return {node1, node2};
}
//否则将node1入队，并向map中加入键值对
q.push(node1);
ShortPath[node1] = {node1};
while(!q.empty()){
char temp = q.front();
q.pop();
vector<char> path = ShortPath[temp];
for(auto neibor: graph[temp]){
if(ShortPath.find(neibor) == ShortPath.end()){
// 如果邻接节点不在map中（相当于未访问过），就向map中加入键值对
ShortPath[neibor] = path;
ShortPath[neibor].push_back(neibor);
q.push(neibor);
if(neibor == node2)
return ShortPath[neibor];
}
}
}
return {};
}
};
int main(){
Graph graph;
graph.add_edge('A', {'B', 'D'});
graph.add_edge('B', {'A', 'C', 'D'});
graph.add_edge('C', {'B', 'D', 'E'});
graph.add_edge('D', {'A', 'B', 'C', 'E'});
graph.add_edge('E', {'C', 'D', 'F'});
graph.add_edge('F', {'C','E'});
vector<char> short_path = graph.getShortPath('A', 'F');
for(auto s: short_path){
cout << s;
}
}
