对输入图的折线图执行边缘着色的 C++ 程序

2023-06-20 12:06:03 507

算法

Begin Take the input of the number of vertices ‘n’ and number of edges ‘e’. Take the input of ‘n’ vertex pairs for the ‘e’ edges in the graph in ed[][]. Function GenLineGraph(): Construct a line graph in LineEd[][]. To construct line graph, for each edge in the given graph, connect it to its adjacent edge in LineEd. Function EdgeColor(): Color the graph edges of LineEdge[][] graph. Assign color to current edge as col i.e. 1 initially. If any of the adjacent edges have the same color, then discard this color and go to flag again and try next color. Print the color for each edge of the line graph. End.

示例代码

#include using namespace std; int GenLineGraph(int ed[][2], char LineEd[][3], int e) { int i, cnt = 0, j, N; char c; for(i = 0; i < e; i++) { for(j = i+1; j < e; j++) { if(ed[j][0] == ed[i][0] || ed[j][0] == ed[i][1] || ed[j][1] == ed[i][0] || ed[j][1] == ed[i][1]) { LineEd[cnt][0] = 'a'+i; LineEd[cnt][1] = 'a'+j; LineEd[cnt][2] = 0; cnt++; } } } N = cnt; cout<<"\n\nThe adjacency list representation for the given graph: "; for(i = 0; i < e; i++) { cnt = 0; c = 'a'+i; cout<<"\n\t"< { "; for(j = 0; j < N; j++) { if(LineEd[j][0] == i+'a') { cout<>n; cout<<"输入图形的边数： "; cin>>e; int ed[e][2]; char LineEd[e*e][3]; for(i = 0; i < e; i++) { cout<<"\nEnter the vertex pair for edge '"<>ed[i][0]; cout<<"V(2): "; cin>>ed[i][1]; } e = GenLineGraph(ed, LineEd, e); EdgeColor(LineEd , e); for(i = 0; i < e; i++) cout<<"\nThe color of the edge between vertex n(1):"<输出结果

输入图形的顶点数：4
输入图形的边数： 3
Enter the vertex pair for edge 'a'
V(1): 1
V(2): 2
Enter the vertex pair for edge 'b'
V(1): 3
V(2): 2
Enter the vertex pair for edge 'c'
V(1): 4
V(2): 1
The adjacency list representation for the given graph:
a-> { b c }
b-> { a }
c-> { a }
The color of the edge between vertex n(1):a and n(2):b is: color1.
The color of the edge between vertex n(1):a and n(2):c is: color2.

对输入图的折线图执行边缘着色的 C++ 程序

算法

示例代码

热门推荐

随机推荐