目录
要求
- 图的邻接表和邻接矩阵存储
- 建立下图的邻接表或邻接矩阵,并输出之;
- 思路:
- 通过遍历邻接矩阵,采用头插法即可构造邻接表。
- 图的各种遍历算法实现
- 以0结点为起点实现上述图的深度优先和广度优先遍历算法;
- 思路:
- 用堆栈实现深度优先遍历,用队列实现广度优先遍历。
- 最小生成树的算法实现
- 利用普里姆(Prim)算法或克鲁斯卡尔(Kruskal)算法求上图的最小生成树,算法实现代码必需有注释。
- 思路:
- Prim:从0点出发每次取能到达的最小权重边,走完即为一颗最小生成树。
- 最短路径的算法实现
- 利用狄克斯特拉(Dijkstra)算法求上图中0结点到其它结点的最短路径,算法实现代码必须有注释。
- 思路:
- 循环每次计算到每一个点的最小距离并记录,然后取最小距离的那个点合并。
源代码
若以下显示需要登录,请刷新页面或点击此处下载。
思考
若只求带权有向图G中从顶点i到顶点j的最短路径,如何修改Dijkstra 算法来实现这一功能?
void Dijkstra_way(int first_point)
{
int* widget_list = new int[map_size]; //记录距离0的长度
for (int i = map_size; i--;)
{
widget_list[i] = INF;
adjList[i].weight = -1;
}
widget_list[first_point] = 0;
adjList[first_point].weight = 0;
for (int i = 1; i < map_size; ++i)
for (int j = map_size; j--;) //计算距离
if (adjList[j].weight >= 0)
for (node* node_p = adjList[j].next_p; node_p != NULL; node_p = node_p->next_p)
if (widget_list[j] + node_p->weight < widget_list[node_p->data])
{
widget_list[node_p->data] = widget_list[j] + node_p->weight;
adjList[node_p->data].weight = j;
}
cout << "<< Dijkstra 最短路径:" << endl;
coolQueue<int> stack;
for (int i = 0; i < map_size; ++i)
{
for (int j = i; j != first_point;)
{
stack.End_push(j);
j = adjList[j].weight;
}
cout << "<< " << first_point;
for (int pop_int = 0; stack.End_pop(pop_int);)
cout << " -> " << pop_int;
cout << endl;
stack.clear();
}
adjList_reflush();
}
Great blog here! Also your site loads up fast! What host are you using? Can I get your affiliate link to your host? I wish my website loaded up as fast as yours lol
Oh my goodness! an amazing post dude. Thanks a lot However My business is experiencing trouble with ur rss . Do not know why Unable to join it. Will there be anybody acquiring identical rss difficulty? Anyone who knows kindly respond. Thnkx
I’m truly enjoying the design and layout of your site. It’s a very easy on the eyes which makes it much more enjoyable for me to come here and visit more often. Did you hire out a designer to create your theme? Superb work!
Hi, I do think this is a great website. I stumbledupon it 😉 I’m going to come back yet again since I saved as a favorite it. Money and freedom is the greatest way to change, may you be rich and continue to guide others.
Can I recently say thats a relief to locate someone who in fact knows what theyre preaching about on-line. You actually realize how to bring a challenge to light making it critical. More people should check out this and see why side of the story. I cant believe youre no more well-known simply because you definitely possess the gift.
Hey there, I think your blog might be having browser compatibility issues. When I look at your blog in Safari, it looks fine but when opening in Internet Explorer, it has some overlapping. I just wanted to give you a quick heads up! Other then that, awesome blog!
Your blog site is pretty cool! How was it made !
An impressive share, I merely given this onto a colleague who had been doing a small analysis within this. And that he actually bought me breakfast since I discovered it for him.. smile. So ok, i’ll reword that: Thnx for the treat! But yeah Thnkx for spending time to talk about this, I’m strongly about this and love reading regarding this topic. If you can, as you grow expertise, would you mind updating your website with more details? It is extremely of great help for me. Massive thumb up for this text!
Hello there, just became alert to your blog through Google, and found that it is really informative. I’m going to watch out for brussels. I’ll be grateful if you continue this in future. A lot of people will be benefited from your writing. Cheers!
The guidelines you provided allow me to share extremely precious. It been found such a pleasurable surprise to possess that looking forward to me once i awoke today. They may be constantly clear easy to understand. Thanks a ton for the valuable ideas you’ve got shared the following.
Do you people have a facebook fan page? I looked for one on twitter but could not discover one, I would really like to become a fan!
healthy eating should be our top priority since there are many junk foods and foods with no nutritional value these days**
Most of the people take advantage of the list to be certain they have the many necessary elements, such as food and clothes.
I discovered your web page just recently through a recommendation and had a look at some of your articles. I like what you are writing about and I hope you keep up the good work. If you are interested in sharing some content or swap links do not hesitate to get in touch with me.
What would be your next topic next week on your blog.”“:’
This web page is often a walk-through its the internet you wanted about this and didn’t know who to question. Glimpse here, and you’ll absolutely discover it.
we have different jewelry boxes at home and most of them comes from my mother who like to collect jewelry boxes;;
Hiya, I just hopped over for your web site by way of StumbleUpon. Not something I might typically learn, but I liked your emotions none the less. Thank you for making something value reading.
I strongly agree on you, I hope that others will realized this also and will take time to read your post! keep writing mate!
my daughter have been doing some scrapbooking stuffs over the years and she really likes it,.
Your blog is amazing dude. i love to visit it everyday. very nice layout and content “
The truth is and see if the Hcg diet protocol and as a consequence HCG Drops certainly are a in fact quick way to be able to shed pounds; while the healthy diet has a strong will most likely moreover sizable focus to undertake positive. hcg diet drops
Good website! I truly love how it is easy on my eyes it is. I am wondering how I might be notified whenever a new post has been made. I have subscribed to your RSS which may do the trick? Have a great day!
Hello there! Great stuff, please do tell me when you post again something similar!
Howdy! This blog post could not be written any better! Looking through this article reminds me of my previous roommate! He continually kept preaching about this. I am going to send this information to him. Pretty sure he will have a good read. Thanks for sharing!
I saw one more thing relating to this on another blog. Youve obviously spent time on this. Congratulations!
After study many of the content in your web site now, and i also truly much like your way of blogging. I bookmarked it to my bookmark website list and are checking back soon. Pls take a look at my web page also and inform me how you feel.
my kids really like to play with those assorted pool toys, they specially like pokemon pool toys and stuff like that*
certainly like your web site but you need to check the spelling on several of your posts. Several of them are rife with spelling problems and I find it very troublesome to tell the truth nevertheless I will definitely come back again.
I together with my friends came reading the nice information and facts on your website and all of the sudden I got a terrible suspicion I had not expressed respect to the web blog owner for those strategies. Those young men became absolutely happy to study all of them and have now simply been tapping into these things. Appreciate your being simply accommodating as well as for going for some amazing resources millions of individuals are really desperate to know about. My personal honest regret for not expressing gratitude to earlier.
Can I just now say what a relief to find one who in fact knows what theyre speaking about online. You definitely understand how to bring a problem to light making it essential. Workout . should see this and understand this side from the story. I cant think youre less well-known when you absolutely provide the gift.
Sweet blog! I found it while surfing around on Yahoo News. Do you have any tips on how to get listed in Yahoo News? I’ve been trying for a while but I never seem to get there! Thanks
Your style is unique in comparison to other people I have read stuff from. Thank you for posting when you’ve got the opportunity, Guess I will just book mark this web site.
Intimately, the post is actually the sweetest on that worthw hile topic. I harmonise with your conclusions and also will certainly eagerly look forward to your incoming updates. Saying thanks will certainly not simply be enough, for the extraordinary clarity in your writing. I can perfect away grab your rss feed to stay informed of any kind of updates. Solid work and also much success in your business dealings!
i like Californication because of the pretty girls and the nice music that it imparts on the show,,
Appreciate it to get a incredibly apparent and very helpful publish. I’m positively a violator of many of these rules. I generally uncover personally conflicted when producing a blog posting because I see myself personally creating more than people prefer to read, but I feel that I have got to do the subject matter proper rights by completely protecting it. I think that by pursuing some of these policies I finish up cutting out critical factors to the dialogue. I guess you could have to acquire a stability.
Hey! I simply wish to give a huge thumbs up for the good information you have right here on this post. I might be coming back to your weblog for extra soon.
“Hello, you site is very funny he told me to cheer up”
safe online canadian pharmacy
Thank you for taking the time to discuss the idea, I find myself intently with it and additionally real love looking at more about this kind of theme. In the event capability, mainly because you arrive at mastery, on earth do you insights upgrading your primary webpage utilizing indepth important info? This is useful for all of us.
Just wanna input on few general things, The website design is perfect, the articles is very great : D.
An intriguing discussion is worth comment. There’s no doubt that that you ought to publish more on this subject matter, it may not be a taboo matter but typically people don’t speak about such issues. To the next! Kind regards!
Здесь вы найдете разнообразный видео контент отмена бронирования ялта интурист и возврат
generic amoxicillin 500mg: amoxil online – where can i buy amoxicillin without prec
amoxicillin 500mg prescription
amoxicillin from canada: cheapest amoxicillin – amoxicillin 500 coupon
canadian pharmacy amoxicillin
http://azithromycinca.com/# where can i buy doxycycline in singapore
doxycycline 40 mg generic coupon
http://azithromycinca.com/# price of doxycycline 100mg
doxycycline generic price
Hello! Do you know if they make any plugins to help with Search
Engine Optimization? I’m trying to get my site to rank for some targeted keywords
but I’m not seeing very good results. If you know of any please share.
Cheers! You can read similar text here
price prescriptions
family pharmacy online