#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define OVERFLOW -2
#define ERROR 0
#define OK 1
#define Length (q.rear+1)%QUEUE_MAXSIZE //队满
#define MAX_VERtEX_NUM 20 //顶点的最大个数
#define QUEUE_MAXSIZE 100
#define Queue_increment 10
typedef struct QNode{
int data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
QueuePtr front; //队头指针
QueuePtr rear; //队尾指针
}LinkQueue;
//-------------------------------------------------------------------------------------------------------------
typedef struct {
int adj; //对于无权图，用 1 或 0 表示是否相邻；对于带权图，直接为权值。
}ArcCell,AdjMatrix[MAX_VERtEX_NUM][MAX_VERtEX_NUM];
typedef struct {
char vexs[MAX_VERtEX_NUM]; //存储图中顶点数据
AdjMatrix arcs; //二维数组，记录顶点之间的关系
int vexnum,arcnum; //记录图的顶点数和弧（边）数
}MGraph;
//---------------------------------------------------------------------------
// 矩阵打印关系
void PrintGrapth(MGraph &G){
int i,j;
for (i = 0; i < G.vexnum;++i){
printf("%d",G.vexs[i]);
}
printf("顶点间的关系:\n");
for (i = 0; i < G.vexnum; ++i){
for (j = 0; j < G.vexnum; ++j){
printf("%d ", G.arcs[i][j].adj);
}
printf("\n");
}
}
//---------------------------------------------------------------------------
//根据顶点本身数据，判断出顶点在二维数组中的位置
int LocateVex(MGraph &G,int v){
//遍历一维数组，找到变量v
for (int i=0; i<G.vexnum; ++i) {
if (G.vexs[i]==v) {
return i;
}
}
return -1; //如果找不到，返回-1
}
//构造无向图
int CreateDN(MGraph &G){
int i,j,k,m,n,x;int v1,v2;//char a[2];
printf("请输入总顶点数n和总边数:");
scanf("%d",&(G.vexnum)); // 输入总顶点数，总边数
scanf("%d",&(G.arcnum));
x=G.vexnum;
if(G.vexnum<20 && G.arcnum<=(x*(x-1)/2)){
printf("请(回车)输入 %d 个顶点的值：\n",G.vexnum);
for (i=0; i<G.vexnum; i++) { // 循环输入顶点值
scanf("%d",&(G.vexs[i]));
}
for (i=0; i<G.vexnum; ++i) { // 初始化邻接矩阵
for (j=0; j<G.vexnum; ++j) {
G.arcs[i][j].adj=0;
}
}
printf("\n请实现 %d 条边的连接：\n",G.arcnum);
for (k=0;k<G.arcnum; ++k) { // 构造邻接矩阵
printf("\n请输入哪'两个'顶点要进行连接边：");
fflush(stdin);
scanf("%d",&v1);
n=LocateVex(G, v1); //定位顶点
scanf("%d",&v2);
m=LocateVex(G, v2);
while (m==-1||n==-1) {
printf("没有这样的顶点,请重新输入：");
fflush(stdin);
scanf("%d",&v1);
n=LocateVex(G, v1); //定位顶点
scanf("%d",&v2);
m=LocateVex(G, v2);
// if(m!=-1&&n!=-1){break; }
}
while(G.arcs[n][m].adj==1){
printf("\n!!!两顶点已经被连接!!!\n");
printf("请重新输入两顶点：");
fflush(stdin);
scanf("%d",&v1);
n=LocateVex(G, v1); //定位顶点
scanf("%d",&v2);
m=LocateVex(G, v2);
// if(G.arcs[n][m].adj!=1){break; }
while (m==-1||n==-1) {
printf("没有这样的顶点,请重新输入：");
fflush(stdin);
scanf("%d",&v1);
n=LocateVex(G, v1); //定位顶点
scanf("%d",&v2);
m=LocateVex(G, v2);
// if(m!=-1&&n!=-1){break; }
}
}
G.arcs[n][m].adj=G.arcs[m][n].adj=1; //无向图的二阶矩阵沿主对角线对称
}
}else{
printf("\n!!!您输入的总顶点数 大于 20 了或者是输入的总边数 不符合 n(n-1)/2 !!!\n");
CreateDN(G);
}
return OK;
}
//-------------------------------------------------------------------------------------------------
int visited[MAX_VERtEX_NUM]; // 辅助数组
// 遍历节点
void DFS(MGraph &G,int v){
int j;
printf("访问到顶点:%d\n\n",G.vexs[v]); // 表示顶点被访问过了
visited[v]=1;
for(j=0;j<G.vexnum;++j){
if(G.arcs[v][j].adj!=0 && visited[j]==0){ // 如果有邻接点则继续递归
DFS(G,j);
}
}
}
// 顶点的非连通图的深度遍历
int DFSTraverse(MGraph &G){
int n=0,v,x,j,m;
for(v=0;v<G.vexnum;v++) visited[v]=0; // 把所有的标记置为0
printf("\n请输入遍历起点：\n");
scanf("%d",&x);
printf("遍历起点为：%d \n",x);
m = LocateVex(G,x);
if(m==-1){
printf("\n！！！您输入的起点不在顶点表内！！！\n");
DFSTraverse(G);
}
//n=LocateVex(G,x);
visited[m]=1;
for(j=0;j<G.vexnum;++j){
if(G.arcs[n][j].adj!=0 && visited[j]==0){ // 如果有邻接点则继续递归
DFS(G,j);
}
}
//DFS(G,m);
for(v=0;v<G.vexnum;++v){ // 判断是否还有没有被遍历的图
if(visited[v]==0){
DFS(G,v); // 调用DFS遍历单个图
}
}
return OK;
}
//-------------------------------------------------------------------------------------
//构建空队
int InitQueue_Q(LinkQueue &Q){
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front){
printf("队存储空间分配失败！！");
exit(OVERFLOW);
}
Q.front->next=NULL;
return OK;
}
//队尾插入元素
int EnQueue_Q(LinkQueue &Q,int &e){
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
if(!p){ //存储分配失败
printf("队存储空间分配失败!!!\n");
exit(OVERFLOW);
}
p->data=e; //e赋值给p指向的空间
p->next=NULL; //p指向NULL
Q.rear->next=p;
Q.rear=p; //将p赋给Q
return OK;
}
// 删除队列头元素
int DeQueue_Q(LinkQueue &Q,int &e){
QNode *P;
if(Q.front==Q.rear) return ERROR;
P=Q.front->next ;
e=P->data;
Q.front ->next =P->next; //将原对头的后继p->next赋值给头结点后继
if(Q.rear ==P) //当队列中只有一个元素时，q->rear指向头结点
Q.rear =Q.front;
free(P);
return OK;
}
// 队判空
int QueueEmpty(LinkQueue Q)
{
if(Q.front->next==NULL)
return ERROR;
else
return OK;
}
//-----------------------------------------------------------------------------------------------------
// BFSTraversed调用BFS每一个节点都被访问
void BFS(MGraph &G,int i){
int j;
LinkQueue Q;
InitQueue_Q(Q);
if(visited[i]==0){ //未访问过该顶点
printf("访问到顶点：%d\n\n",G.vexs[i]);
visited[i]=1; // 置1
EnQueue_Q(Q,i); //将其入队列
while(QueueEmpty(Q)){ // 循环队不为空QueueEmpty返回1
DeQueue_Q(Q,i); //将队头元素出队列，置为v
for(j=0;j<G.vexnum;j++){
if(G.arcs[i][j].adj!=0 &&visited[j]==0){ //未访问过的邻接点
printf("顶点走到的值：%d\n\n",G.vexs[j]); // i 为v中未被访问的邻接点
visited[j]=1; // 访问置1
EnQueue_Q(Q,j); //入队列
}
}
}
}
}
// 广度优先遍历图
int BFSTraverse(MGraph &G)
{
int i,v,j,m;char x;
LinkQueue Q;
InitQueue_Q(Q);
for(v=0;v<G.vexnum;v++){ // 辅助数组置零
visited[v]=0;
}
printf("\n请输入遍历起点：\n");
scanf("%d",&x);
printf("遍历起点为：%d \n",x);
m=LocateVex(G,x);
if(m==-1){
printf("\n！！！您输入的起点不在顶点表内！！！\n");
BFSTraverse(G);
}
visited[m]=1;
EnQueue_Q(Q,m); //将其入队列
while(QueueEmpty(Q)){ // 循环队不为空QueueEmpty返回1
DeQueue_Q(Q,m); //将队头元素出队列，置为v
for(j=0;j<G.vexnum;j++){
if(G.arcs[m][j].adj!=0 &&visited[j]==0){ //未访问过的邻接点
printf("顶点走到的值：%d\n\n",G.vexs[j]); // i 为v中未被访问的邻接点
visited[j]=1; // 访问置1
EnQueue_Q(Q,j); //入队列
}
}
}
for(i=0;i<G.vexnum;i++){ // 保证所有节点被访问
BFS(G, i );
}
return OK;
}
//操作菜单
void OperateMenu(){
printf("\n\n--------------请选择元素处理方式---------\n\n");
printf("！！！！！注：测试程序过程中，输入应全为数字！！！！！\n\n");
printf("0> :退出\n\n");
printf("1>: 深度遍历\n\n");
printf("2>: 广度遍历\n\n");
printf("3>: 输出邻接矩阵\n\n");
printf("(注：选择过程中应为数字)\n\n");
printf("请选择对元素的处理：");
}
void main() {
MGraph G;//建立一个图的变量
int w=0,k,boo=1;
printf("请用户选择创建图 或 退出程序：\n\n");
printf("注：程序测试过程中输入应全为数字\n\n");
printf("创建图请输入：'1'\n\n");
printf("退出请选择'0'或 其它！！\n\n");
printf("请选择：");
scanf("%d",&w);
if(w==1){
boo=CreateDN(G);
if(boo)
printf("\n建图成功！！！\n");
else
printf("\n建图失败！！！\n");
OperateMenu();
scanf("%d",&k);
while(k){
switch(k){
case 0:break;
case 1:boo=DFSTraverse(G); // 深度遍历
if(boo)
printf("\n深度遍历成功！！！\n");
else
printf("\n深度遍历失败！！！\n");
break;
case 2:boo=BFSTraverse(G); // 广度遍历
if(boo)
printf("\n广度遍历成功！！！\n");
else
printf("\n广度遍历失败！！！\n");
break;
case 3:PrintGrapth(G);
}
OperateMenu();
scanf("%d",&k);
}
}
}