文章目录
- 前言
- 图的定义
- 图的遍历
- 深度优先搜索（dfs）
- 广度优先搜索
- 拓扑排序
- 检测有向图中的环
- 最短路径（Dijkstra）
前言
这个数据结构很繁琐，说实话我不喜欢。但是不学吧，总觉得我在数据结构这一块有个大漏洞。
在网上各处搜罗，看了大家对于面试会问到的有关图的内容，想了想，就先整理那部分吧。
图的定义
图的遍历
深度优先搜索（dfs）
所谓的深度优先搜索，指的是在搜索时，如果遇到一个结点既有子结点，又有兄弟结点，那么先找子结点，然后找兄弟结点。
很明显，在由于边是没有方向的，所以，如果4和5顶点相连，那么4会出现在5的相邻链表中，5也会出现在4的相
邻链表中，那么为了不对顶点进行重复搜索，应该要有相应的标记来表示当前顶点有没有搜索过，可以使用一个布
尔类型的数组 boolean[V] marked,索引代表顶点，值代表当前顶点是否已经搜索，如果已经搜索，标记为true，
如果没有搜索，标记为false；
public class DepthFirstSearch {
//索引代表顶点，值表示当前顶点是否已经被搜索
private boolean[] marked;
//记录有多少个顶点与s顶点相通
private int count;
//构造深度优先搜索对象，使用深度优先搜索找出G图中s顶点的所有相邻顶点
public DepthFirstSearch(Graph G,int s){
//创建一个和图的顶点数一样大小的布尔数组
marked = new boolean[G.V()];
//搜索G图中与顶点s相同的所有顶点 dfs(G,s);
}
//使用深度优先搜索找出G图中v顶点的所有相邻顶点
private void dfs(Graph G, int v){
//把当前顶点标记为已搜索
marked[v]=true;
//遍历v顶点的邻接表，得到每一个顶点w
for (Integer w : G.adj(v)){
//如果当前顶点w没有被搜索过，则递归搜索与w顶点相通的其他顶点
if (!marked[w]){
dfs(G,w);
}
}
//相通的顶点数量+1
count++;
}
//判断w顶点与s顶点是否相通
public boolean marked(int w){ return marked[w]; }
//获取与顶点s相通的所有顶点的总数 4
public int count(){ return count; }
}
广度优先搜索
所谓的深度优先搜索，指的是在搜索时，如果遇到一个结点既有子结点，又有兄弟结点，那么先找兄弟结点，然后
找子结点。
public class BreadthFirstSearch {
//索引代表顶点，值表示当前顶点是否已经被搜索
private boolean[] marked;
//记录有多少个顶点与s顶点相通
private int count;
//用来存储待搜索邻接表的点
private Queue<Integer> waitSearch;
//构造广度优先搜索对象，使用广度优先搜索找出G图中s顶点的所有相邻顶点
public BreadthFirstSearch(Graph G, int s) {
//创建一个和图的顶点数一样大小的布尔数组
marked = new boolean[G.V()];
//初始化待搜索顶点的队列
waitSearch = new Queue<Integer>();
//搜索G图中与顶点s相同的所有顶点
dfs(G, s);
}
//使用广度优先搜索找出G图中v顶点的所有相邻顶点
private void dfs(Graph G, int v) {
//把当前顶点v标记为已搜索
marked[v]=true;
//把当前顶点v放入到队列中，等待搜索它的邻接表
waitSearch.enqueue(v);
//使用while循环从队列中拿出待搜索的顶点wait，进行搜索邻接表
while(!waitSearch.isEmpty()){
Integer wait = waitSearch.dequeue();
//遍历wait顶点的邻接表，得到每一个顶点w
for (Integer w : G.adj(wait)) {
//如果当前顶点w没有被搜索过，则递归搜索与w顶点相通的其他顶点
if (!marked[w]) {
dfs(G, w);
}
}
}
//相通的顶点数量+1
count++;
}
//判断w顶点与s顶点是否相通
public boolean marked(int w) {
return marked[w];
}
//获取与顶点s相通的所有顶点的总数
public int count() {
return count;
}
}
拓扑排序
给定一副有向图，将所有的顶点排序，使得所有的有向边均从排在前面的元素指向排在后面的元素，此时就可以明
确的表示出每个顶点的优先级。
class Graph {
int V; // 顶点的个数
list<int> *adj; // 所有顶点的起始指针
};
void topologicalSort(int V, list<int> *adj) {
// 计算所有入度
vector<int> in_degree(V, 0);
for (int u=0; u<V; u++) {
list<int>::iterator itr;
for (itr = adj[u].begin(); itr != adj[u].end(); itr++) {
in_degree[*itr]++;
}
}
// 加入入度为0的点
queue<int> q;
for (int i = 0; i < V; i++) {
if (in_degree[i] == 0) q.push(i);
}
int cnt = 0;
vector <int> top_order;
while (!q.empty()) {
int u = q.front();
q.pop();
top_order.push_back(u);
// 所有连接点, 入度减去1
list<int>::iterator itr;
for (itr = adj[u].begin(); itr != adj[u].end(); itr++) {
if (--in_degree[*itr] == 0) q.push(*itr);
}
cnt++;
}
if (cnt != V) {
cout << "There exists a cycle in the graph\n";
return;
}
for (int i=0; i<top_order.size(); i++)
cout << top_order[i] << " ";
cout << endl;
}
检测有向图中的环
如果我们要使用拓扑排序解决优先级问题，首先得保证图中没有环的存在。
bool isCyclicGraph(vector<int> &start, vector<int> &end) {
// 找到最大顶点值,构造图,
int n = 0;
for (int s : start) {
n = max(n, s);
}
for (int e : end) {
n = max(n, e);
}
// 构造图
vector<vector<int>> graph(n + 1);
vector<int> d(n + 1);
int m = start.size();
// 计算所有顶点的入度
for (int i = 0; i < m; i++) {
graph[start[i]].push_back(end[i]);
d[end[i]]++;
}
queue<int> que;
// 将所有入度为0的点,加入队列
for (int i = 1; i <= n; i++) {
if (graph[i].size() && !d[i]) {
que.push(i);
}
}
while (!que.empty()) {
int h = que.front();
que.pop();
// 将多有入度为0的点,对应的顶点 入度减去1
for (int y : graph[h]) {
d[y]--;
if (!d[y]) {
que.push(y);
}
}
}
// 判断是否所有顶点的入度都是0, 如果是,则没有环,否则就有
for (int i = 1; i <= n; i++) {
if (d[i]) {
return true;
}
}
return false;
}
最短路径（Dijkstra）
- 维护一个最短路径的的集合(sptSet)和最短距离数组, 直到遍历所有的点, 初始化起始点的距离是0, 集合为空.
- 初始化起始点s到所有的点的距离是INF, 注意s到s的距离是0.
- 、while sptSet 不包含所有的顶点:
1. 选择当前能到达点的最小距离的点u,加入 sptSet
2. 使用u作为中间顶点,更新所有点的距离,选择最小距离的替换
3. dist[u]+graph[u][v] < dist[v]
int minDistance(vector<int> dist, set<int> sptSet) {
int min_d = INT_MAX, u;
for(int i = 0, i < dist.size(); i ++) {
if(sptSet.find(i) == sptSet.end() && dist[v] < min_d) {
min_d = dist[i], u = i;
}
}
return u;
}
// 使用vector 表示的邻接矩阵, return 起始点到所有点的最小距离
// 没有边的用0填充
vector<int> dijstra(vector<vector<int>> graph, set<int> &sptSet,int src) {
int V = graph.size();
vector<int> dist(V, 0);
for(int i = 0;i < V; i ++) {
if(i != src) dist[i] = INT_MAX;
}
while(sptSet.size() < V-1) {
// pick mininum distance u
int u = minDistance(dist, sptSet);
sptSet.insert(u);
// 使用u更新距离
for(int v = 0; v < V; v ++) {
if(sptSet.find(v)==sptSet.end() && graph[u][v]
&& dist[u] != INT_MAX
&& dist[u]+graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
return dist;
}
