图论_图的存储结构

邻接矩阵

顶点结构

用顺序表存顶点集，每个顶点包含数据data，顶点编号id（大部分情况下和顶点在数组中的下标对应）

struct Vertex{ int id; DataType data; };

边结构

用边的两个顶点在顺序表中的索引表示边，由于一条边包含两个索引，所以用一个二维数组来表示E集，边存在就填1，不存在就填0（自己指向自己的边）或INF（不同顶点之间的边）

typedef int Edge; //表示边的存在状态（0,1,INF）

图结构

封装好顶点集和边集，用vertexNum表示顶点个数，edgeNum表示边的条数，isDirect表示是否是有向图

struct MGraph{ Vertex nodes[MaxNumber]; Edge edges[MaxNumber][MaxNumber]; int vertexNum; int edgeNum; bool isDirect; };

初始化图

把边集里面自己指向自己的边填为0，不同顶点之间的边填为无穷大，假设已确定所有顶点

void initGraph(MGraph* graph,int vNum,bool isDirect,DataType vertex[]){ graph->vertexNum=vNum; greph->edgeNum=0; graph->isDirect=isDirect; for(int i=0;i<vertexNum;i++){ //初始化顶点集 graph->nodes[i].id=i; graph->nodes[i].data=vertex[i]; for(int j=0;j<vertexNum;j++){ //初始化边集 if(i==j)graph->edges[i][j]=0; else graph->edges[i][j]=INFINITY; } } }

添加边

假设边有权重weight，若不是网络就填1，边的起点为v1（索引），边的终点为v2（索引），若是无向图，添加一条边要添加对应的相反的边

void InsertEdge(MGraph* graph,int v1,int v2,int weight){ graph->edges[v1][v2]=weight; if(!graph->isDirect){ graph->edges[v2][v1]=weight; } graph->edgeNum++; }

邻接表

边结构

实际上是边的弧头和弧尾表示一条出度边，包含边的权值weight（如果是无权图就不需要），顶点的编号（弧头在数组中的下标）id，指向下一个弧头的指针next

struct Edge{ int weight; int id; Edge* next; }

顶点结构

用顺序表存顶点，每个顶点包含编号id，顶点的数据data，顶点的第一条出度边（实际上是弧头）fitstEdge

struct Vertex{ int id; Datatype data; Edge* firstEdge; }

图结构

包含顶点集数组V，顶点数量vertexNum，边数量edgeNum，是否是有向图isDirect

struct LGreaph{ Vertex* nodes; int vertexNum; int edgeNum; bool isDirect; }

初始化图

给顺序表中的顶点初始化data和id，firstEdge初始化为NULL

void initGraph(LGraph* graph,bool isDirect,int vNum,int edgeNum,DataType vertex[]){ graph->isDirect=isDirct; graph->vertexNum=vNum; graph->edgeNum=0; for(int i=0;i<graph->vertexNum;i++){ //初始化顶点集 graph->nodes[i].id=i; graph->nodes[i].data=vertex[i]; graph->nodes[i].firstEdge=NULL; } }

添加边

用头插法插在出度链表的表头，维护edgeNum，如果是无向图，需要添加相反的出度边

Edge* createEdge(int w,int v){ Edge* e=malloc(sizeof(Edge)); e->weight=w; e->id=v; e->next=NULL; return e; } void InsertEdge(LGraph* graph,int weight,int v1,int v2){ Edge* e=createEdge(weight,v2); e->next=graph->nodes[v1].firstEdge; graph->nodes[v1].firstEdge=e; graph->edgeNum++; if(!graph->isDirect){ //添加相反的出度边 e=createEdge(weight,v1); e->next=graph->nodes[v2].firstEdge; graph->nodes[v2].firstEdge=e; } }

缺点：不方便统计入度

十字链表

CrossGraph主要解决有向图

若用逆邻接表存有向图，有n条边就需要存2n个边结构
用十字链表存有向图，有n条边只需要存n个边结构

边结构

一条边含弧尾节点的编号tail，弧头节点的编号head，指向tail下一条出度边的指针tailNext，指向head下一条入度边的指针headNext，边的权重weight

struct Edge{ int tail; Edge* tailNext; int head; Edge* headNext; }

顶点结构

一个顶点含顶点编号id，顶点数据data，指向第一条入度边的指针firtstIn，指向第一条出度边的指针firstOut

struct Vertex{ int id; DataType data; Edge* firstIn; Edge* firstOut; }

图结构

用顺序表存储顶点集

struct CGraph{ int vertexNum; int edgeNum; Vertex* nodes; }

初始化图

void initGraph(CGraph* graph,int vNum,DataType vertex[]){ graph->vertexNum=vNum; graph->edgeNum=0; for(int i=0;i<graph->vertexNum;i++){ //初始化顶点结构 graph->id=i; graph->nodes[i].data=vertex[i]; graph->nodes[i].firstIn=nullptr; graph->nodes[i].firstOut=nullptr; } }

添加边

用头插法插入入度链表和出度链表

void InsertEdge(CGraph* graph,int t,int h,int w){ Edge* e=(Edge*)Edge(sizeof(Edge)); if(!e)return; graph->edgeNum++; e->tail=t; e->head=h; e->weight=w; //头插法插入出度边 e->tailNext=graph->nodes[e->tail]->firstOut; graph->nodes[e->tail]->firstOut=e; //头查法插入入度边 e->headNext=graph->nodes[e->head]->firstIn; graph->nodes[e->head]->firstIn=e; }

遍历所有出度

只需要从firstOut开始，沿着tailNext遍历到NULL

void traversalOut(CGraph* graph,int v){ Edge* p=graph->nodes[v]->firstOut; while(p){ visit(p); //访问行为 p=p->tailNext; } }

遍历入度同理

遍历所有入度

只需要从firstIn开始，沿着headNext遍历到NULL

void traversalIn(CGraph* graph,int v){ Edge* p=graph->nodes[v]->firstIn; while(p){ visit(p); //访问行为 p=p->headNext; } }