美文网首页
从0开始——图

从0开始——图

作者: c枫_撸码的日子 | 来源:发表于2018-11-16 16:39 被阅读0次

1图的概念

图的概念

2.图的存储结构

1.邻接矩阵

邻接矩阵 
//邻接矩阵
#include <stdlib.h>
#include <stdio.h> 
#include <windwos.h>

typedef char VertexType;//定点类型，这里设为char
typedef int EdgeType;//边的权值
#define MAXVEXS 100//最大顶点数
#define INFINITY 65535 //表示无穷大

typedef struct Graph
{
    VertexType vexs[MAXVEXS ];//顶点集合
    EdgeType arc[MAXVEXS][MAXVEXS];//邻接矩阵
    int numVexs,numEdge;//当前顶点数和边数
}Graph;

//创建无向图邻接矩阵 
void CreateGraph(Graph *G)
{
    int i,j,k,w;
    printf("请输入邻接图的顶点个数和边个数:\n");   
    scanf("%d,%d",&G->numVexs,&G->numEdge);
    printf("请输入顶点集合:\n");
    for(i=0;i<G->numVexs;i++)//初始化顶点
        scanf("%c",&G->vexs[i])；
    for(i=0;i<G->numVexs;i++)//初始化邻接矩阵
        for(j=0;j<G->numEdge;j++)
            G->arc[i][j]=INFINITY;//先初始化为无限大
    for(k=0;k<G->numEdge;k++)
    {
        printf("请输入(vi,vj)的i和j和权值w:");
        scanf("%d,%d,%d",&i,&j,&w);
        G->arc[i][j]=w;
        G->arc[j][i]=w;
    } 
}

2.邻接表

邻接表
带权值的邻接表 
//邻接表 
#include <stdlib.h>
#include <stdio.h> 
#include <windwos.h>

typedef char VertexType;//顶点类型，这里设为char
typedef int EdgeType;//边的权值
#define MAXVEXS 100//最大顶点数

typedef struct EdgeNode//边表节点 
{
    int adjvex;//邻接点下标
    EdgeType weight;//权值
    struct EdgeNode *next;//下一个邻接点 
}EdgeNode;

typedef struct VexNode//顶点表节点
{
    VertexType data;//顶点域 
    EdgeNode *firstedge;//边表头指针 
} VexNode,AdjList[MAXVEXS];

typedef struct
{
    AdjList list;
    int numVex,numEdge;//实际的顶点数和边数          
}GraphAdjList;

//创建无向图邻接表 
void CreateGraph(GraphAdjList *G)
{
    int i,j,k,w;
    EdgeNode *e;
    printf("请输入顶点数和边数:\n");
    scanf("%d,%d",&G->numVex,&G->numEdge);
    for(i=0;i<G->numVex;i++)//建立顶点表 
    {
        scanf("%c",G->list[i].data);//输入顶点的值
        G->list[i].firstedge = NULL;//先指向NULL 
    }
    
    for(k=0;k<G->numEdge;k++)
    {
        printf("请输入(vi,vj)下标i和j和权值w\n");
        scanf("%d,%d",&i,&j,&w);
        e =(EdgeNode*)malloc(sizeof(EdgeNode));
        e->weight=w;
        e->adjvex=j;
        e->next=G->list[i].firstedge;
        G->list[i].firstedge = e;
        
        //因为是无向图，i->j和j->i都是一样的
        e->weight=w;
        e->adjvex=i;
        e->next=G->list[j].firstedge;
        G->list[j].firstedge = e;        
            
    }
    
}

3.图的遍历

概念
1.深度优先遍历（Depth_First_Search）DFS
深度优先类似于树的前序遍历！！！
1.1邻接矩阵的深度优先算法 
//邻接矩阵的深度优先算法 
#include <stdlib.h>
#include <stdio.h> 
#include <windwos.h>

typedef char VertexType;//定点类型，这里设为char
typedef int EdgeType;//边的权值
#define MAXVEXS 20//最大顶点数
#define INFINITY 65535 //表示无穷大

//用于记录已经访问的节点,0->表示未访问过，1表示已访问 
int visited[MAXVEXS]; 

typedef struct Graph
{
    VertexType vexs[MAXVEXS ];//顶点集合
    EdgeType arc[MAXVEXS][MAXVEXS];//邻接矩阵
    int numVexs,numEdge;//当前顶点数和边数
}Graph;

//创建无向图邻接矩阵 
void CreateGraph(Graph *G)
{
    int i,j,k,w;
    printf("请输入邻接图的顶点个数和边个数:\n");   
    scanf("%d,%d",&G->numVexs,&G->numEdge);
    printf("请输入顶点集合:\n");
    for(i=0;i<G->numVexs;i++)
        scanf("%c",&G->vexs[i])
    for(i=0;i<G->numVexs;i++)
        for(j=0;j<G->numEdge;j++)
            G->arc[i][j]=INFINITY;//先初始化为无限大
    for(k=0;k<G->numEdge;k++)
    {
        printf("请输入(vi,vj)的i和j和权值w:");
        scanf("%d,%d,%d",&i,&j,&w);
        G->arc[i][j]=w;
        G->arc[j][i]=w;
    } 
}

//邻接矩阵深度优先递归算法 
void DFS(Graph *G,int i)
{
    int j;
    printf("%c ",G->vexs[i]);//访问顶点i
    visited[i]=1;//记录i节点访问过
    for(j=0;j<G->numVexs;j++)
    {
        if(G->arc[i][j] == 1&&visited[j]!=1)//下个连接点并且未访问过
        {
            DFS(G,j);
        } 
    }       
} 
//邻接矩阵的深度遍历操作
DFSTraverse(Graph *G)
{
    int i;
    for(i=0;i<G->numVexs;i++)
        visited[i]=0;//所有顶点默认未访问
    for(i=0;i<G->numVexs;i++)
    {
        if(visited[i]==0)
            DFS(G,i);
    } 
}

1.2邻接表的深度优先算法

//邻接表 深度优先算法 
#include <stdlib.h>
#include <stdio.h> 
#include <windwos.h>

typedef char VertexType;//顶点类型，这里设为char
typedef int EdgeType;//边的权值
#define MAXVEXS 100//最大顶点数

typedef struct EdgeNode//边表节点 
{
    int adjvex;//邻接点下标
    EdgeType weight;//权值
    struct EdgeNode *next;//下一个邻接点 
}EdgeNode;

typedef struct VexNode//顶点表节点
{
    VertexType data;//顶点域 
    EdgeNode *firstedge;//边表头指针 
} VexNode,AdjList[MAXVEXS];

typedef struct
{
    AdjList list;
    int numVex,numEdge;//实际的顶点数和边数          
}GraphAdjList;

int visited[MAXVEXS];//记录顶点的访问状态，0表示未访问，1表示已访问。 

//创建无向图邻接表 
void CreateGraph(GraphAdjList *G)
{
    int i,j,k,w;
    EdgeNode *e;
    printf("请输入顶点数和边数:\n");
    scanf("%d,%d",&G->numVex,&G->numEdge);
    for(i=0;i<G->numVex;i++)//建立顶点表 
    {
        scanf("%c",G->list[i].data);//输入顶点的值
        G->list[i].firstedge = NULL;//先指向NULL 
    }
    
    for(k=0;k<G->numEdge;k++)
    {
        printf("请输入(vi,vj)下标i和j和权值w\n");
        scanf("%d,%d",&i,&j,&w);
        e =(EdgeNode*)malloc(sizeof(EdgeNode));
        e->weight=w;
        e->adjvex=j;
        e->next=G->list[i].firstedge;
        G->list[i].firstedge = e;
        
        //因为是无向图，i->j和j->i都是一样的
        e->weight=w;
        e->adjvex=i;
        e->next=G->list[j].firstedge;
        G->list[j].firstedge = e;        
            
    }   
}
//深度优先递归算法 
void DFS(GraphAdjList G,int i)
{
    EdgeNode *p;
    printf("%c ",G->list[i].data);//访问顶点
    visited[i]; 
    p = G->list[i].firstedge;//指向下一个邻接点
    while(p!=NULL)
    {
        if(visited[p->adjvex]==0)//位访问
            DFS(G,p->adjvex);
        p=p->next;//指向下一个节点 
    }   
} 

//深度优先遍历
void DFSTraver(GraphAdjList *G) 
{
    int i;
    for(i=0;i<G->numVex;i++)
        visited[i]=0;//初始化所有顶点的状态为：未访问
    for(i=0;i<G->numVex;i++)
    {
        if(visited[i]==0)//如果未访问过
        {
            DFS(G,i);//深度优先访问 
        } 
    } 
}

1.3扩展:马踏棋盘算法(骑士周游问题)

马踏棋盘
马的走法

2.广度优先遍历（Breadth_First_Search）BFS
广度优先类似于树的层序遍历，用队列的形式去实现！！！

队列方式实现
1.1邻接矩阵的广度优先算法 
#include <stdlib.h>
#include <stdio.h> 
#include <windwos.h>

typedef char VertexType;//顶点类型，这里设为char
typedef int EdgeType;//边的权值
#define MAXVEXS 100//最大顶点数

int visited[MAXVEXS];//记录顶点的访问状态 

//邻接矩阵的广度优先算法
void BFSTraverse(Graph *G)
{
    int i,j;
    Queue Q;//队列
    InitQueue(&Q);//初始化队列 
    for(i=0;i<G->numVexs;i++)
        visited[i]=0;//初始化顶点的状态为0，表示未访问
    
    for(i=0;i<G->numVexs;i++)
    {
        if(visited[i]==0)//如果未被访问过
        {
            printf("%c ",G->vexs[i]);//访问顶点
            visited[i]=1;//记录该顶点被访问过
            EnQueue(&Q,i);//把顶点入队
            while(!IsEmpty(Q))//如果队列不为空 
            {
                DeQueue(&Q,&i);//出队
                for(j=0lj<G.numVexs;j++)
                {
                    //判断其他顶点与当前顶点存在边且未被访问过
                    if(G->arc[i][j]==1&&visited[j]==0)
                    {
                        printf("%c ",G->vexs[i]);//访问顶点
                        visited[i]=1;//记录该顶点被访问过
                        EnQueue(&Q,i);//把顶点入队   
                    } 
                } 
            }
        } 
    }
         
}

1.2邻接表的广度优先算法

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

typedef char VertexType;//顶点类型，这里设为char
typedef int EdgeType;//边的权值
#define MAXVEXS 100//最大顶点数

int visited[MAXVEXS];//记录顶点的访问状态 

//邻接表的广度优先算法
void BFSTraverse(GraphAdjList *G)
{
    int i,j;
    EdgeNode *p;
    Queue Q;//队列
    InitQueue(&Q);//初始化队列 
    for(i=0;i<G->numVexs;i++)
        visited[i]=0;//初始化顶点的状态为0，表示未访问
    
    for(i=0;i<G->numVexs;i++)
    {
        if(visited[i]==0)//如果未被访问过
        {
            printf("%c ",G->list[i].data);//访问顶点
            visited[i]=1;//记录该顶点被访问过
            EnQueue(&Q,i);//把顶点入队
            while(!IsEmpty(Q))//如果队列不为空 
            {
                DeQueue(&Q,&i);//出队
                p=G->list[i].firstedge;//指向头指针 
                while(p)//不为空 
                {
                    //判断当前顶点未被访问过
                    if(visited[p->adjvex]==0)
                    {
                        printf("%c ",G->vexs[i]);//访问顶点
                        visited[p->adjvex]=1;//记录该顶点被访问过
                        EnQueue(&Q,i);//把顶点入队   
                    } 
                    p=p->next;//指向下一个顶点 
                } 
            }
        } 
    }
         
}

相关文章

  • 从0开始——图

    1图的概念 2.图的存储结构 1.邻接矩阵 2.邻接表 3.图的遍历 1.2邻接表的深度优先算法 1.3扩展:马踏...

  • 从0开始

    不想再碌碌无为继续这么混下去了好嘛

  • 从0开始

    空杯心态，说着容易做着难。 当我们从有了孩子的欣喜若狂，到孩子第一天上幼儿园的充满希望，然后到小学三四年级的开始纠...

  • 从0开始

    当一家公司开始招聘专业安全人员的时候，意味着安全对这家公司已经比较重要了，比如曾发生一些入侵或者信息泄漏等安全事件...

  • 从0开始

    The best time to plant a tree is twenty years ago. The se...

  • 从0开始

    接触简书已经半年多了，最初是在看一些公众号的文章时偶然间看到了简书，这个集读文写文于一身的平台，早早的就下了这个软...

  • 从0开始

    写作是我的短板，一直以来都想突破但都在得过且过，没有行动，希望从今天开始学习，跟大家一起努力加油，成为更好的自己！

  • 从0开始

    现在生活已经慢慢进入正轨，而我却在迷茫。我的这种迷茫和否定不知跟谁去说，又不知从何说起。 目前跟家人，朋友，没有一...

  • 从0⃣️开始

    今天是二零二零年六月十一日，我只想吐槽一下昨天的宝宝拍照。 昨天并不是一个很好的天气，这几天的江苏已然进入了梅雨季...

  • 从0开始

    好不容易日更100天，结果昨天忘了，今天又要从0开始，气死我了，我还买了复活卡，谁知道点错了。突然没兴趣写下去了。...

网友评论

      本文标题：从0开始——图

      本文链接：https://www.haomeiwen.com/subject/gbtjfqtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|从0开始——图|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！