【邻接矩阵】64 邻接矩阵：顶点u的第一个邻接顶点

【邻接矩阵】64 邻接矩阵：顶点u的第一个邻接顶点

问题描述 :

目的：使用C++模板设计并逐步完善图的邻接矩阵抽象数据类型（ADT）。

内容：

（1）请参照图的邻接矩阵模板类原型，设计并逐步完善图的邻接矩阵ADT。（由于该环境目前仅支持单文件的编译，故将所有内容都集中在一个源文件内。在实际的设计中，推荐将抽象类及对应的派生类分别放在单独的头文件中。）

（2）设计并实现一个算法，在已存在的图中返回G中指定顶点u的第一个邻接顶点的位序（顶点集）。若顶点在G中没有邻接顶点，则返回-1。图的存储结构采用邻接矩阵。将其加入到ADT中。

 

函数原型：

int GetFirstAdjVex(int u, int &v); //返回G中指定顶点u的第一个邻接顶点的位序（顶点集）。若顶点在G中没有邻接顶点，则返回-1

 

注意：DG（有向图）, DN（有向网）, UDG（无向图）, UDN（无向网）

 

图的邻接矩阵模板类原型参考如下：

 

template <class TypeOfVer, class TypeOfEdge>

class adjmatrix_graph{

    private:

       int Vers;        //顶点数 

       int Edges;       //边数 

       TypeOfEdge **edge;  //存放邻接矩阵（TypeOfEdge表示顶点关系类型。对于无权图，用1或0，表示相邻否；对于带权图，则为权值类型） 

       TypeOfVer *ver;    //存放结点值 

       TypeOfEdge noEdge;  //邻接矩阵中的∞的表示值

       string GraphKind;   //图的种类标志 

        

       bool DFS(int u, int &num, int visited[]); //DFS遍历（递归部分）

 

    public:

       adjmatrix_graph( const string &kd, int vSize, const TypeOfVer d[], const TypeOfEdge noEdgeFlag); //构造函数构造一个只有结点没有边的图。4个参数的含义：图的类型、结点数、结点值和邻接矩阵中表示结点间没有边的标记（无权图：0，有权图：输入参数定） 

       adjmatrix_graph( const string &kd, int vSize, int eSize, const TypeOfVer d[], int **e); //构造函数构造一个无权图。5个参数的含义：图的类型、结点数、边数、结点集和边集 

       adjmatrix_graph( const string &kd, int vSize, int eSize, const TypeOfEdge noEdgeFlag, const TypeOfVer d[], int **e, const TypeOfEdge w[]); //构造函数构造一个有权图。7个参数的含义：图的类型、结点数、边数、无边标记、结点集、边集、权集

       bool GraphisEmpty() { return Vers == 0; }  //判断图空否

       string GetGraphKind(){ return GraphKind; }

       bool GetVer(int u, TypeOfVer &data); //取得G中指定顶点的值 

       int GetFirstAdjVex(int u, int &v); //返回G中指定顶点u的第一个邻接顶点的位序（顶点集）。若顶点在G中没有邻接顶点，则返回-1 

       int GetNextAdjVex(int u, int v, int &w); //返回G中指定顶点u的下一个邻接顶点（相对于v）的位序（顶点集）。若顶点在G中没有邻接顶点，则返回-1

       bool PutVer(int u, TypeOfVer data); //对G中指定顶点赋值 

       bool InsertVer(const TypeOfVer &data); //往G中添加一个顶点 

       int LocateVer(TypeOfVer data); //返回G中指定顶点的位置 

       bool PrintMatrix();  //输出邻接矩阵 

       int GetVerNum(){ return Vers;}    //取得当前顶点数 

       int GetEdgeNum(){ return Edges;}  //取得当前边数 

       bool Insert_Edge(int u, int v); //无权图插入一条边

       bool Insert_Edge(int u, int v, TypeOfEdge w); //有权图插入一条边

       bool DeleteVer(const TypeOfVer &data); //往G中删除一个顶点

       bool Delete_Edge(int u, int v); //无权图删除一条边 

       bool Delete_Edge(int u, int v, TypeOfEdge w); //有权图删除一条边 

       void DFS_Traverse(int u); //DFS遍历（外壳部分）

       void BFS_Traverse(int u); //BFS遍历

       ~adjmatrix_graph(); //析构函数 

};

 

输入说明 :

建图的输入数据格式参见建图的算法说明。

 

第一行：图的类型

第二行：结点数

第三行：结点集

第四行：边数

第五行：边集

第六行：指定顶点的位序

 

输出说明 :

第一行：顶点集

空行

第二行：邻接矩阵

空行

第三行：第一个邻接顶点的位序（如无邻接顶点，则输出-1）

输入范例 :

DG
6
A B C D E F
6
0 1
0 2
0 3
1 4
2 4
3 5
0

输出范例 :

A B C D E F

0 1 1 1 0 0 
0 0 0 0 1 0 
0 0 0 0 1 0 
0 0 0 0 0 1 
0 0 0 0 0 0 
0 0 0 0 0 0 

1

解题思路：

解题代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <sstream>
#include <stack>
#include <map>
#include <ctime>
#include <array>
#include <set>
using namespace std;template <class TypeOfVer, class TypeOfEdge>//节点数值，边数值
class adjmatrix_graph {
private:int Vers;        //顶点(节点)数 int Edges;       //边数 //存放邻接矩阵（TypeOfEdge表示顶点关系类型。对于无权图，用1或0，表示相邻否；对于带权图，则为权值类型） vector<vector<TypeOfEdge> >edge;//邻接矩阵TypeOfEdge noEdge;  //邻接矩阵中的∞的表示值vector<TypeOfVer> ver;    //存放结点值 string GraphKind;   //图的种类标志 bool have_dir = false, have_w = false;//图类型参数//bool DFS(int u, int& num, int visited[]); //DFS遍历（递归部分）
public:adjmatrix_graph(){Vers = 0;Edges = 0;edge.clear();ver.clear();noEdge = 0;}~adjmatrix_graph(){;}//全自动输入bool Auto_input(bool need_emp){//DG（有向图）, DN（有向网）, UDG（无向图）, UDN（无向网）/*第一行：图的类型  DN UDN第二行：结点数第三行：结点集第四行：无边标记第五行：边数第六行：边集第七行：权集*//*第一行：图的类型  DG UDG第二行：结点数 第三行：结点集第四行：边数第五行：边集*/cin >> GraphKind;//图的类型 cin >> Vers;//结点数size(Vers);for (int i = 0; i < Vers; i++)//结点集cin >> ver[i];if (need_emp)cin >> noEdge;//无边标记vector<TypeOfEdge> line;//邻接矩阵初始化for (int j = 0; j < Vers; j++){for (int i = 0; i < Vers; i++)line.push_back(noEdge);edge.push_back(line);}cin >> Edges;//边数vector<int> x_p, y_p, w_p;for (int i = 0; i < Edges; i++){int c_x, c_y;cin >> c_x >> c_y;x_p.push_back(c_x);y_p.push_back(c_y);}//图的类型识别if (GraphKind == "DG")//DG（有向图）have_dir = true, have_w = false;if (GraphKind == "DN")//DN（有向网）have_dir = true, have_w = true;if (GraphKind == "UDG")//UDG（无向图）have_dir = false, have_w = false;if (GraphKind == "UDN")//UDN（无向网）have_dir = false, have_w = true;if(have_w)for (int i = 0; i < Edges; i++){int c_w;cin >> c_w;w_p.push_back(c_w);}for (int i = 0; i < Edges; i++){if (have_dir == false)//无向图操作{if (have_w == true)//带权值的网的操作edge[x_p[i]][y_p[i]] = edge[y_p[i]][x_p[i]] = w_p[i];else//无权值操作edge[x_p[i]][y_p[i]] = edge[y_p[i]][x_p[i]] = 1;}else{if (have_w == true)//带权值的网的操作edge[x_p[i]][y_p[i]] = w_p[i];else//无权值操作edge[x_p[i]][y_p[i]] = 1;}}return 1;}//输出邻接矩阵 bool PrintMatrix(){int i, j;for (i = 0; i < Vers; i++){for (j = 0; j < Vers-1; j++)cout << edge[i][j] << " ";cout << edge[i][j]<<" ";cout << endl;}return 1;}//判断图空否bool GraphisEmpty(void){return Vers == 0;}//图的类型string GetGraphKind(void){return GraphKind;}//获得顶点集vector<TypeOfVer> GetGraph_Point(void){return ver;}//往G中添加一个顶点 bool InsertVer(const TypeOfVer& data){ver.push_back(data);vector<TypeOfEdge> line;//邻接矩阵一行for (int j = 0; j < Vers; j++){edge[j].push_back(noEdge);}for (int j = 0; j <= Vers; j++){line.push_back(noEdge);}edge.push_back(line);Vers++;return 1;}//返回G中指定顶点的位置 int LocateVer(TypeOfVer data){int i = 0;for (i = 0; i < ver.size(); i++)if (ver[i] == data)return i;return -1;}//删除一个顶点bool Delete_Point(const TypeOfVer& data){int i, j;for (i = 0; i < Vers; i++)if (ver[i] == data){ase(ver.begin() + i);break;}if (i == Vers)//没有找到return 0;ase(edge.begin() + i);for (j = 0; j < Vers; j++)edge[j].erase(edge[j].begin() + i);return 1;}//取得当前边数 int GetEdgeNum(void){return Edges;}//取得当前顶点数 int GetVerNum(){return Vers;}//图删除一条边 bool Delete_Edge(int u, int v){if (have_dir == true)if (edge[u][v] != noEdge){edge[u][v] = noEdge;Edges--;return true;}elsereturn false;else{if (edge[u][v] != noEdge && edge[v][u] != noEdge){edge[u][v] = noEdge;edge[v][u] = noEdge;Edges--;return true;}elsereturn false;}return false;}//取得G中指定顶点的入度int search_PointIn(int p) {if (have_dir == false)//无向图无入度return -1;if (p < 0 || p >= Vers)return -1;int i,ans=0;for (i = 0; i < Vers; i++)if (edge[i][p] != noEdge)ans++;return ans;}int search_PointOut(int p)//取得G中指定顶点的出度{if (p < 0 || p >= Vers)return -1;int i, ans = 0;for (i = 0; i < Vers; i++)if (edge[p][i] != noEdge)ans++;return ans;}bool Look_adjacent(int u, int v){if (u < 0 || u >= Vers)return false;if (v < 0 || v >= Vers)return false;if (u == v)return false;if (edge[u][v] != noEdge)return true;elsereturn false;}int Look_firstPoint(int p)//获取第一个临界顶点位序{if (p < 0 || p >= Vers)return -1;for (int i = 0; i < Vers; i++)if (edge[p][i] != noEdge)return i;return -1;}//+++++++++++++++++++======分割线=====+++++++++++++++++++++++++++++//返回G中指定顶点u的第一个邻接顶点的位序（顶点集）。若顶点在G中没有邻接顶点，则返回-1 int GetFirstAdjVex(int u, int& v){int p;return p;}//返回G中指定顶点u的下一个邻接顶点（相对于v）的位序（顶点集）。若顶点在G中没有邻接顶点，则返回-1int GetNextAdjVex(int u, int v, int& w){return -1;}//对G中指定顶点赋值 bool PutVer(int u, TypeOfVer data){return 1;}//无权图插入一条边bool Insert_Edge(int u, int v){return 1;}//有权图插入一条边bool Insert_Edge(int u, int v, TypeOfEdge w){return 1;}//void DFS_Traverse(int u); //DFS遍历（外壳部分）//void BFS_Traverse(int u); //BFS遍历};
int main()
{int i;adjmatrix_graph<char, int> a;a.Auto_input(0);int p;cin >> p;//cout << a.GetGraphKind() << endl;//输出类型//输出顶点集----------------------vector<char> ans;ans = a.GetGraph_Point();for (i = 0; i < ans.size() - 1; i++)cout << ans[i] << " ";cout << ans[i] << endl;//-------------------------------cout << endl;a.PrintMatrix();cout << endl;cout << a.Look_firstPoint(p) << endl;return 0;
}