600字范文 > C语言《数据结构》（朱战立）：图

C语言《数据结构》（朱战立）：图

时间：2018-12-20 19:02:15

相关推荐

C语言《数据结构》（朱战立）：图

C语言数据结构：图

一、图的基本概念

1、图的定义

G=（V，E）

V{x|x∈某个数据元素集合}：表示顶点E{(x,y)|x,y∈V}：表示路径，若指定Path(x,y)，说明x到y是一条单向通路，若不指定则是无向的。

2、图的基本术语

顶点和边：图中结点称为顶点，两个顶点相关联，这称两顶点间有条边

有向图和无向图：<x,y>，<y,x>表示边有方向，(x,y)表示边无方向

无向完全图：在n个顶点的无向图中，任意两个顶点间有且只有一条边（n(n-1)/2条边）

有向完全图：在n个顶点的有向图中，任意两个顶点之间有且只有方向相反的两条边（n(n-1)）

邻接顶点：一条边的两个点称为邻接顶点

顶点的度：指与某一顶点相关联的边的条数，有几条边就有多少度

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

权：边的附带信息

路径长度：不带权的图，路径的长度就行路径上边的条数。带权的图，路径的长度，是边上权的总和

子图：G1={V1,E2}和G2{V2，E2},若V2∈V1，E2属于E1，则G2是G1的子图

连通图：无向图中，任意两个顶点都能连通

强连通图，有向图中，任意两个顶点都能连通

生成树：一个连通图最小的连通子图。有n个顶点的连通图的生成树有n个顶点和n-1条边

简单路径：路径上的顶点不重复

回路：路径上的第一个顶点和最后一个顶点重合，称为回路

3、图的抽象数据类型

① 数据集合

数据集合由一组顶点{v}和一组边{e}集合组成，当为带权图时，还包含边上的权集合{w}

② 操作集合

//初始化图Initiate(G);//插入顶点InsertVertex(G,vertex);//插入边InsertEdge(G,V1,V2,weight);//删除边DeleteEdge(G,V1,V2)//删除顶点DeleteVertex(G,vertex);//取第一个领接顶点GetFirstVex(G,int,V1,V2);//取下一个领接顶点GetNextVex(G,int,V1,V2);//遍历DepthFirstSearch(G);

二、图的存储结构

1、图的邻接矩阵存储结构

适用于稠密矩阵，当为稠密矩阵时最高效

顶点信息用一维数组存储，边信息的邻接矩阵用二维数组存储，无向图的邻接矩阵一定是对称矩阵。有向图一般非对称。

① 无向图和其邻接矩阵

考试写法如下：

② 带权无向图和其邻接矩阵

自己和自己为0，非邻接顶点为∞，权为权值

③ 有向图和其邻接矩阵

④ 带权有向图和其邻接矩阵

2、图的邻接表存储结构

适合稀疏矩阵，为稀疏矩阵时更有效

将稀疏矩阵存储在行指针数组结构的三元组链表中

三、图的实现

1、邻接矩阵存储结构图的操作实现

① 结点结构体

#inclede"SeqList.h"typedef struct{SeqList vertices;//存放顶点的顺序表int edge[MaxVertices][MaxVertices];//存放边的邻接矩阵int numOfEdges;//边的条数}AdjMGraph;

② 初始化

void Initiate(AdjMGraph *G,int n){int i,j;for(i=0;i<n;i++){for(j=0;j<n;j++){if(i==j) G->edge[i][j] = 0;else G->edge[i][j] = MaxWeight;//表示无穷大}G->numOfEdges = 0;ListInitiate(&G->Vertices);}

③ 插入顶点

void InsertVertex(AdjMGraph *G,DataType vertex){ListInsert(&G->Vertices,G->Vertices.size,vertex);}

④ 插入边

void InsertEdge(AdjMGraph *G,int v1,int v2,int weight){if(v1<0 || v1 >= G->Vertives.size || v2<0 || v2>=G->Vertices.size){printf("参数v1或v2越界出错!\n");return;}G->edge[v1][v2]=weight;G->numOfEdges++;}

⑤ 删除边

void DeleteEdge(AdjMGraph *G,int v1,int v2){if(v1<0 || v1>=G->Vertices.size || V1==V2){printf("参数v1或v2出错！\n");return;}if(G->edge[v1][v2]==MaxWeight||v1==v2){printf("该边不存在！\n");return;}G->edge[v1][v2]=MaxWeight;G->numOfEdges--;}

⑦ 取第一个邻接顶点

int GetFirstVex(AdjMGraph G,int v){int col;if(v<0 || V>= G.Vertices.size){printf("参数v1越界出错");return -1;}for(col=0;col<G.Vertices.size;col++)if(G.edge[v][col]>0 && G.edge[v][col]<MaxWeight) return col;return -1;}

⑧ 取下一个邻接结点

int GetNextVex(AdjMGraph G,int v1,int v2){int col;if(v1<0 || v1>=G.Vertices.size || V2<0 || V2>=G.Vertices.size){printf("参数v1或v2越界出错！\n");return -1;}for(col=v2+1;col<G.Vertices.size;col++)if(G.edge[v1][col]>0 && G.edge[v1][col]<MaxWeight) retutn col;return -1;}

2、创建图函数

typedef struct{int row;//行int col;//列int weight;//权值}RowColWeight;void GreatGraph(AdjMGraph *G,DataType V[],int n,RowColWeight E[],int e){int i,k;Initiate(G,n);for(i=0;i<n;i++)InsertVertex(G,V[i]);//插入顶点for(k=0;k<e;k++)InsertEdge(G,E[K].row,E[k].col.E[k].weight);//插入边}

3、邻接表存储结构图的操作实现

① 邻接表的存储结构

typedef struct Node{int dest;//邻接边弧头顶点序号struct Node *next;}Edge;typedef struct{DataType data;//顶点数据元素int source;//邻接边弧尾顶点序号Edge *adj;//邻接边的头指针}AdjHeight;typedef struct{AdjLHeight a[MaxVertices];//邻接表数组int numOfVerts;//顶点个数int numOfEdges;//边个数}AdjLGraph;

② 初始化

AdjInitiate(AdjLGraph *G){int i;G->numOfVerts=0;G->numOfEdfes=0;for(i=0;i<MaxVertices;i++){G->a[i].source = i;G->a[i].adj = NULL;}}

③ 插入顶点

void InsertVertex(adjLGraph *G,int i,DataType vertex){if(i>=0 && i<Maxvertices){G->a[i].data=vertex;G->numOfVerts++;}else printf("顶点越界");}

④ 插入边

void InsertEdge(AdjLGraph *G,int v1,int v2){Edge *p;if(v1<0 || v1>=G->numOfVerts || v2<0 || v2 >= G->numOfVerts){printf("参数v1或v2越界出错！");return;}p = (Edge *)malloc(sizeof(Edge));p->dest = v2;p->next = G->a[v1].adj;G->a[v1].adj = p;G->numOfEdges++;}

⑤ 删除边

void DeleteEdge(AdjLGraph *G,int v1,int v2){Edge *curr,*pre;if(v1<0 || v1>= G->numOfVerts || v2<0 || v2>=G->numOfVerts){printf("参数v1或v2越界出错！");return;}pre = NULL;curr = G->a[v1].adj;while(curr != NULL && curr->dest != v2){pre = curr;curr = curr->next;}if(curr!=NULL && curr->dest !=v2){pre = curr;curr = G->a[v1].adj;while(curr!=NULL && curr->dest != v2){pre = curr;curr = curr->next;}if(curr != NULL && curr->dest == v2 && pre ==NULL){G->a[v1].adj=crtt->next;free(curr);G->numOfEdges--;}else if(curr != NULL && curr->dest == v2 && pre != NULL){pre->next = curr->next;free(curr);G->numOfEfges--;}elseprintf("边<v1,v2>不存在！")}

四、图的遍历

1、图的遍历关键点

图无首尾之分，要指定访问的第一个结点设计要考虑遍历路径为回路的情况，避免死循环要使一个顶点的所有邻接顶点按照某种次序都被访问到

2、图的深度优先遍历

顺着顶点一直找邻接结点，然后再返回到顶点，再找他的邻接结点一直顺着找，他没有就顺着他的邻接结点找

关键：在图的所有邻接顶点中，每次都在访问完当前顶点后，首先访问当前顶点的第一个邻接顶点。

① 访问顶点v并标记顶点v为已访问

② 查找顶点v的第一个邻接顶点w

③ 若顶点v的邻接顶点w存在，则继续执行，否则算法结束

④ 若顶点w尚未被访问，则深度优先遍历递归访问顶点w

⑤ 查找顶点v的w邻接顶点的下一个邻接顶点w，转到步骤3

void DepthFSearch(AdjMGraph G,int v,int visited[],void Visit(DataType)){int w;Visit(G.Vertices.list[v]);visited[v]=1;w=GetFirstVex(G,v);while(w!=-1){if(!visited[w])DepthFSearch(G,w,visited,Visit);w=GetNextVex(G,v,w);}}

3、图的广度优先遍历

顺着顶点先找完它的邻接结点，一层一层的寻找

关键：从指定顶点开始，按照到该顶点的路径长度由短到长的顺序，依次访问图中的其余顶点

① 访问初始顶点v并标记顶点v为已访问

② 顶点v入队列

③ 若队列非空，则继续执行，否则算法结束

④ 出队列取得队头顶点u

⑤ 查找顶点u的第一个邻接顶点w

⑥ 若顶点u的邻接顶点w不存在，则转到步骤③，否则循环执行

（a）若顶点w尚未被访问，则访问顶点w并标记顶点w为已访问

（b）顶点w入队列

（c）查找顶点u的w邻接顶点后的下一个邻接顶点w，转到步骤⑥

#include "SeqCQueue.h"//导入循环队列void BroadFSearch(AdjMGraph G,int v,int visited[],void Visit(DataType item)){int u,w;SeqCQueue queue;Visit(G.Vertices.list[v]);visitrd[v]=1;QueueInitiate(&queue);QueueAppend(&queue,v);while(QueueNotEmpty(queue)){QueueDelete(&queue,&u);w=GetFirstVex(G,u);while(w!=-1){if(!visited[w]){Visit(G.Vertices.list[w]);visited[w]=1;QueueAppend(&queue,w);}w=GetNextVex(G,u,w);}}}