图的应用
（1）创建无向图的邻接矩阵存储结构
（2）输出无向图的邻接矩阵表示
（3）输入任意两个结点，判断是否有边存在
（4）输入任意一个结点，求顶点的度
（5）根据邻接矩阵求该无向图中边的数目
（6）实现图的深度优先遍历
（7）实现图的广度优先遍历
#include<stdio.h>
#include<stdlib.h>
#define MAX 100 // 图中最大顶点个数
//建立邻接矩阵
typedef struct{
int n,e; // 顶点数、边数
char vexs[MAX]; // 顶点数组
int edges[MAX][MAX]; // 边的邻接矩阵
}MGraph;
/*建立邻接矩阵*/
void CreateMGraph(MGraph *G){
int i,j,k;
char ch1,ch2; // 输入的顶点
printf("请输入顶点数：");
scanf("%d",&G->n);
printf("请输入边数：");
scanf("%d",&G->e);
printf("请输入各顶点信息(每个顶点以回车键作为结束)：\n");
for(i=0; i<G->n; i++){
getchar();
printf("请输入%d个顶点：",i+1);
scanf("%c",&G->vexs[i]);
}
for(i=0; i<G->n; i++)
for(j=0;j<G->n;j++)
G->edges[i][j] = 0; // 将邻接矩阵元素全部置0
for(k=0;k<G->e;k++){
getchar();
printf("建立第%d条边 (两顶点之间用空格分开)",k+1);
scanf("%c %c",&ch1,&ch2);
for(i=0; i<G->n; i++)
for(j=0;j<G->n;j++)
if(ch1==G->vexs[i] && ch2==G->vexs[j]){
G->edges[i][j] = 1;
G->edges[j][i] = 1; //加上该语句为无向邻接矩阵，去掉为有向邻接矩阵
}
}
}
/*输出邻接矩阵*/
void DispMGraph(MGraph G){
int i,j;
printf("\n图的邻接矩阵：\n");
for(i=0;i<G.n;i++){
for(j=0;j<G.n;j++)
printf("%5d",G.edges[i][j]);
printf("\n");
}
}
// 判断两个结点之间是否有边存在
int EdgeMGraph(MGraph *G, char m, char n)
{
int x=0,y=0,num=0;
while(num++ != G->n) //遍历数组找到两个节点序号
{
if(G->vexs[num] == n)
x = num;
if(G->vexs[num] == m)
y = num;
}
return G->edges[x][y];
}
//求任意一个顶点的度
int DegreeMGraph(MGraph *G, char m){
int i=0,j,sum=0;
while(G->vexs[i]!=m && i<G->n) //i 为 m的下标
i++;
if(i<G->n)
{
for(j=0;j<G->n;j++)
sum += G->edges[i][j];
}
return sum;
}
//根据邻接矩阵求该无向图中边的数目
int AllMGraph(MGraph *G){
int x=0,y=0,bian=0;
for(x=0; x<G->n; x++)
for(y=0; y<G->n; y++)
if(G->edges[x][y])
bian++;
return bian/2;
}
//建立邻接表 (结构体嵌套)
typedef char VertexType;
int visited[MAX];
typedef struct node{ //定义边表节点
int adjvex; //邻接点域
struct node *next; //指向下一邻接点的指针域
}EdgeNode;
typedef struct vexnode{ //定义顶点表节点
VertexType data; //顶点域
EdgeNode *firstedge; //指向第一条边节点
}VHeadNode;
typedef struct{
VHeadNode adjlist[MAX]; //邻接表头节点数组
int n,e; //顶点数、边数
}AdjList;
//建立图的邻接表的算法
//可以实现根据参数flag的值为0或1来选择生成无向图还是有向图
void CreateAGraph(AdjList *g, int flag){ //生成无向图的邻接表函数
int i,j,k;
EdgeNode *p;
if(flag == 0)
printf("\n建立一个无向图：\n");
else
printf("\n建立一个有向图：\n");
printf("请输入图的顶点数：");
scanf("%d",&g->n);
printf("请输入图的边数：");
scanf("%d",&g->e);
printf("请输入图的各顶点信息：\n");
for(i=0; i<g->n; i++){ //生成n个顶点的顶点表
getchar();
printf("第%d个顶点信息",i+1);
scanf("\n%c",&(g->adjlist[i].data)); //读入顶点信息,data为adjlist[i]的数据域
g->adjlist[i].firstedge = NULL; //点的边表头指针设为空，firstedge为adjlist[i]的指针域
}
printf("\n请输入边的信息，输入格式为：序号1 [空格] 序号2(序号依次为0、1、2···)\n");
for(k=0; k<g->e; k++){
printf("请输入第%d条边：",k);
scanf("\n%d %d",&i,&j);
//将编号为i的节点添加到邻接表中
p = (EdgeNode *)malloc(sizeof(EdgeNode));
p->adjvex = j;
p->next = g->adjlist[i].firstedge;
g->adjlist[i].firstedge = p;
//将编号为j的节点添加到邻接表中，有向图不用添加节点，去掉下面if语句
if(flag == 0){
p = p = (EdgeNode *)malloc(sizeof(EdgeNode));
p->adjvex = i; //邻接点序号为i
p->next = g->adjlist[j].firstedge; //将新节点p插到顶点vi边表头
g->adjlist[j].firstedge = p;
}
}
}
//输出图的邻接表
void DispAGraph(AdjList *g){
int i;
EdgeNode *p;
printf("\n图的邻接表图表示如下：\n");
for(i=0; i<g->n; i++){
printf("%2d [%c]",i,g->adjlist[i].data);
p = g->adjlist[i].firstedge;
while(p != NULL){
printf("-->[%d]",p->adjvex);
p = p->next;
}
printf("\n");
}
}
//图的深度优先遍历
void DFS(AdjList *g,int vi){
EdgeNode *p;
printf("(%d",vi);
printf("%c)",g->adjlist[vi].data);
visited[vi] = 1;
p = g->adjlist[vi].firstedge;
while(p != NULL){
if(visited[p->adjvex] == 0)
DFS(g,p->adjvex);
p = p->next;
}
}
//图的广度优先遍历
void BFS(AdjList *g,int vi){
int i,v,visited[MAX];
int qu[MAX],front=0,rear=0; //定义循环队列
EdgeNode *p;
for(i=0; i<g->n; i++) //辅助的访问数组赋初值
visited[i] = 0;
printf("(%d",vi); //输出起始访问顶点
printf("%c)",g->adjlist[vi].data);
visited[vi] = 1;
rear = (rear+1) % MAX; //队尾指针后移
qu[rear] = vi; //将vi入队
while(front != rear){ //当队不空时
front = (front+1) % MAX;
v = qu[front]; //将对头元素出队，赋给顶点v
p = g->adjlist[v].firstedge; //将顶点v的下一条邻接边顶点指针赋给p
while(p != NULL){
if(visited[p->adjvex] == 0){ //若未被访问过
visited[p->adjvex] = 1; //访问数组该元素置1，已访问
printf("(%d",p->adjvex); //输出该顶点编号
printf("%c)",g->adjlist[p->adjvex].data); //输出该顶点信息
rear = (rear+1) % MAX; //队尾指针后移
qu[rear] = p->adjvex; //将p所指的顶点入队
}
p = p->next; //p指针后移
}
}
}
void Menu()
{
printf(" 图的各种操作");
printf("\n==================================================");
printf("\n| 1--创建该无向图的邻接矩阵存储结构 |");
printf("\n| 2--输出该无向图的邻接矩阵表示 |");
printf("\n| 3--输入任意两个结点，判断是否有边存在 |");
printf("\n| 4--输入任意一个结点，求顶点的度 |");
printf("\n| 5--根据邻接矩阵求该无向图中边的数目 |");
printf("\n| 6--建立图的邻接表的算法 |");
printf("\n| 7--实现图的深度优先遍历 |");
printf("\n| 8--实现图的广度优先遍历 |");
printf("\n| 0--返回 |");
printf("\n==================================================");
printf("\n请输入菜单号（0-8）：");
}
main(){
MGraph G;
AdjList g;
char choice,a,m,n;
int f,i;
while(1){
Menu();
scanf("%c",&choice);
getchar();
switch(choice){
case '1':
CreateMGraph(&G);
printf("建立成功！\n");
break;
case '2':
printf("该无向图的邻接矩阵表示为：\n");
DispMGraph(G);
break;
case '3':
printf("请输入两个顶点(中间用空格分开)： ");
scanf("%c %c",&m,&n);
if(EdgeMGraph(&G,m,n))
printf("有边！\n");
else
printf("无边！\n");
break;
case '4':
printf("请输入一个结点：");
scanf("%c",&m);
printf("这个结点的度为：%d\n",DegreeMGraph(&G,m));
break;
case '5':
printf("该无向图中边的数目是：%d\n",AllMGraph(&G));
break;
case '6':
printf("要建立的是有向图(1)还是无向图(0)，请选择： ");
scanf("%d",&f);
CreateAGraph(&g,f);
DispAGraph(&g);
break;
case '7':
printf("请输入开始深度优先遍历的顶点序号(序号从0开始编号): ");
scanf("%d",&f);
printf("\n从顶点%d开始深度优先遍历序列为：",f);
for(i=0; i<g.n; i++)
visited[i] = 0;
DFS(&g,f);
break;
case '8':
printf("请输入开始广度优先遍历的顶点序号(序号从0开始编号): ");
scanf("%d",&i);
printf("\n从顶点%d开始广度优先遍历序列为：",i);
BFS(&g,i);
break;
case '0':
exit(1);
default:
printf("请重新输入\n");
}
if(choice != '0'){
printf("\n按回车继续，按任意键返回主菜单！\n");
a = getchar();
if(a != '\xA'){
getchar();
exit(1);
}
}
}
}
