外国大学的一道题:
• Load information of an initial graph from a source file graph.txt from current directory. This file
will provide enough information to construct an initial graph G = { V, E } and produce a valid
graph object (see graph.txt). A graph object has at least two main attributes. One is a set of
vertices where each vertex is a C++ construct. Each edge could look like (1,2, 10) . This will
allow you to keep track of the weight associated with that edge.
• The graph object that is now created must be able to perform a few basic operations (graph
manipulations)
• bool adjacent(Vertex struct1, Vertex struct2): to test whether vertex objects are adjacent
• vector <Vertex> neighbors(Vertex v) to list all adjacent vertices to v
• bool addEdge(Vertex v1, Vertex v2) to add an edge between v1 and v2 if it is not already
there
• bool deleteEdge(Vertex v1, Vertex v2) to delete an edge if it already exists
• int getEdgeValue(Vertex v1, Vertex v2) to return the weight of edge connecting v1 and v2.
You can assume there is at most one edge between any two vertices
• void setEdgeValue(Vertex v1, Vertex v2) to update weight associated to the edge
connecting v1 and v2
• bool isConnected() to test whether the current graph is connected or not
• Develop the breadth-first-search( ) algorithm so that you can search a graph for specific
information. For instance to find all possible paths from a source vertex to a destination vertex.
Your search method must print out all paths that it finds at each step.A breath first search from
vertex 1 to vertex 6 through the graph of our example would produce following paths at each
step. Note that at each step k the distance between the currently visiting node from the root
node is equal to k.
............
Graph.txt上这样定义的:
Sample graph.txt
directed = false
V = city1,city2,city3,city4,city5,city6
E = (city1, city5, 8), (city1, city2, 6), (city5, city4, 12), (city5, city2, 3), (city2, city3, 4), (city3,
city4, 7), (city4, city6, 12)
第一步这是要加载graph.txt文件去初始化图.加载graph.txt文件很简单,初始化图怎样实现呢?要怎样去想?我一点思路也没有.
xiao
