11图

图

一些概念

图是由两个集合组成的：V结点集合与E边集

简单图：在图结构中，如果不存在顶点到其自身的边，且同一条边不会重复出现

无向图：边没有方向

有向图：边有方向

完全图：如果图中每两个顶点间都存在一条边

端点：无向图中的一条边的两个点，互为邻接点

度：

无向图中顶点具有边的数目

出度：从某个点出去的边数

入度：进入某个点的边数

子图：图的子集

路径：从一个顶点到另一个顶点之间的顶点序列

路径长度：路径所经的边的个数（最大值）

回路（环）：开始结点与结束结点相同

欧拉回路：经过图中各边有且仅有一次的回路（结点可能重复）

哈密顿回路：经过图中各顶点有且仅有一次的回路

连通：两个顶点之间如果有路径，则连通

连通图：如果任意两个顶点之间连通

连通分量：在一个无向图中一个极大连通子图，叫做连通分量

强连通图：有向图中的任意两个顶点之间连通

强连通分量：有向图中一个极大连通子图，叫做强连通分量

稠密图：大于nlnn的图

稀疏图：少于nlnn的图

权：图的每个边对应的数值，叫做权值

网：带权的图

连通图的生成树：极小连通图

图的存储

1.邻接矩阵

用一维数组存储结点

用二维数组存储边

列之和为入度，行之和为出度

注：对于带权图，没有边连接结点之间用正无穷表示，其余用权值表示

问题：对于稀疏图会出现空间浪费，因为结点间不连通的较多

代码实现

#include<stdio.h>
#include<stdlib.h>
#define Maxvertices 100
typedef struct {
    //一维数组表示顶点信息，二维数组表示边信息
    int Vertices[Maxvertices];
    int Edge[Maxvertices][Maxvertices];
    int numV,numE;//顶点数，边数
}AdjMatrix;
//注意：数组最大空间为100，并不意味着每次都需要存入100，真正存入的空间是以numV和numE来统计的

void CreateGraph(AdjMatrix *G)
{
    int n,e;//n代表顶点数，e代表边数
    int vi,vj;	//边的顶点（两个）
    printf("输入顶点数和边数");
    scanf("%d%d",&n,&e);
    G->numV=n;
    G->numE=e;
    
    //初始化图
    for(int i=0;i<n;i++)	//边数组初始化
    {
        for(int j=0;i<n;i++)
        {
            if(i==j)			//对角线之间赋0
            {
                G->Edge[i][j]=0;
			}
            else
            {
                G->Edge[i][j]=32767;	//其余为无穷值
            }
		}
	}
    
    for(int i=0;i<G->numV;i++)		//顶点信息录入
    {
        printf("请输入第%d个顶点的信息",i+1);
        scanf("%d",&G->Vertices[i]);
	}
    
    for(int i=0;i<G->numE;i++)		//边信息录入
    {
        printf("请输入边的顶点信息i,j");
        scanf("%d%d",&vi,&vj);	
        //无向图示例
        G->Edge[vi-1][vj-1]=1;		//边存在则赋值
        G->Edge[vj-1][vi-1]=1;
        //有向图则无需对称
    }
}

2.邻接表

数组和链表一起存储

数组：顶点集合

链表：边集（链表结点之间的关系为”从同一结点出发/进入“）

注：一个数组元素后的链表数目为一个结点的出度/入度（只能表示一种）

问题：对于顶点的出度和入度不能同时看到

#include<stdio.h>
#include<stdlib.h>
#define MAXVEX 100	//顶点数目最大值

//边链表中的结构
typedef struct EdgeNode{
    int adjvex;				//邻接的点所对应的下标
    struct EdgeNode* next;	//下一个指针
}EdgeNode;

//顶点表中的结构
typedef struct VertexNode{
    char data;				//信息的值
    struct EdgeNode* first;	//边表的头指针
}VertexNode,AdjList[MAXVEX];

//邻接表的抽象结构
typedef struct GraphAdjList{
    AdjList adjlist;			//顶点集合数组
    int numVertexes,numEdge;	//顶点的数量和边的数量
}GraphAdjList;

void CreateAlGraph(GraphAdjList* G)
{
    printf("输入顶点数和边数");
    scanf("%d%d",&G->numVertexes,&G->numEdge);			
    int vi,vj;	//接收顶点信息
    //输入顶点信息
    for(int i=0;i<G->numVertexes;i++)
    {
        scanf("%c",&G->adjlist[i]);
        getchar();
        G->adjlist[i].first=NULL;
	}
    //输入边的信息
    for(int i=0;i<G->numEdge;i++)
    {
        scanf("%d%d",&vi,&vj);
        getchar();
        EdgeNode* e=(EdgeNode*)malloc(sizeof(EdgeNode));
        e->adjvex=vj;
        e->next=G->adjlist[vi].first;
        G->adjlist[vi].first=e;
    }
}

3.十字链表

顶点集合：将出度和入度结合在一起，每个顶点结点多加一个指针

边集合：采用弧之间的关系

两个下标和两个指针：头尾结点的下标，指向同一结点的弧首指针，指向同一结点的弧尾指针

问题：对边的操作频繁不适合

#include<stdio.h>
#include<stdlib.h>
#define MAX 100
//边集
typedef struct AreBox{
    int tail;		//弧尾对应的顶点在数组中的下标
    int headvex;	//弧头对应的顶点在数组中的下标
    struct AreBox* hlink,*tlink;
    //弧头和弧尾对应的下一个边
}

typedef struct VexNode{
    int data;		//数据域
    AreBox* firstIn,*firstout;
    //该结点为弧头和弧尾的链表的头结点
}VexNode;

typedef struct {
    VexNode xlist[MAX];	//顶点数组
    int vexnum,arenum;
    //顶点数和边数
}OLGraph;

void CreatDG(OLGraph* G)
{
    int vi,vj;	//邻接顶点下标
    //输入有向图的顶点数和边数
    scanf("%d%d",&G->vexnum,&G->arenum);
    //输入顶点集的数据
    for(int i=0;i<G->vexnum;i++)
    {
        scanf("%d",&G->xlist[i].data);
        G->xlist[i].firstIn=NULL;
        G->xlist[i].firstout=NULL;
	}
    
    //构建十字链表
    for(int i=0;i<G->arenum;i++)
    {
        scanf("%d%d",&vi,&vj);		//输入下标
        
        //建立弧的结点
        AreBox*p=(AreBox*)malloc(sizeof(AreBox));
        p->tailvex=vi;	//弧尾下标
        p->headvex=vj;	//弧头下标
        p->hlink=G->xlist[vj].firstIn;	//指向弧头相同的下一个弧
        p->tlink=G->list[vj].firstout;
        
        G->xlist[vi].firstOut=G->xlist[vi].firstIn=p;		//头插
        
	}
}

4.邻接多重表

结点采用数组存储

边采用链表存储

一个边结点有四个数据

前后结点，前后指向同一结点的弧指针

优点：删除图中某个结点只需删除数组结点与之后跟踪到的所有结点即可

#include<stdio.h>
#include<stdlib.h>
#define MAX 100
//确定边的类型
typedef struct node{
    int ivex,jvex;
    struct node* vi;
    struct node* vj;
}AreNode;

typedef struct{
    char vertex;
    AreNode* first;
}VNode;

typedef struct{
    VNode Dvex[MAX];
    int vexnum,arenum;
}Grap;

void creat(Grap* G)
{
    int vi,vj;
    //输入顶点数和边数
    scanf("%d%d",&G->vexnum,&G->arenum);
    //输入各顶点的值
    for(int i=0;i<G->vexnum;i++)
    {
        scanf("%c",&G->Dvex[i].vertex);
        getchar();
        G->Dvex[i].first=NULL;
    }
    
    //构建邻接多重表
    for(int i=0;i<G->arenum;i++)
    {
        scanf("%d%d",&vi,&vj);
        AreNode* e=(AreNode*)malloc(sizeof(AreNode));
        e->ivex=vi;
        e->jvex=vj;
        e->Vi=G->Dvex[vi].first;
        G->Dvex[vi].first=e;
        e->Vj=G->Dvex[vj].first;
        G->Dvex[vj].fist=e;
    }
}

5.边集数组

两个一维数组构成，一个存储顶点信息，一个存储边的信息（结构体数组）

发布于 2024-11-10