Need Help with an algorithm-graph

Hello. I have an assignment to do on graphs and I'm a little confused. Basically i have to examine if a directed graph is a star graph or a ring graph and print both of them with an adjacency list and an adjacency matrix. Also i have to find which is the worst case of complexity for these algorithms.

Can anyone help me?

Thanks in advance!

Re: Need Help with an algorithm-graph

Any connected graph with an equal number of vertices and edges must be a ring graph. (If it isn't connected, it must be a collection of disjoint ring graphs.)

You can test for connectedness and ringness simultaneously with a depth-first-search, aborting if you ever encounter a vertex with other than 2 edges before you return to the original vertex. If you traversed all the vertices, you have a ring graph.

Star graphs are even easier. Assuming no self-edges, just check whether or not every vertex except one has 1 edge, and the last has n-1 edges.

Re: Need Help with an algorithm-graph

Thanks a lot for the help.Another thing,can this program be made in C? and if yes, i need to use arrays, right?

Re: Need Help with an algorithm-graph

Quote:

Originally Posted by

**Dominus_Mors**
Thanks a lot for the help.Another thing,can this program be made in C?

Why do you think it can't be made in 'C'? Some of the most sophisticiated pieces of software have been built using 'C'
Quote:

i need to use arrays, right?

There is no "need" to use arrays in any program you create. Whether arrays makes it easier, that is another story.

Regards,

Paul McKenzie

Re: Need Help with an algorithm-graph

BY asking i mean if this is easy to be made in C. And yes you're right C is one of the best languages after assembly. and the array thing you need to make efficient programs,with any means necessary! By the way,thanks.

Re: Need Help with an algorithm-graph

Just about any programming language will be able to do graph algorithms fairly easily. The efficiency will be determined much more by the choice of algorithm than by the language. The most difficult part will be deciding what data structure you will use to store the graph.