09
2019
12

图的应用

(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);
             }
         }
    }
}



« 上一篇 下一篇 »

返回顶部
请先 登录 再评论,若不是会员请先 注册