Homework 4 Simple Undirected Graph

Data Structures Homework #4

Description

Please construct a simple undirected graph (each node contains a 32bit signed integer) with 8 functions: “addEdge”, “deleteEdge”, “deleteVertex”, “degree”, “weight”, “isExistPath”,” deleteGraph” and “number_of_component”.


1.          void addEdge(const int label_1, const int label_2 , const int weight);

A function can add an edge between vertex label_1 & label_2 with edge weight = weight.

If vertex label_1 or label_2 doesn't exist in the graph, create vertex label_1 or label_2 in this graph.

Please note that the edge weight should be the weight that this edge was first added into graph.

e.g. addEdge 0 5 3

addEdge 5 0 10

Then the edge weight of edge 05 is 3.

2.       void deleteEdge(const int label_1, const int label_2);
Delete the edge between vertex label_1 & label_2.

If this edge doesn't exist in this graph, do nothing.

3.       void deleteVertex(const int label);

Delete the vertex label and all edges connected to label.
If label doesn't exist in this graph, do nothing.

4.       int degree(const int label);

Return the degree of vertex label.
If label doesn't exist in this graph, return 0.

5.       int weight(const int label);

Return the sum of edge weight of vertex label.
If label doesn't exist in this graph, return 0.

6.       bool isExistPath(const int label_1, const int label_2);
If there is at least one path between label_1 & label_2, return true.
If there’s no path between label_1 & label_2 or at least one of label_1 and label_2 doesn't exist in the graph, return false.

7.       void deleteGraph();
Delete all vertices and edges in the graph.

8.       int number_of_component();

Return the number of the components in this graph.
If there’s no vertex in this graph, return 0.

 

Implement these functions in function.cpp.

Note

Each of the 3 hidden test cases contains up to 300,000 instructions and each graph may have 150,000 of nodes.

The time limit for test cases 1-3 are 1 sec, time limit for test case 4 is 20 sec.

You have to #include “function.h” to include the partial judge header that we provided.

The testing case1 is similar to Sample Input and make sure your code can pass basic testing to get 60.
題目: http://acm.cs.nthu.edu.tw/problem/11440/
Upload your function.cpp as [studentID]_hw4.zip and submit to ilms BEFORE the deadline.

Input

The input is several instructions:
addEdge 4 6 8

addEdge 7 9 5

addEdge 6 8 4

addEdge 0 3 8

addEdge 8 9 6

weight 6

addEdge 9 5 6

deleteVertex 5

addEdge 6 8 2

weight 9

isExistPath 0 8

addEdge 2 4 6

number_of_component

Output

If your code is correct, the output for online judge would be “[All Accepted]”.

12

11

false

2