# 有关图的问题

• ### 问题

• 外国大学的一道题:

• 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
2011年4月6日 9:42

### 答案

• 建议看一下数据结构的书，里面有图的内容，而且有源代码。如果你能从文件里正确读取数据，新建图就不是问题
NEU_ShieldEdge
• 已标记为答案 2011年4月16日 7:10
2011年4月8日 7:26
• 这个您要根据txt文件中的数据格式自己做解析获取相关的数据。

Visual C++ enthusiast, like network programming and driver development. At present is being engaged in the WinCE/Windows Mobile platform embedded development.
• 已标记为答案 2011年4月16日 7:10
2011年4月14日 3:44

### 全部回复

• 建议看一下数据结构的书，里面有图的内容，而且有源代码。如果你能从文件里正确读取数据，新建图就不是问题
NEU_ShieldEdge
• 已标记为答案 2011年4月16日 7:10
2011年4月8日 7:26
• 要从Graph.txt文件中读取数据的确是个问题,有很大的困难.

这里有二个数组,而且指定为vector类型的,要读取数据并赋值的确有些困难.

xiao
2011年4月8日 9:29
• 这个您要根据txt文件中的数据格式自己做解析获取相关的数据。

Visual C++ enthusiast, like network programming and driver development. At present is being engaged in the WinCE/Windows Mobile platform embedded development.
• 已标记为答案 2011年4月16日 7:10
2011年4月14日 3:44