public class Graph<T> { protected final int MAXSIZE=10; //邻接矩阵可以表示的最大顶点数 protected final int MAX=999; //在网中，表示没有联系（权值无穷大） protected T[] V;//顶点信息 protected int[][] arcs;//邻接矩阵 protected int e;//边数 Protected int n;//顶点数 public Graph(){ V =(T[]) new Object[MAXSIZE]; arcs=new int[MAXSIZE][MAXSIZE]; } public void CreateAdj(){ //创建无向图的邻接矩阵 // 补充代码... ... } // 在图中查找顶点v,找到后返回其在顶点数组中的索引号， // 若不存在，返回-1 public int LocateVex(T v){ // 补充代码... ... return -1; } public void DisplayAdjMatrix(){ //在屏幕上显示图G的邻接矩阵表示 // 补充代码... ... } }

这是一个泛型类 Graph<T>，表示一个图。其中包含邻接矩阵表示法所需要的顶点信息数组 V，邻接矩阵数组 arcs，边数 e 和顶点数 n。MAXSIZE 和 MAX 是常量，分别表示邻接矩阵可以表示的最大顶点数和在网中表示没有联系的权值无穷大。

CreateAdj() 是一个方法，用于创建无向图的邻接矩阵。LocateVex(T v) 是一个方法，在图中查找顶点 v，找到后返回其在顶点数组中的索引号，若不存在，返回-1。DisplayAdjMatrix() 是一个方法，在屏幕上显示图 G 的邻接矩阵表示。

相关问题

class Graph { private: int V; // 图的顶点数 vector<vector<int>> adj; // 邻接表存储结构 显示[Error] '>>' should be '> >' within a nested template argument list

这是一个常见的编译错误，因为在C++中，">>" 连用会被解释为位运算符而不是模板参数列表的结束符号。解决方法是在 ">>" 之间加一个空格，即将 ">>" 改为 "> >"，或者使用 "typename" 关键字来指示这是一个类型而不是一个成员变量。例如：

class Graph {
private:
    int V;
    vector<vector<int> > adj; // 加空格解决问题
};

或者：

class Graph {
private:
    int V;
    vector<typename vector<int>::vector> adj; // 使用typename关键字
};

#include<iostream> #include<vector> #include<iterator> #include<limits.h> #include<string> using namespace std; int n; //顶点个数 vector<vector<int> >g; //g：图（graph）（用邻接矩阵（adjacent matrix）表示） int s; //s：源点（source） vector<bool>known; //known：各点是否知道最短路径 vector<int>dist; //dist：源点 s 到各点的最短路径长度 vector<int>pre; //prev 各点的最短路径的前一顶点 void Dijkstra() { //贪心算法 known.assign(n,false); dist.assign(n,INT_MAX); pre.resize(n); //初始化 known、dist、prev dist[s]=0; //初始化源点 s 到自身的路径 for(;;) { int min=INT_MAX,v=s; for(int i=0; i<n; ++i) if(!known[i]&&min>dist[i]) min=dist[i],v=i; //寻找未知的最短路径的顶点 v if(min==INT_MAX)break; //如果找不到，退出 known[v]=true; for(int w=0; w<n; ++w) //遍历所有 v 指向的顶点 w if(!known[w]&&g[v][w]<INT_MAX && dist[w]>dist[v]+g[v][w]) //调整顶点 w 的最短路径长度 dist 和最短路径的前一顶点 prev dist[w]=dist[v]+g[v][w],pre[w]=v; } } void Print_SP(int v) { if(v!=s)Print_SP(pre[v]); cout<<v<<" "; } int main() { n=5; g.assign(n,vector<int>(n,INT_MAX)); //构建图 g[0][1]=10; g[0][3]=30; g[0][4]=100; g[1][2]=50; g[2][4]=10; g[3][2]=20; g[3][4]=60; s=0; Dijkstra(); copy(dist.begin(),dist.end(),ostream_iterator<int>(cout," ")); cout<<endl; for(int i=0; i<n; ++i) if(dist[i]!=INT_MAX) { cout<<s<<"->"<<i<<":"; Print_SP(i); cout<<endl; } return 0; }每行代码什么意思

这段代码实现了Dijkstra算法，用于求解带权图中单源最短路径问题。下面是每行代码的具体意思：

#include<iostream> 
#include<vector> 
#include<iterator> 
#include<limits.h> 
#include<string> 

头文件的引入。

using namespace std; 

使用标准命名空间。

int n; //顶点个数 
vector<vector<int> >g; //g：图（graph）（用邻接矩阵（adjacent matrix）表示） 
int s; //s：源点（source） 
vector<bool>known; //known：各点是否知道最短路径 
vector<int>dist; //dist：源点 s 到各点的最短路径长度 
vector<int>pre; //prev 各点的最短路径的前一顶点 

定义了顶点个数、图、源点、各点是否知道最短路径、源点到各点的最短路径长度、各点的最短路径前一顶点等变量。

void Dijkstra() { //贪心算法 
    known.assign(n,false); 
    dist.assign(n,INT_MAX); 
    pre.resize(n); //初始化 known、dist、prev 
    dist[s]=0; //初始化源点 s 到自身的路径 
    for(;;) { 
        int min=INT_MAX,v=s; 
        for(int i=0; i<n; ++i) 
            if(!known[i]&&min>dist[i]) 
                min=dist[i],v=i; //寻找未知的最短路径的顶点 v 
        if(min==INT_MAX)break; //如果找不到，退出 
        known[v]=true; 
        for(int w=0; w<n; ++w) //遍历所有 v 指向的顶点 w 
            if(!known[w]&&g[v][w]<INT_MAX && dist[w]>dist[v]+g[v][w]) //调整顶点 w 的最短路径长度 dist 和最短路径的前一顶点 prev 
                dist[w]=dist[v]+g[v][w],pre[w]=v; 
    } 
} 

Dijkstra算法函数的实现。首先对known、dist、prev进行初始化，然后进行循环，每次找到未知的最短路径的顶点v，将其标记为已知，再遍历所有v指向的顶点w，调整顶点w的最短路径长度和最短路径的前一顶点prev。

void Print_SP(int v) { 
    if(v!=s)Print_SP(pre[v]); 
    cout<<v<<" "; 
} 

输出最短路径的函数实现。递归输出前一顶点的最短路径，然后输出当前顶点v。

int main() { 
    n=5; 
    g.assign(n,vector<int>(n,INT_MAX)); //构建图 
    g[0][1]=10; 
    g[0][3]=30; 
    g[0][4]=100; 
    g[1][2]=50; 
    g[2][4]=10; 
    g[3][2]=20; 
    g[3][4]=60; 
    s=0; 
    Dijkstra(); 
    copy(dist.begin(),dist.end(),ostream_iterator<int>(cout," ")); 
    cout<<endl; 
    for(int i=0; i<n; ++i) 
        if(dist[i]!=INT_MAX) { 
            cout<<s<<"->"<<i<<":"; 
            Print_SP(i); 
            cout<<endl; 
        } 
    return 0; 
} 

主函数的实现。初始化图，设置源点，调用Dijkstra函数求解最短路径，输出源点到各点的最短路径长度，逐个输出源点到每个顶点的最短路径及其长度。