#ifndef _GRAPH_MARTIX_H

#define _GRAPH_MARTIX_H

#include <iostream>

using namespace std;

const int MaxGrzphSize=;             //图的最大顶点个数

const int MaxWeight=;               //图中允许的最大权值

class Graph_Martix

{

private:

int edge[][];

int graphsize;

public:

Graph_Martix();

int GetWeight(const int v1,const int v2);

int GetFirstNeighbor(const int v);

void GetAllNeighbor(const int v);

int GetNextNeighbor(const int v1,const int v2);

void DepthFirstSearch(int v);

void RDFS(const int v,int *visited);

};

#endif

#include "Graph_Martix.h"

Graph_Martix::Graph_Martix() {

    cout<<"请输入邻接矩阵节点个数"<<endl;

    cin>>graphsize;

    cout<<"请输入各个节点之间的权值:"<<endl;

    for(int i=;i<graphsize;i++){

        for(int j=;j<graphsize;j++){

            cin>>edge[i][j];

        }

    }

}

int Graph_Martix::GetWeight(const int v1,const int v2){

    if(v1==-||v2==-)

        return -;

    else

        return edge[v1][v2];

}

int Graph_Martix::GetFirstNeighbor(const int v){

    if (v==-) return -;

    for(int i=;i<graphsize;i++){

        if(edge[v][i]>&&edge[v][i]<MaxWeight)

            return i;

    }

    return -;//若v没有邻接顶点，则返回-1.

}

void Graph_Martix::GetAllNeighbor(const int v) {

    if(v==-) return;

    for(int i=;i<graphsize;i++){

        if(edge[v][i]>&&edge[v][i]<MaxWeight){

            cout<<i;

        }

    }

}

int Graph_Martix::GetNextNeighbor(const int v1,const int v2) {

    if(v1==-||v2==-) return -;

    for(int i=v2+;i<graphsize;i++)

        if(edge[v1][i]>&&edge[v1][i]<MaxWeight)

            return i;

        return -;           //若在v2之后没有与v1邻接的顶点，则返回-1.

}

void Graph_Martix::RDFS(const int v,int *visited)

{

 cout<<v<<" ";                                   //输出v的序号

    visited[v]=;                                   //说明v已被访问过

 int w=GetFirstNeighbor(v);                      //取得v的第一个邻接顶点的序号

 while(w!=-)                                    //若存在顶点w

 {

  if(!visited[w])                             //若w未被访问过，从w递归访问

   RDFS(w,visited);

  w=GetNextNeighbor(v,w);                     //w为v关于w的下一个邻接顶点

 }

}

void Graph_Martix::DepthFirstSearch(int v)

{

 int *visited=new int[graphsize];               //为辅助数组申请空间

 for(int k=;k<graphsize;k++)

  visited[k]=;

 RDFS(v,visited);                               //从序号为0的节点出发，深度优先遍历

 delete[]visited;                               //释放辅助数组空间

}

#include <iostream>

#include "Graph_Martix.h"

#include "Graph_Martix.cpp"

using namespace std;

int main(){

 Graph_Martix a;

 int b,c,d,e,f,g;

 while(){

 cout<<"请输入要执行的操作"<<endl;

 cout<<"0.退出"<<endl;

 cout<<"1.获取指定权值"<<endl;

 cout<<"2.获取该点全部邻接顶点"<<endl;

 cout<<"3.深度遍历"<<endl;

 cin>>c;

 switch(c){

 case :

  exit();

  break;

 case :

  cout<<"请输入该边的起点，终点"<<endl;

  cin>>d>>e;

  b=a.GetWeight(d,e);

  if(b==-){

   cout<<"边不存在"<<endl;

  }

  cout<<b<<endl;

  break;

 case :

  cout<<"请输入顶点序号"<<endl;

  cin>>f;

  a.GetAllNeighbor(f);

  break;

 case :

  cout<<"请输入选择哪个顶点开始深度遍历"<<endl;

  cin>>g;

  a.DepthFirstSearch(g);

  cout<<endl;

  break;}}

 return ;

}