#include "iostream.h"
#define MaxVerNum 100 //最大顶点数设为100
int Gtype=0; //图储存类型(0:有向邻接表(默认) 1:有向邻接矩阵 2:无向邻接矩阵)
int visited[MaxVerNum]; //顶点标志向(用于标记遍历时是否被访问过)
typedef char VertexType; //顶点类型
typedef int EdgeType; //边的权值类型
typedef struct{
//以邻接矩阵储存的图类型MGragh
VertexType vexs[MaxVerNum]; //顶点表
EdgeType edges[MaxVerNum][MaxVerNum]; //邻接矩阵，即边表
int n,e; //顶点数，边数
}MGraph;
typedef struct Node{
//定义边表结点
int adjvex; //邻接点域
struct Node *next; //指向下一个邻接点
//若要表示边上的信息，则应增加一个数据域info
}EdgeNode;
typedef struct vNode{
//定义顶点表结点
VertexType vertex; //顶点域
EdgeNode *firstedge; //边表头指针
}VertexNode;
typedef VertexNode AdjList[MaxVerNum]; //定义邻接表类型
typedef struct{
//以邻接表储存的图类型ALGraph
AdjList adjlist; //邻接表
int n,e; //顶点数，边数
}ALGraph;
void CreateMGraph(MGraph *G){ //建立一个有向图的邻接矩阵存储算法
//建立有向图G的邻接矩阵存储
int i,j,k;
cout<<"1.建立有向图(默认)"<<endl;
cout<<"2.建立无向图"<<endl;
cout<<"请选择:";
cin>>Gtype;
if (Gtype!=2) Gtype=1;
cout<<"请输入顶点数和边数(输入格式为:顶点数,边数):"<<endl;
cin>>G->n>>G->e; //输入顶点数和边数
cout<<"请输入顶点信息(输入格式为:顶点号<CR>):"<<endl;
for (i=0;i<G->n;i++)
cin>>G->vexs[i]; //输入顶点信息,建立顶点表
for (i=0;i<G->n;i++)
for (i=0;j<G->n;j++)
G->edges[i][j]=0; //初始化邻接矩阵
cout<<"请输入每条边对应的两个顶点的序号(输入格式为:i,j):"<<endl;
for (k=0;k<G->e;k++){
cin>>i>>j; //输入e条边,建立邻接矩阵
if (Gtype==2) G->edges[i][j]=1; //若_bk==2,则建立无向图的邻接矩阵存储
}
}//CreateMGraph
void CreateALGraph(ALGraph *G){
//建立有向图的邻接表储存
int i,j,k;
EdgeNode *s;
cout<<"请输入顶点数和边数(输入格式为:顶点数,边数):"<<endl;
cin>>G->n>>G->e; //读入顶点数和边数
cout<<"请输入顶点信息(输入格式为:顶点号<CR>):"<<endl;
for (i=0;i< G->n;i++){ //建立有n个顶点的顶点表
cin>>G->adjlist[i].vertex; //读入顶点信息
G->adjlist[i].firstedge=NULL; //顶点的边表头指针设为空
}
cout<<"请输入每条边对应的两个顶点的序号(输入格式为:i,j):"<<endl;
for (k=0;k< G->e;k++){ //建立边表
cin>>i>>j; //读入边<Vi,Vj>的定点对应序号
s=new EdgeNode; //生成新边表结点s
s->adjvex=j; //邻接点序号为j
s->next=G->adjlist[i].firstedge; //将新边表结点s插入到顶点Vi的边表头部
G->adjlist[i].firstedge=s;
}
}//CreateAlGraph
void DFSAL(ALGraph *G,int i){
//以Vi为出发点对邻接表存储的图G,进行DFS(Depth_First Search)搜索
EdgeNode *p;
cout<<"Visit vertex:V"<<G->adjlist[i].vertex<<endl; //访问顶点Vi
visited[i]=1; //标记Vi以访问
p=G->adjlist[i].firstedge; //取Vi边表头指针
while (p) { //依次搜索Vi的邻接点Vj,j=p->adjvex
if (!visited[p->adjvex]) DFSAL(G,p->adjvex);//若Vj尚未访问，则以Vj为出发点向纵深搜索
p=p->next; //找Vi的下一个邻接点
}
}//DFSAL
void DFSTraverseAL(ALGraph *G){
//深度优先遍历以邻接表储存的图G
int i;
for (i=0;i< G->n;i++)
visited[i]=0; //标志向量初始化
for (i=0;i< G->n;i++)
if (!visited[i])
DFSAL(G,i); //若Vi未访问过，从Vi开始DFS搜索
}//DFSTraveseAL
