## Programming in Graphs

Discuss all kind of algorithms and data structures from their mathematical and programming sides.

Moderators: Darobat, RecursiveS, Dante Shamest, Bugdude, Wizard

### Programming in Graphs

Hello I want a solution for the question below

I have no idea of data structure and I am poor programmer
Your project will create a program for a given undirected graph (as
shown below) and provides several functions that are associated with this
graph. Please use appropriate data structures to store your graph. PROGRAM CAN BE WRITTEN IN C++

Your project will create a program for a given undirected graph (as
shown below) and provides several functions that are associated with this

Make sure you actually implement the algorithm that produces the
The UNDIRECTED graph as shown below:
(Graph is shown as attachment)

[img]
IMAGE IS SHOWN AS ATTACHMENT
[/img]

You should implement a function to print out the graph in the format as:
5
A
B
C
D
E
A B 1
A C 2
B D 4
D E 3
C E 4
B E 1
D C 2
B C 2
The first line provides the number of nodes in the graph. This number is
fixed as 5 in our project. The next 5 lines contain single character node
designations. This data is stored in the node. The next 6 line provides the
number of edges. Each line contains the edge information. Each line
consists of two node designators (single characters) and the edge's weight.
Note that undirected edges are stored in both directions. That is, the line
A C 2 implies there is an edge C --> A as well as an edge A --> C, both
with weight = 2.
Details of Supported Functions
The descriptions of the functions that will be supported by the graph data
type are as follows:

This function will take a Node as an argument. The function
performs a breadth first search starting from that node. This
function prints nodes in the order it encounters them.
2. Depth First Search (dfs()):
This function will take a Node as an argument. The function
performs a depth first search starting from that node. This function
prints nodes in the order it encounters them.
3. Minimum Spanning Tree (mst()):
This function will print out the edges added to the minimum
spanning tree and it will print the overall weight of the minimum
spanning tree. This should be performed using Prim's algorithm
4. Shortest Path (shortpath()):
This function takes two Node arguments. The first argument is the
source and the second argument is the destination. This function
must print the total distance from the source to the destination and
it must print the path from source to destination. This should be
performed using Dijkstra's algorithm.
Attachments
573+project3_page1_image1.jpg (16.39 KiB) Viewed 2177 times
chpotti

Posts: 2
Joined: Mon Apr 11, 2011 1:37 am

### Re: Programming in Graphs

So what have you done so far? What are you having difficulties with? We are not simply going to do your homework for you.

ventsyv

Posts: 2810
Joined: Mon Sep 22, 2003 5:25 pm
Location: MD USA

### Re: Programming in Graphs

I really dont know how to proceed
chpotti

Posts: 2
Joined: Mon Apr 11, 2011 1:37 am

### Re: Programming in Graphs

Do you understand what an undirected weighted graph is and what operations you can perform on it? Do you know the terminology - what is an edge, what is a node, what's a loop, etc ?

You should first read your textbook and catch up on that, otherwise it will be very hard to finish this assignment, even if we help you. Once you do that, you start by reading the input file and generating the graph, you can use a 2D array or a graph (bunch of nodes connected by pointers) to represent the graph

ventsyv

Posts: 2810
Joined: Mon Sep 22, 2003 5:25 pm
Location: MD USA

### Re: Programming in Graphs

Hello
I am new in this field. So i know a little bit about it.
So i can not suggest you how it works .
jonnitwo

Posts: 28
Joined: Mon Apr 04, 2011 2:57 am
Location: uk

### Re: Programming in Graphs

Hello all,

Gomory-Hu Tree
Mealy and Moore Machines
Bellman Ford Algorithm
Edmonds Karp Algorithm
Ford Fulkerson Algorithm
Dijkstra Algorithm
Hasse Diagrams
Uniform Cost Search
Eulerian Path
Markov Model
Petri Nets
Hamilton Graph

as you see up, i need short algorithms(codes) two of them.. please help me.. im new on this subject..
jancooth

Posts: 1
Joined: Tue May 10, 2011 2:39 pm