Top Research Professionals
The research experts and assignment help team consists exclusively of highly qualified graduate writers, each professional with in-depth subject matter expertise and significant experience in custom academic writing.
Boost Your Final Grades By Ordering Custom Writing Help!
For similar papers and sample answers; with a few clicks, Order your research paper, thesis, dissertation writing and other assignment help services
Posted: June 15th, 2022
Develop a program to read simple undirected connected graphs into an n x n 2D array.
Develop a program to read simple undirected connected graphs into an n x n 2D array.
CMPS 2433 – Discrete Structures and Analysis
Program 4
Due December 4, 2018
Problem: Write a program to read simple undirected connected graphs into an n x n 2D array. Then
determine whether that graph has an Euler Circuit using the algorithm described below. If the graph has
an Euler circuit, find one and print out the nodes in the Euler Circuit. If the graph does not have one,
print NO EULER CIRCUIT EXISTS.
Method: First your program must determine if the connected graph input and stored in the 2D array has
an Euler Circuit. A graph that has vertices of all even degree contains an Euler Circuit. Second, if the
graph does have one, then your program must find an Euler Circuit in the graph using a modification of
Fleury’s algorithm.
Fleury’s algorithm, published 1883 constructs Euler subcircuits by first choosing an arbitrary vertex (say
0) of a graph, and forms a circuit by choosing edges successively. Once an edge is chosen, it is removed.
Edges are chosen successively so that each edge begins where the last edge ends, and so that this edge
is not a cut edge, unless there is no alternative. The algorithm terminates when the original vertex (0) is
reached. If there are no edges remaining in the graph, then the path has the constructed Euler circuit,
otherwise it has only found a subcircuit. Just stop there and print out a message that only a subcircuit
was found.
Important Notes:
You must use arrays or vectors in this program.
If you use arrays, you must dynamically allocate memory for each array and properly free up
that memory when you finish processing that particular graph (array).
You must write functions to
o Open the input and output files
o Read in the graph’s edges
o Determine if a graph has an Euler Circuit
o Find and print an Euler Circuit using Fleury’s algorithm
o Determine if a graph has edges
There will not be more than 20 vertices.
Vertices are labelled 0, 1, 2, …
Input File: connected2D.dat
Sample input file: 3 //number of test cases
6 //number of rows and columns in the 2D array
0 1 0 0 0 1 //values in the 2D array
1 0 1 0 0 0 //DRAW the GRAPH on the input file
0 1 0 1 1 1
0 0 1 0 1 0
0 0 1 1 0 1
1 0 1 0 0 0
4 //number of rows and columns in the 2D array
0 1 1 1 //values in the 2D array
1 0 1 1 //DRAW the GRAPH on the input file
1 1 0 1
1 1 1 0
7
0 1 0 1 0 0 0
1 0 0 1 0 0 0
0 0 0 1 1 0 0
1 1 1 0 1 1 1
0 0 1 1 0 0 0
0 0 0 1 0 0 1
0 0 0 1 0 1 0
Output File: lastname_prog4.txt
Sample output file: Joanna Wringer
Euler Circuit: There are 3 Graphs
GRAPH 1
0 1 2 3 4 2 5 0
EULER CIRCUIT CONSTRUCTED
GRAPH 2
NO EULER CIRCUIT EXISTS
GRAPH 3
0 1 3 0
A SUBCIRCUIT CONSTRUCTED
Study Notes, Research Topics & Assignment Examples: Local laws versus international maritime laws »Nursing Essay Writing ServiceWhy Choose our Custom Writing Services
We prioritize delivering top quality work sought by college students.
Discounted Pricing
Our custom writing services maintain the highest quality while remaining affordable for students. Our pricing for research papers, theses, and dissertations is not only fair considering the superior quality but also competitive with other writing services.
0% Similarity Index
We guarantee plagiarism-free, human-written content. Every product is assured to be original and not AI-generated. Our writers, tutors and editors are research experts who ensures the right formating and citation sytles are followed. To note, all the final drafts undergo rigorous plagiarism checks before delivery for submission to ensure authenticity for our valued customers.
How it works
When you decide to place an order with Dissertation Help, here is what happens: