none
有关图的问题 RRS feed

  • 问题

  • 外国大学的一道题:

    • 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
    • 已标记为答案 wh_xiao 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.
    • 已标记为答案 wh_xiao 2011年4月16日 7:10
    2011年4月14日 3:44
    版主

全部回复

  • 建议看一下数据结构的书,里面有图的内容,而且有源代码。如果你能从文件里正确读取数据,新建图就不是问题
    NEU_ShieldEdge
    • 已标记为答案 wh_xiao 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.
    • 已标记为答案 wh_xiao 2011年4月16日 7:10
    2011年4月14日 3:44
    版主