C++创建加权图？

Question

如何创建C++加权Graph,其中图中的每个顶点都有一个权重(某个整数值)？

您可以在此处下载我的图表项目(RapidShare):

以下是从存储在文本文件中的图形数据创建图形的功能:

void GraphType::createGraph()
{
    ifstream infile;
    char fileName[50];

    int index;
    int vertex;
    int adjacentVertex;

    if(gSize != 0)
        clearGraph();

    cout << "Enter input file name: ";
    cin >> fileName;
    cout << endl;

    infile.open(fileName);

    if(!infile)
    {
            cout << "Cannot open input file." << endl;
            return;
    }

    infile >> gSize;

    graph = new UnorderedLinkList[gSize];

    for(index = 0; index < gSize; index++)
    {
            infile >> vertex;
            infile >> adjacentVertex;

            while(adjacentVertex != -999)
            {
                graph[ vertex ].insertLast(adjacentVertex);
                infile >> adjacentVertex;
            }
    }
    infile.close();
}

这里是从文本文件"Network2.txt"输入的Graph数据(顶点数= 10,顶点0到9和相邻顶点):

10

0 1 2 9 -999

1 0 2 -999

2 0 1 9 8 3 -999

3 2 8 5 -999

4 3 8 6 5 -999

5 4 6 7 -999

6 4 7 8 -999

7 8 6 5 -999

8 9 2 3 4 6 7 -999

9 0 2 8 -999

我的问题是,如何为顶点0到9分配唯一的值或权重？任何帮助将非常感谢.提前致谢!

Answer 1

的Boost图库(BGL)提供类型MutablePropertyGraph,其内每个边缘和顶点可以存储重量作为属性.请参阅此处的示例,该示例构建具有加权边的有向图.

Answer 2

在邻接列表中，不要让它只存储相邻节点的索引，而是让它存储一个包含相邻节点索引的结构体以及连接这些节点的边的值。