使用C++的图数据结构

Question

我正在制作一个将打印所有路径的控制台应用程序。但我很难想出如何显示从源到目标的所有路径。

这里是我的代码：

#include<iostream> 

using namespace std; 

int arr[8][8] = {{50,30,45,120,0,7,0,0},{30,45,28,4,70,0,0,0}, 
{50,20,0,38,0,0,0,0},{0,4,30,0,52,0,3,0},{0,75,0,27,0,2,0,3}, 
{70,0,0,0,2,0,2,0},{0,80,0,73,0,2,0,0},{60,0,90,0,30,0,0,0}}; 
char vertex[8] = {'A','B','C','D','E','F','G','H'}; 

void displayPath() 
{ 
    system("cls"); 
    int start, end; 
    char from, to; 

    cout << "From vertex: "; 
    cin >> from; 
    cout << "To: "; 
    cin >> to; 

    switch(from) 
    { 
     case 'a':case 'A': start = 0; break; 
     case 'b':case 'B': start = 1; break; 
     case 'c':case 'C': start = 2; break; 
     case 'd':case 'D': start = 3; break; 
     case 'e':case 'E': start = 4; break; 
     case 'f':case 'F': start = 5; break; 
     case 'g':case 'G': start = 6; break; 
     case 'h':case 'H': start = 7; break;  

    } 

    switch(to) 
    { 
     case 'a':case 'A': end = 0; break; 
     case 'b':case 'B': end = 1; break; 
     case 'c':case 'C': end = 2; break; 
     case 'd':case 'D': end = 3; break; 
     case 'e':case 'E': end = 4; break; 
     case 'f':case 'F': end = 5; break; 
     case 'g':case 'G': end = 6; break; 
     case 'h':case 'H': end = 7; break; 
    } 

    int temp = 0; 
    int current = start; 

    if(arr[start][end] > 0) 
    { 
     cout << vertex[start] << "->" << vertex[end]; 
    } 
    else 
     cout << "No path"; 
} 

void computeDistance() 
{ 
    system("cls"); 
    int start,end; 
    char from, to; 

    cout << "From vertex: "; 
    cin >> from; 
    cout << "To: "; 
    cin >> to; 

    switch(from) 
    { 
     case 'a':case 'A': start = 0; break; 
     case 'b':case 'B': start = 1; break; 
     case 'c':case 'C': start = 2; break; 
     case 'd':case 'D': start = 3; break; 
     case 'e':case 'E': start = 4; break; 
     case 'f':case 'F': start = 5; break; 
     case 'g':case 'G': start = 6; break; 
     case 'h':case 'H': start = 7; break;  
    } 

    switch(to) 
    { 
     case 'a':case 'A': end = 0; break; 
     case 'b':case 'B': end = 1; break; 
     case 'c':case 'C': end = 2; break; 
     case 'd':case 'D': end = 3; break; 
     case 'e':case 'E': end = 4; break; 
     case 'f':case 'F': end = 5; break; 
     case 'g':case 'G': end = 6; break; 
     case 'h':case 'H': end = 7; break; 
    } 

    if(arr[start][end] > 0) 
    { 
     cout << arr[start][end] << " meters" << endl; 
    } 
    else 
     cout << "No path"; 
} 

int main() 
{ 
    int choice; 

    cout << "Menu\n\n[1] Display Path\n[2] Compute Distance\n\nChoice: "; 
    cin >> choice; 

    switch(choice) 
    { 
     case 1: displayPath(); break; 
     case 2: computeDistance(); break; 
    } 

    system("pause"); 
    return 0; 
} 

该程序只给出了源到目标，不是所有的顶点穿过。这应该是样本输出：

From: A 
To: F 

A -> B -> D -> F 

此外，它应遵循最短路径的概念。并会给总距离。我希望你能用这个帮助我。提前谢谢你。

Answer 1

首先你需要实现一些算法，它将找到最短路径。
基本上有几个选择：

• Dijkstra's algorithm
• A* search algorithm

我看不出你有什么实现其做这样的搜索。

Answer 2

图中2个节点之间的各种路径的数量是指数型的。这意味着可以有很多。 我不确定你的图是否总是由8个节点构成。在下面的解决方案中，我假定它是。

1. 有了这样一个小数据，你可以使用非常缓慢和效率不高的解决方案。
2. 示例：让我们生成节点的每个可能的排列，并检查从源头开始的所有排列，并检查它们直到它们到达目的地。
3. 检查所有路径后获取最短路径非常简单 - 只需在检查每条路径的总距离时进行计数。

一些代码：

#include <bits/stdc++.h> 
using namespace std; 

int Graph[8][8]; 
map <int, bool> used; // to not print same path multiple times 


int valid_path(int src, int dest, vector<int>& path) 
{ 
    int pathHash=0; 
    if (path[0]!=src) return -1; 
    for (size_t i=1; i<path.size(); i++) 
    { 
     pathHash= pathHash*10+path[i]; // such solution works only because of small size of data 
     if (Graph[path[i-1]][path[i]]==0) return -1; // there is no edge between these nodes 
     if (path[i]==dest) break; 

    } 
    return pathHash; 
} 

void print_path (int dest, vector<int>& path) 
{ 
    for (size_t i=0; i<path.size(); i++) 
    { 
     cout << path[i] << " "; 
     if (path[i]==dest) break; 
     cout << " --> "; 
    } 
} 

void generate_paths(int src, int dest) 
{ 
    vector<int> perm {0, 1, 2, 3, 4, 5, 6, 7}; 
    do 
    { 
     int pathHash= valid_path(src, dest, perm); 
     if (pathHash!=-1 && used[pathHash]==false) 
     { 
      used[pathHash]=true; 
      print_path(dest, perm); 
      cout << "\n"; 
     } 
    } while (next_permutation(perm.begin(), perm.end())); 
} 


int main() { 
    for (size_t i=0; i<8; i++) 
    { 
     for (size_t j=0; j<8; j++) 
     { 
      cin >> Graph[i][j]; 
     } 
    } 
    generate_paths(0, 7); 
} 

/* example input 
0 1 0 1 0 1 0 0 
0 0 1 0 0 0 0 0 
0 0 0 1 0 0 0 0 
0 1 0 0 1 0 0 0 
0 0 0 0 0 1 0 0 
0 0 0 0 0 0 1 0 
0 0 0 0 0 0 0 1 
0 0 0 0 0 0 0 0 
*/