数据结构无向图的建立和遍历（邻接矩阵）

　　图主要分为无向图、有向图和网。存储方式主要是邻接矩阵和邻接表，接下来我写的是数据结构无向图邻接矩阵的构建方法

1.结构体

#define MAX  20   //边和顶点的最大数量 
typedef char ElemType;
typedef struct Graph{
    int vexNum;  //顶点数
    int arcNum;  //边的数量 
    ElemType vexs[MAX];       //顶点信息 
    int arcs[MAX][MAX];    //边的信息 
}Graph,*myGraph;

2.构建图

void createGraph(myGraph &G)
{
    G=(Graph*)malloc(sizeof(Graph));  //结构体的指针要初始化
     
    int i,j,k;
    int vexNum,arcNum;
    char v1,v2;    //边的两个顶点 
    printf("请输入顶点的数量:");
    scanf("%d",&G->vexNum);
    printf("请输入边的数量:");
    scanf("%d",&G->arcNum);
    
    printf("请依次将顶点数据输入进来
");
    for(i=0;i<G->vexNum;i++)
    {   
        getchar();
        scanf("%c",&G->vexs[i]); 
    }
    
    for(i=0;i<G->vexNum;i++)
    {
        for(j=0;j<G->vexNum;j++)
        {
            G->arcs[i][j]=0;//初始化矩阵 
        }
    }
    
    printf("请依次将边输入进来
");
    for(i=0;i<G->arcNum;i++)
    {
        getchar();
        scanf("%c%c",&v1,&v2);
        j=getLocate(G,v1);
        k=getLocate(G,v2);
        G->arcs[j][k]=1;
        G->arcs[k][j]=1;
    }
}

3.输出邻接矩阵

void printfGraph(myGraph G)
{
    int i,j;
    printf("  "); 
    for(i=0;i<G->vexNum;i++)
    {
        printf("%c ",G->vexs[i]);
    }
    printf("
");
    for(i=0;i<G->vexNum;i++)
    {
        printf("%c ",G->vexs[i]);
        for(int j=0;j<G->vexNum;j++)
        {
            printf("%d ",G->arcs[i][j]);
        }
        printf("
");
    }
}

4.图的深度优先遍历

深度优先遍历：先遍历第一元素顶点，在遍历该顶点最近的邻接点，如此反复循环，如果无法找到邻接点，则返回回来

void DFS(myGraph G,int i,int *visit)
{
    int j;
    if(!visit[i])
    {
        visit[i]=1;  //代表该顶点已被遍历
        printf("%c ",G->vexs[i]);
        for(int j=0;j<G->vexNum;j++)
        {
            if(!visit[j]&&G->arcs[i][j]==1) //访问没有被访问过得邻接点 
            {
                DFS(G,j,visit);
            }
        }
    } 
}

5.图的广度优先遍历：从图中某一个顶点出发，再依次访问所有的邻接点，直至所有的顶点均被访问为止

void BFS(myGraph G,int *visit)  //满足队列先进先出的特性 
{
    int front=0;
    int rear=0;
    int Queue[MAX]; //储存每个数据的下标 
    int i,j,k;
    
    for(i=0;i<G->vexNum;i++)
    {
        visit[i]=0;   //先经过了深度优先遍历，先全部变成未访问 
    }
    
    for(i=0;i<G->vexNum;i++) //避免出现个人没有边的顶点 
    {
        if(!visit[i])
        {
            visit[i]=1;  //该顶点已被访问
            printf("%c ",G->vexs[i]);
            Queue[rear++]=i;   //第一元素的下标 
        }
        while(front!=rear)
        {
            j=Queue[front++];
            
            for(k=firstVertex(G,j);k>=0;k=nextVertex(G,j,k))  //将出队列的所有节点的邻接点都入队
            {
                if(!visit[k])//如果没有被访问过 
                {
                    visit[k]=1;
                    Queue[rear++]=k;
                    printf("%c ",G->vexs[k]);
                }
            }
        }
    }
}

所有的代码如下：

#include<stdio.h>
#include<stdlib.h> 

#define MAX  20   //边和顶点的最大数量 
typedef char ElemType;
typedef struct Graph{
    int vexNum;  //顶点数
    int arcNum;  //边的数量 
    ElemType vexs[MAX];       //顶点信息 
    int arcs[MAX][MAX];    //边的信息 
}Graph,*myGraph;

//获取顶点的下标
int getLocate(myGraph G,char v)
{
    int i;
    for(i=0;i<G->vexNum;i++)
    {
        if(v==G->vexs[i])
        {
            return i;
        }
    }
    return -1;
}
 

//图的创建
void createGraph(myGraph &G)
{
    G=(Graph*)malloc(sizeof(Graph));  //结构体的指针要初始化
     
    int i,j,k;
    int vexNum,arcNum;
    char v1,v2;    //边的两个顶点 
    printf("请输入顶点的数量:");
    scanf("%d",&G->vexNum);
    printf("请输入边的数量:");
    scanf("%d",&G->arcNum);
    
    printf("请依次将顶点数据输入进来
");
    for(i=0;i<G->vexNum;i++)
    {   
        getchar();
        scanf("%c",&G->vexs[i]); 
    }
    
    for(i=0;i<G->vexNum;i++)
    {
        for(j=0;j<G->vexNum;j++)
        {
            G->arcs[i][j]=0;//初始化矩阵 
        }
    }
    
    printf("请依次将边输入进来
");
    for(i=0;i<G->arcNum;i++)
    {
        getchar();
        scanf("%c%c",&v1,&v2);
        j=getLocate(G,v1);
        k=getLocate(G,v2);
        G->arcs[j][k]=1;
        G->arcs[k][j]=1;
    }
}

//返回第一个邻接点坐标 
int firstVertex(myGraph G,int i)
{
    if(i<0||i>(G->vexNum-1))
    {
        printf("输入的下标不正确
");
        return -1;
    }
    else
    {
        int j;
        for(int j=0;i<G->vexNum;j++)
        {
            if(G->arcs[i][j]==1)
            {
                return j;
            }
        }
        return -1;    
    }
}

//返回下一个邻接点坐标 
int nextVertex(myGraph G,int i,int j)
{
    if(i<0||i>(G->vexNum-1)||j<0||j>(G->vexNum-1))
    {
        printf("输入的下标不正确
");
        return -1;
    }
    else
    {
        int k;
        for(k=j+1;k<G->vexNum;k++)
        {
            if(G->arcs[i][k]==1)
            {
                return k;
            }
        }
        return -1;
    }
}

//图的深度优先遍历
void DFS(myGraph G,int i,int *visit)
{
    int j;
    if(!visit[i])
    {
        visit[i]=1;  //代表该顶点已被遍历
        printf("%c ",G->vexs[i]);
        for(int j=0;j<G->vexNum;j++)
        {
            if(!visit[j]&&G->arcs[i][j]==1) //访问没有被访问过得邻接点 
            {
                DFS(G,j,visit);
            }
        }
    } 
}

//图的广度优先遍历
void BFS(myGraph G,int *visit)  //满足队列先进先出的特性 
{
    int front=0;
    int rear=0;
    int Queue[MAX]; //储存每个数据的下标 
    int i,j,k;
    
    for(i=0;i<G->vexNum;i++)
    {
        visit[i]=0;   //先经过了深度优先遍历，先全部变成未访问 
    }
    
    for(i=0;i<G->vexNum;i++) //避免出现个人没有边的顶点 
    {
        if(!visit[i])
        {
            visit[i]=1;  //该顶点已被访问
            printf("%c ",G->vexs[i]);
            Queue[rear++]=i;   //第一元素的下标 
        }
        while(front!=rear)
        {
            j=Queue[front++];
            
            for(k=firstVertex(G,j);k>=0;k=nextVertex(G,j,k))  //将出队列的所有节点的邻接点都入队
            {
                if(!visit[k])//如果没有被访问过 
                {
                    visit[k]=1;
                    Queue[rear++]=k;
                    printf("%c ",G->vexs[k]);
                }
            }
        }
    }
} 

//邻接矩阵的打印 
void printfGraph(myGraph G)
{
    int i,j;
    printf("  "); 
    for(i=0;i<G->vexNum;i++)
    {
        printf("%c ",G->vexs[i]);
    }
    printf("
");
    for(i=0;i<G->vexNum;i++)
    {
        printf("%c ",G->vexs[i]);
        for(int j=0;j<G->vexNum;j++)
        {
            printf("%d ",G->arcs[i][j]);
        }
        printf("
");
    }
}

int main()
{    
     myGraph G;
     createGraph(G);  //图的邻接矩阵的建立 
     printfGraph(G);   //图的输出 
     
     printf("深度优先搜索如下：
");
     int visit[G->vexNum]={0};
     for(int i=0;i<G->vexNum;i++) //这里for循环是为了出现没有被连接边的顶点 
     {
         DFS(G,i,visit);  //深度优先搜索 
     }
     
     printf("
");
     printf("广度优先搜索如下：
");
     BFS(G,visit);
     free(G);
}

　　该程序的图的功能可以正常实现，但是图的广度优先遍历会使程序崩溃，但是排序没有问题，还没有找到是什么原因导致的

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/qian-yi/p/12768632.html