Need Help with an algorithm-graph

[Dominus_Mors]

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!

[Lindley]

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.

[Dominus_Mors]

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

[Paul McKenzie]

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'

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

[Dominus_Mors]

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.

[Lindley]

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.