代写C C++ Java Python 视频讲解客服在线客服在线

代做国外C C++ Java程序 Python QQ 2365427650 Email 2365427650@qq.com 免费咨询编程问题

« Computer Architecture Data Structure

Graph Algorithms

In this assignment we want you to write simple graph algorithms for undirected
graphs
. There are three algorithmic tasks. Each task should be coded up in a
separate program.
1. Determine the order of the largest component.
2. Convert to adjacency matrix representation.
3. Compute the diameter.
Input Format
Input for these problems consist of a sequence of one or more (undirected) graphs
taken from the keyboard (e.g.
sys.stdin). Each graph is represented by an adjacency list. The first line is an integer n indicating the order of the graph. This is
followed by
n white space separated lists of adjacencies for nodes labeled 0 to n - 1.
The input will be terminated by a line consisting of one zero (0). This line should
not be processed. Two sample input graphs are listed below.
4 1
0 3
1 5
1 4
0 2
1 3
2 4
0 3
0
G1 G2
0 1
3 2
0 1
2
3
4

Output Format
Output will be like the model answers given below to the console (e.g. sys.stdout).
Your program will only be correct if there is no difference between your output
and the model solution using an automated ’diff’ checker (think
windiff, vim -d,
etc). That is, any other output besides a sequence of answers required is a
wrong
program!
Output for Task 1
Graph 1 has a component of order 3.
Graph 2 has a component of order 5.
Output for Task 2
4
0 1 0 0
1 0 0 1
0 0 0 0
0 1 0 0
5
0 1 0 0 1
1 0 1 0 0
0 1 0 1 0
0 0 1 0 1
1 0 0 1 0
0
Output for Task 3
Graph 1 is disconnected.
Graph 2 has diameter 2.
Besides have a correct program your grade for this assignment will also be based
on how efficient (fast!) your program can handle the marker’s data. To get marks it
must complete with the correct answer within a few seconds on a reasonable sized
data set (e.g., expect more than two graphs with at least 1000 vertices).
  Computer Science 220S2C (2019)
Assignment 3: Graph Algorithms
Please read the entire assignment before starting.
Goals

  • 相关文章:

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新评论及回复

最近发表

Powered By Z-Blog 1.8 Walle Build 100427

Copyright 代写C.