原文:
给定一个有 n 个节点的无向图，任务是打印具有最小和最大度数的节点。 例:
input:
1-----2
| |
3-----4
output:
nodes with maximum degree : 1 2 3 4
nodes with minimum degree : 1 2 3 4
every node has a degree of 2.
input:
1
/ \
2 3
/
4
output:
nodes with maximum degree : 1 2
nodes with minimum degree : 3 4
逼近:对于无向图来说，节点的度就是入射到它的边数，所以每个节点的度可以通过统计它在边列表中的出现频率来计算。因此，方法是使用图从边列表中计算每个顶点的频率，并使用该图找到具有最大和最小度数的节点。 以下是上述方法的实施:
c
// c implementation of the approach
#include
using namespace std;
// function to print the nodes having
// maximum and minimum degree
void minmax(int edges[][2], int len, int n)
{
// map to store the degrees of every node
map m;
for (int i = 0; i < len; i ) {
// storing the degree for each node
m[edges[i][0]] ;
m[edges[i][1]] ;
}
// maxi and mini variables to store
// the maximum and minimum degree
int maxi = 0;
int mini = n;
for (int i = 1; i <= n; i ) {
maxi = max(maxi, m[i]);
mini = min(mini, m[i]);
}
// printing all the nodes with maximum degree
cout << "nodes with maximum degree : ";
for (int i = 1; i <= n; i ) {
if (m[i] == maxi)
cout << i << " ";
}
cout << endl;
// printing all the nodes with minimum degree
cout << "nodes with minimum degree : ";
for (int i = 1; i <= n; i ) {
if (m[i] == mini)
cout << i << " ";
}
}
// driver code
int main()
{
// count of nodes and edges
int n = 4, m = 6;
// the edge list
int edges[][2] = { { 1, 2 },
{ 1, 3 },
{ 1, 4 },
{ 2, 3 },
{ 2, 4 },
{ 3, 4 } };
minmax(edges, m, 4);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java implementation of the approach
import java.util.*;
class gfg
{
// function to print the nodes having
// maximum and minimum degree
static void minmax(int edges[][], int len, int n)
{
// map to store the degrees of every node
hashmap m = new hashmap();
for (int i = 0; i < len; i )
{
// storing the degree for each node
if(m.containskey(edges[i][0]))
{
m.put(edges[i][0], m.get(edges[i][0]) 1);
}
else
{
m.put(edges[i][0], 1);
}
if(m.containskey(edges[i][1]))
{
m.put(edges[i][1], m.get(edges[i][1]) 1);
}
else
{
m.put(edges[i][1], 1);
}
}
// maxi and mini variables to store
// the maximum and minimum degree
int maxi = 0;
int mini = n;
for (int i = 1; i <= n; i )
{
maxi = math.max(maxi, m.get(i));
mini = math.min(mini, m.get(i));
}
// printing all the nodes with maximum degree
system.out.print("nodes with maximum degree : ");
for (int i = 1; i <= n; i )
{
if (m.get(i) == maxi)
system.out.print(i " ");
}
system.out.println();
// printing all the nodes with minimum degree
system.out.print("nodes with minimum degree : ");
for (int i = 1; i <= n; i )
{
if (m.get(i) == mini)
system.out.print(i " ");
}
}
// driver code
public static void main(string[] args)
{
// count of nodes and edges
int n = 4, m = 6;
// the edge list
int edges[][] = {{ 1, 2 }, { 1, 3 },
{ 1, 4 }, { 2, 3 },
{ 2, 4 }, { 3, 4 }};
minmax(edges, m, 4);
}
}
// this code is contributed by princiraj1992
python 3
# python3 implementation of the approach
# function to print the nodes having
# maximum and minimum degree
def minmax(edges, leng, n) :
# map to store the degrees of every node
m = {};
for i in range(leng) :
m[edges[i][0]] = 0;
m[edges[i][1]] = 0;
for i in range(leng) :
# storing the degree for each node
m[edges[i][0]] = 1;
m[edges[i][1]] = 1;
# maxi and mini variables to store
# the maximum and minimum degree
maxi = 0;
mini = n;
for i in range(1, n 1) :
maxi = max(maxi, m[i]);
mini = min(mini, m[i]);
# printing all the nodes
# with maximum degree
print("nodes with maximum degree : ",
end = "")
for i in range(1, n 1) :
if (m[i] == maxi) :
print(i, end = " ");
print()
# printing all the nodes
# with minimum degree
print("nodes with minimum degree : ",
end = "")
for i in range(1, n 1) :
if (m[i] == mini) :
print(i, end = " ");
# driver code
if __name__ == "__main__" :
# count of nodes and edges
n = 4; m = 6;
# the edge list
edges = [[ 1, 2 ], [ 1, 3 ],
[ 1, 4 ], [ 2, 3 ],
[ 2, 4 ], [ 3, 4 ]];
minmax(edges, m, 4);
# this code is contributed by ankitrai01
c
// c# implementation of the approach
using system;
using system.collections.generic;
class gfg
{
// function to print the nodes having
// maximum and minimum degree
static void minmax(int [,]edges, int len, int n)
{
// map to store the degrees of every node
dictionary m = new dictionary();
for (int i = 0; i < len; i )
{
// storing the degree for each node
if(m.containskey(edges[i, 0]))
{
m[edges[i, 0]] = m[edges[i, 0]] 1;
}
else
{
m.add(edges[i, 0], 1);
}
if(m.containskey(edges[i, 1]))
{
m[edges[i, 1]] = m[edges[i, 1]] 1;
}
else
{
m.add(edges[i, 1], 1);
}
}
// maxi and mini variables to store
// the maximum and minimum degree
int maxi = 0;
int mini = n;
for (int i = 1; i <= n; i )
{
maxi = math.max(maxi, m[i]);
mini = math.min(mini, m[i]);
}
// printing all the nodes with maximum degree
console.write("nodes with maximum degree : ");
for (int i = 1; i <= n; i )
{
if (m[i] == maxi)
console.write(i " ");
}
console.writeline();
// printing all the nodes with minimum degree
console.write("nodes with minimum degree : ");
for (int i = 1; i <= n; i )
{
if (m[i] == mini)
console.write(i " ");
}
}
// driver code
public static void main(string[] args)
{
// count of nodes and edges
int m = 6;
// the edge list
int [,]edges = {{ 1, 2 }, { 1, 3 },
{ 1, 4 }, { 2, 3 },
{ 2, 4 }, { 3, 4 }};
minmax(edges, m, 4);
}
}
// this code is contributed by 29ajaykumar
output:
nodes with maximum degree : 1 2 3 4
nodes with minimum degree : 1 2 3 4
时间复杂度 : o(mlogn n)。 辅助空间* : o(n)。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
