开始打印图表的字典最小 bfs
原文:
给定一个有 n 个顶点和 m 条边的连通图。任务是打印从 1 开始的字典上最小的图的 bfs 遍历。 注:顶点从 1 到 n 编号 例:
input: n = 5, m = 5
edges:
1 4
3 4
5 4
3 2
1 5
output: 1 4 3 2 5
start from 1, go to 4, then to 3 and then to 2 and to 5\.
input: n = 3, m = 2
edges:
1 2
1 3
output: 1 2 3
方法:我们可以使用优先级队列(最小堆)代替简单的队列，而不是在图上进行正常的 bfs 遍历。当节点被访问时，将其相邻节点添加到优先级队列中。每次，我们访问一个新节点，它将是优先级队列中索引最小的节点。当我们每次从 1 开始访问节点时，打印节点。 以下是上述办法的实施情况:
卡片打印处理机（card print processor 的缩写）
// c program to print the lexcicographically
// smallest path starting from 1
#include
using namespace std;
// function to print the smallest lexicographically
// bfs path starting from 1
void printlexosmall(vector adj[], int n)
{
// visited array
bool vis[n 1];
memset(vis, 0, sizeof vis);
// minimum heap
priority_queue, greater > q;
// first one visited
vis[1] = true;
q.push(1);
// iterate till all nodes are visited
while (!q.empty()) {
// get the top element
int now = q.top();
// pop the element
q.pop();
// print the current node
cout << now << " ";
// find adjacent nodes
for (auto p : adj[now]) {
// if not visited
if (!vis[p]) {
// push
q.push(p);
// mark as visited
vis[p] = true;
}
}
}
}
// function to insert edges in the graph
void insertedges(int u, int v, vector adj[])
{
adj[u].push_back(v);
adj[v].push_back(u);
}
// driver code
int main()
{
int n = 5, m = 5;
vector adj[n 1];
// insert edges
insertedges(1, 4, adj);
insertedges(3, 4, adj);
insertedges(5, 4, adj);
insertedges(3, 2, adj);
insertedges(1, 5, adj);
// function call
printlexosmall(adj, n);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program to print the lexcicographically
// smallest path starting from 1
import java.util.*;
public class gfg
{
// function to print the smallest lexicographically
// bfs path starting from 1
static void printlexosmall(vector> adj, int n)
{
// visited array
boolean[] vis = new boolean[n 1];
// minimum heap
vector q = new vector();
// first one visited
vis[1] = true;
q.add(1);
// iterate till all nodes are visited
while (q.size() > 0) {
// get the top element
int now = q.get(0);
// pop the element
q.remove(0);
// print the current node
system.out.print(now " ");
// find adjacent nodes
for(int p : adj.get(now)) {
// if not visited
if (!vis[p]) {
// push
q.add(p);
collections.sort(q);
// mark as visited
vis[p] = true;
}
}
}
}
// function to insert edges in the graph
static void insertedges(int u, int v, vector> adj)
{
adj.get(u).add(v);
adj.get(v).add(u);
}
// driver code
public static void main(string[] args) {
int n = 5;
vector> adj = new vector>();
for(int i = 0; i < n 1; i )
{
adj.add(new vector());
}
// insert edges
insertedges(1, 4, adj);
insertedges(3, 4, adj);
insertedges(5, 4, adj);
insertedges(3, 2, adj);
insertedges(1, 5, adj);
// function call
printlexosmall(adj, n);
}
}
// this code is contributed by divyeshrabadiya07.
python 3
# python program to print the lexcicographically
# smallest path starting from 1
# function to print the smallest lexicographically
# bfs path starting from 1
def printlexosmall(adj, n):
# visited array
vis = [false for i in range(n 1)]
# minimum heap
q = []
# first one visited
vis[1] = true;
q.append(1)
# iterate till all nodes are visited
while(len(q) != 0):
# get the top element
now = q[0]
# pop the element
q.pop(0)
# print the current node
print(now, end = " ")
# find adjacent nodes
for p in adj[now]:
# if not visited
if(not vis[p]):
# push
q.append(p)
q.sort()
# mark as visited
vis[p] = true
# function to insert edges in the graph
def insertedges(u, v, adj):
adj[u].append(v)
adj[v].append(u)
# driver code
n = 5
m = 5
adj = [[] for i in range(n 1)]
# insert edges
insertedges(1, 4, adj)
insertedges(3, 4, adj)
insertedges(5, 4, adj)
insertedges(3, 2, adj)
insertedges(1, 5, adj)
# function call
printlexosmall(adj, n)
# this code is contributed by avanitrachhadiya2155
c
// c# program to print the lexcicographically
// smallest path starting from 1
using system;
using system.collections.generic;
class gfg {
// function to print the smallest lexicographically
// bfs path starting from 1
static void printlexosmall(list> adj, int n)
{
// visited array
bool[] vis = new bool[n 1];
// minimum heap
list q = new list();
// first one visited
vis[1] = true;
q.add(1);
// iterate till all nodes are visited
while (q.count > 0) {
// get the top element
int now = q[0];
// pop the element
q.removeat(0);
// print the current node
console.write(now " ");
// find adjacent nodes
foreach (int p in adj[now]) {
// if not visited
if (!vis[p]) {
// push
q.add(p);
q.sort();
// mark as visited
vis[p] = true;
}
}
}
}
// function to insert edges in the graph
static void insertedges(int u, int v, list> adj)
{
adj[u].add(v);
adj[v].add(u);
}
// driver code
static void main()
{
int n = 5;
list> adj = new list>();
for(int i = 0; i < n 1; i )
{
adj.add(new list());
}
// insert edges
insertedges(1, 4, adj);
insertedges(3, 4, adj);
insertedges(5, 4, adj);
insertedges(3, 2, adj);
insertedges(1, 5, adj);
// function call
printlexosmall(adj, n);
}
}
// this code is contributed by divyesh072019.
java 描述语言
output:
1 4 3 2 5
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
