#include<stdio.h>
#include<stdlib.h>
#define Maxn 10 // 图中顶点数
#define Maxe 10 // 图中边数
typedef struct graph{
char vex[Maxn]; // 顶点表
int arcs[Maxe][Maxe]; // 邻接矩阵
int VexNum,ArcNum; //当前顶点 边数
}Graph,*Ptrl_Graph;
//无向图的邻接矩阵创建
void CreateW(Ptrl_Graph &g)
{
printf("请输入顶点数VexN:\n");
scanf("%d",&g->VexNum);
getchar();
printf("请输入边数ArcN:\n");
scanf("%d",&g->ArcNum);
printf("输入顶点集:\n");
for(int i = 0;i<g->VexNum;i++){
scanf("%c",&g->vex[i]);
getchar(); //吃空格
}
for(int i=0;i<g->VexNum;i++){
printf("%c ",g->vex[i]);
}
printf("\n");
printf("顶点表初始化完成\n");
int i, j, k;
for (i=0; i<g->VexNum; i++ )
for (j=0; j<g->VexNum; j++)
g->arcs[i][j]=0; //将邻接矩阵初始化为0
printf("邻接矩阵初始化完成\n");
for (k=1;k<=g->ArcNum; k++)
{
printf("第%d条边的位置:\n",k);
printf("输入边的下标位置(i j):\n");
scanf("%d %d",&i,&j);
g->arcs[i][j] = 1; //建立边
g->arcs[j][i] = 1; //无向图对称矩阵
// printf("请输入两个相连的顶点(A B):\n");
// char x,y;
// int count1=0,count2=0;
// scanf("%c",&x);
// getchar();
// scanf("%c",&y);
// getchar();
// //输入两个相连的边 去顶点表找
// for(i = 0;i<g->VexNum;i++){
// if(x == g->vex[i])
// {
// count1 = i;
// break;
// }
// }
// for(j = 0;j<g->VexNum;j++){
// if( y == g->vex[j])
// {
// count2 = j;
// break;
// }
// }
// g->arcs[count1][count2] = 1;
// g->arcs[count2][count1] = 1;
}
}
//有向图的邻接矩阵
void CreateY(Ptrl_Graph &g)
{ int i;
printf("请输入顶点数VexN:\n");
scanf("%d",&g->VexNum);
printf("请输入边数ArcN:\n");
scanf("%d",&g->ArcNum);
printf("输入顶点集:");
for(i = 0;i<g->VexNum;i++){
scanf("%c",g->vex[i]);
getchar();//吃空格
}
printf("顶点表初始化完成\n");
int j, k;
for (i=0; i<=g->VexNum; i++ )
for (j=0; j<=g->ArcNum; j++)
g->arcs[i][j]=0; //将邻接矩阵初始化为0
printf("邻接矩阵初始化完成\n");
for (k=1; k<=g->ArcNum; k++)
{
printf("第%d条边的位置:\n",k);
printf("输入边的下标位置(i,j):\n");
scanf("%d %d",&i,&j);
g->arcs[i][j] = 1; //建立边
//g.arcs[j][i] = 1; //无向图对称矩阵
}
}
void Print_Vex(Ptrl_Graph g){
printf("顶点表信息:\n");
int i;
for(i=0;i<g->VexNum;i++)
printf("%c ",g->vex[i]);
printf("\n");
}
void printArr(Ptrl_Graph &g){
int i,j;
for(i=0;i<g->VexNum;i++){
for(j=0;j<g->VexNum;j++){
printf("%d ",g->arcs[i][j]);//cout<<g.arcs[i][j]<<" ";
}
printf("\n");
}
}
//int Findth(Ptrl_Graph g,char v){
// int i = 0;
// for(i=0;i<g->VexNum;i++){
// if(v == g->vex[i])
// return i;
// }
//}
int visited[Maxn] = {0};
//深度优先遍历无向图
void DFS_AM(Ptrl_Graph g, int v){ //v 表示下标
printf("%c ",g->vex[v]);
visited[v] = 1; //标记访问记录
for(int w = 0; w < g->VexNum; w++){
if((g->arcs[v][w] != 0) && (!visited[w])){
DFS_AM(g,w);
}
}
}
int main(){
Ptrl_Graph G = (Ptrl_Graph)malloc(sizeof(Graph));
CreateW(G);
printArr(G);
Print_Vex(G);
DFS_AM(G,0);
}