数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会科学
时尚学
法律学打印 C 语言程序中从 1 开始图的字典序最小 DFS。
将给定一个具有 N 个顶点和 M 条边的连通图。我们需要打印图中从 1 开始的字典序最小 DFS。
顶点应从 1 到 N 编号
示例
Input: N = 5 M =5 edge(1, 4, arr) edge(3, 4, arr) edge(5, 4, arr) edge(3, 2, arr) edge(1, 5, arr) edge(1, 2, arr) edge(3, 5, arr) edge(1, 3, arr) output: 1 2 3 4 5
不进行常规 DFS，首先对与每个顶点关联的边进行排序，以便每次只先挑选最小的边。排序后，只需执行常规 DFS，即可得到字典序最小的 DFS 遍历。
以下是算法在 C++ 中的实现。
算法
Start
Step 1 -> Declare Function void lexo(vector<int>* arr, int n)
Declare bool check[n + 1] = { 0 }
Loop For int i=0 and i<n and i++
Call sort(arr[i].begin(), arr[i].end())
Loop For int i = 1 and i < n and i++
IF !check[i]
Call graph(arr, i, n, check)
End
End
Step 2 -> declare Function void edge(int u, int v, vector<int>* arr)
Call ar[u].push_back(v)
Call ar[v].push_back(u)
Step 3 -> Declare function void graph(vector<int>* arr, int src, int n,bool* check) print src
Set check[src] = true
Loop for int i = 0 and i < arr[src].size() and i++
IF !check[arr[src][i]]
Call graph(arr, arr[src][i], n, check)
End
End
Step 4- > In main()
Declare int n = 5, m = 5
Use STL vector<int> arr[n + 1]
Call edges(1,4, arr)
Call edges(3,4, arr)....
Call lexo(arr, n)
Stop示例
#include <bits/stdc++.h>
using namespace std;
//for inserting an edge
void edge(int u, int v, vector<int>* arr){
arr[u].push_back(v);
arr[v].push_back(u);
}
// Function for dfs graph traversal
void graph(vector<int>* arr, int src, int n,bool* check){
cout << src << " ";
check[src] = true;
for (int i = 0; i < arr[src].size(); i++){
if (!check[arr[src][i]])
graph(arr, arr[src][i], n, check);
}
}
void lexo(vector<int>* arr, int n){
bool check[n + 1] = { 0 };
for (int i = 0; i < n; i++)
sort(arr[i].begin(), arr[i].end());
for (int i = 1; i < n; i++){
if (!check[i])
graph(arr, i, n, check);
}
}
int main(){
int n = 5, m = 5;
vector<int> arr[n + 1];
// for inserting an edge
edge(1, 4, arr);
edge(3, 4, arr);
edge(5, 4, arr);
edge(3, 2, arr);
edge(1, 5, arr);
edge(1, 2, arr);
edge(3, 5, arr);
edge(1, 3, arr);
//call lexo function
lexo(arr, n);
return 0;
}输出
如果运行上述程序，它将生成以下输出
1 2 3 4 5
更新于: 22-Aug-2019
257 次浏览
广告