C语言-数据结构-图

目录

一,图的概念

1,图的定义

2,图的基本术语

二,图的存储结构

1,邻接矩阵

2,邻接表

三,图的遍历

1,深度优先搜索

2,广度优先搜素

四,生成树和最小生成树

1,生成树的特点:

2,最小生成树

(1)普利姆算法Prim

(2)普里姆算法思路

五,最短路径

1,Dijkstra算法

2,Floyd算法

六,拓扑排序

七,关键路径

---

一,图的概念

1,图的定义

在图G中，如果代表边的顶点对是无序的，则称G为无向图。用圆括号 序偶表示无向边。
如果表示边的顶点对是有序的，则称G为有向图。用尖括号序偶表示 有向边。

2,图的基本术语

1,端点和连接点	无向图：若点若 存在一条边(i，j) 顶点i和顶点j为端点，它们互为邻接
	有向图：若 存在一条边<i，j> 顶点i为起始端点（简称为起点）， 顶点j为终止端点（简称终点），它们互为邻接点。
2,顶点的度、入度和出度	无向图：以顶点  i为端点的边数称为该顶点的度。
	有向图： 以顶点i为终点的入边的数目，称为该 顶点的入度。以顶点i为始点的出边的数目，称为该顶点的出度。一个顶点的入度与出度的和为该顶点的度。
3、完全图	无向图：每 两个顶点之间都存在着一条边，称为完全无向图，包含有 n(n-1)/2条边。
	有向图：每 两个顶点之间都存在着方向相反的两条边，称为完全有向 图，包含有n(n-1)条边。
4、子图	设有两个图G=(V，E)和G'=(V'，E')，若V'是V的子集， 且E'是E的子集，则称G'是G的子图。
5, 路径长度	路径长度是指一条路径上经过的边的数目。
6,简单路径	若一条路径上除开始点和结束点可以相同外，其余顶点均不相同，则称 此路径为简单路径。
7、回路或环	若一条路径上的开始点与结束点为同一个顶点，则此路径被称为回 路或环。开始点与结束点相同的简单路径被称为简单回路或简单环。
8、连通、连通图和连通分量	无向图： (1)若从顶点i到顶点j有路径，则称顶点i和j是连通的。 (2)若图中任意两个顶点都连通，则称为连通图，否则称为非连通图。 (3)无向图G中的极大连通子图称为G的连通分量。显然，任何连通图的连 通分量只有一个，即本身，而非连通图有多个连通分量。
	有向图： (1)若从顶点i到顶点j有路径，则称从顶点i到j是连通的。 (2)若图G中的任意两个顶点i和j都连通，即从顶点i到j和从顶点j到i都存在 路径，则称图G是强连通图。 (3)有向图G中的极大强连通子图称为G的强连通分量。显然，强连通图 只有一个强连通分量，即本身。非强连通图有多个强连通分量。
9、权和网	图中每一条边都可以附带有一个对应的数值，这种与边相关的数 值称为权。边上带有权的图称为带权图，也称作网。

寻找非强连通图的强连通分量:

① 在图中找有向环。

② 扩展该有向环：如果某个顶点到该环中任一顶点有路径，并且该环 中任一顶点到这个顶点也有路径，则加入这个顶点。

二,图的存储结构

1,邻接矩阵

（1）如果G是无向图，则： A[i][j]=1：若(i,j)∈E(G) 0:其他

（2）如果G是有向图，则： A[i][j]=1：若∈E(G) 0:其他

（3）如果G是带权无向图，则： A[i][j]= wij ：若i≠j且(i,j)∈E(G) 0：i=j ∞：其他

（4）如果G是带权有向图，则： A[i][j]= wij ：若i≠j且∈E(G) 0：i=j ∞：其他

结论:无向图的邻接矩阵是对称的,顶点i的度=第i行(列)中1的个数

特别:完全图的邻接矩阵中,对角线元素为0,其余元素为1

结论:有向图的邻接矩阵可能是不对称的,顶点的出度=第i行元素之和;顶点的入度=第i列元素之和

邻接矩阵的存储需要用到两个表,一个表位顶点表,用一维数组表示,里面存储顶点.第二个表表示邻接矩阵,用二维数组表示

#define MAXInt 32767 //表示无穷大
#define MVNum 100  //最大顶点数
typedef char VerTexType;//顶点的数据类型为char
typedef int ArcType;//设置边的权值为整型typedef struct {VerTexType vexs[MVNum];//顶点表ArcType arcs[MVNum][MVNum];//邻接矩阵int vexnum, arcnum; //图当前的顶点数和边数
}AMGraph;

无网图初始化:

//无向网
Status CreateUDN(AMGraph &G)
{                                       /／采用邻接矩阵表示法，创建无向网G 
cin>>G.vexnum>>G.arcnum;                /／输入总顶点数，总边数 for(i =0; i<G.vexnum; ++i) cin>>G.vexs[i];                     /／依次输入点的信息 for(i = 0; i<G.vexnum;++i)             /／初始化邻接矩阵 for(j=0;j<G.vexnum;++j) G.arcs[i][j] = Maxlnt;         /／边的权值均置为极大值 for(k = 0; k<G.arcnum;++k)
{                                        /／构造邻接矩阵 cin>>v1>>v2>>w;                     /／输入一条边所依附的顶点及边的权值 i = LocateVex(G, v1);j = LocateVex(G, v2);                 /／确定v1和v2在G中的位置 G.arcs[i][j]=W;                         /／边＜v1,v2＞的权值置为w G.arcs[j][i]= G.arcs[i][j];         /／置＜v1, v2＞的对称边＜v2,v1＞的权值为w 
} return OK; 
}

邻接矩阵的主要特点:

一个图的邻接矩阵表示是唯一的。

特别适合于稠密图的存储。邻接矩阵的存储空间为O(n2)

优点:只管,简单,好理解,方便寻找任意两顶点之间是否存在边,方便计算顶点的度

缺点:不便于增加和删除顶点,如果为稀疏图,就会有大量的无效元素,浪费空间;统计边数,浪费时间

2,邻接表

分为两种节点,一种是头节点,头节点分为两个部分一部分是顶点信息,另一部分是指向第一条依附于该顶点的边的指针.边节点,第一部分是该边所指向的顶点的位置,第二部分是指向下一条边的指针,第三部分是边的相关信息,例如权,顶点,按照编号的顺序将顶点数据储存在一维数组中,相关联的的边,用线性链表进行连接

无向图:

邻接表并不唯一,边节点的顺序不唯一,若无向图有n个顶点,e条边,则邻接表需要n个头节点和2e个边节点,所以空间复杂度为O(n+2e)

无向图中的顶点v1的度为第i个单链表中的节点数

有向图:如果为邻接表,那么头节点指向的是该顶点的出度边,逆邻接表头节点指向的是该顶点的入度边.

由此,邻接表出度为第i单链表中的节点数,找出度容易,找入度难需要遍历整个图才可知. 逆邻接表入度为第i单链表中的节点数,找入度容易,出度困难

有向图和网空间复杂度为O(n+e)

#define MVNum 100  //最大顶点数typedef struct VNode {VerTexType deta;ArcNode* firstarc;
}VNode,AdjList[MVNum];typedef int OtherInfo;typedef struct ArcNode {  //边节点int adjvex;  //该边所指向的顶点的位置struct ArcNode* nextarc;//指向下一条边的指针OtherInfo info;//和边相关的信息,例如:权
}ArcNode;
typedef struct {AdjList vertices;int vexnum, arcnum;//图当前的顶点数和边数
}ALGraph;

无向网的初始化:

//无向图
Status CreateUDG(ALGraph &G){      /／采用邻接表表示法，创建无向图G 
cin>>G.vexnum>>G.arcnum;           /／输入总顶点数，总边数 for(i = 0; i<G.vexnum; ++i)       /／输入各点，构造表头结点表
{ cin>> G.vertices[i].data;         /／输入顶点值G.vertices[i].firstarc=NULL;
}for(k = 0; k<G.arcnum;++k){ cin>>V1>>v2;                    /／输入一条边依附的两个顶点i = LocateVex(G, v1); j = LocateVex(G, v2);p1=new ArcNode;                 /／生成一个新的边结点＊p1p1->adjvex=j;                     /／邻接点序号为j p1->nextarc=G.vertices[i].firstarc; G.vertices[i].firstarc=p1;     /／将新结点＊p1插入顶点vi的边表头部p2=new ArcNode;                 /／生成另一个对称的新的边结点＊p2->adjvex=i;                     /／邻接点序号为i p2->nextarc= G.vertices[j].firstarc; G.vertices[j].firstarc=p2;         /／将新结点＊p2插入顶点vj的边表头部
}

邻接表的主要特点:

优点:方便找任意顶点的邻接点,节约稀疏图的空间,需要有向图:(n+e),无向图:(n+2e)的空间

缺点:有向图,不方便统计度的总数

联系:

邻接表中的一行对应邻接矩阵中的一行,邻接表中的节点个数等于邻接矩阵中一行非零元素的个数

区别:

邻接矩阵空间复杂度为O(n^2),邻接表的空间复杂度为O(n+1)

邻接矩阵是唯一的,但是邻接表不是唯一的

邻接矩阵适用于稠密图,邻接表适用于稀疏图

三,图的遍历

1,深度优先搜索

■在访问图中某一起始顶点 v后，由 v出发，访问它的任一邻接顶点 w;

■再从 w 出发，访问与 w邻接但还未被访问过的顶点 W2;

■然后再从 w2出发，进行类似的访问，…

■ 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。

■ 接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。

■ 如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；

■如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中 搜索 所有顶点都被访问过为止。

创建一个visited数组,用来储存该顶点是否被访问过:visited[i]=0表示顶点i没有访问；visited[i]=1表示顶点i已经访问过。

void DFS (AMGraph G,int v)
{cout<<v;visitd[v]=true;for(w=0;w<G.vexnum;W++){if(G.arcs[v][w]!=0&&(!visited[w]))DFS(G,w);}

邻接矩阵来扫描时间复杂度为O(n^2)

void DFS(ALGraph *G，int v){ArcNode *p; int w;visited[v]=1;                     //置已访问标记printf("%d "，v);                //输出被访问顶点的编号p=G->Adjlist[v].firstarc;        //p指向顶点v的第一条边的边头节点while (p!=NULL){w=p->adjvex;if (visited[w]==0)DFS(G，w);                  //若w顶点未访问，递归访问它p=p->nextarc;                  //p指向顶点v的下一条边的边头节点}}

邻接表来扫描,时间复杂度为O(n+e)

2,广度优先搜素

方法：从图的某一结点出发，首先依次访问该结点的所有邻点 Vi, Vib, …, Vi，再按这些顶点被访问的先后次序依次访问与它们相邻接的所有未被访问的顶点 重复此过程，直至所有顶点均被访问为止。

邻接表的BFS算法：

void BFS(ALGraph *G，int v){ArcNode *p; int w，i;int queue[MAXV]，front=0，rear=0;     //定义循环队列int visited[MAXV];for (i=0;i<G->n;i++)visited[i]=0;                     //访问标志数组初始化printf("%2d"，v);                        //输出被访问顶点的编号visited[v]=1;                        //置已访问标记rear=(rear+1)%MAXV;queue[rear]=v;//v进队while (front!=rear)                 //队列不空时循环{front=(front+1)%MAXV;w=queue[front];//出队并赋给wp=G->adjlist[w].firstarc;         //找w的第一个的邻接点while (p!=NULL){if (visited[p->adjvex]==0){printf(“%2d”，p->adjvex);     //访问之visited[p->adjvex]=1;rear=(rear+1)%MAXV;     //相邻顶点进队queue[rear]=p->adjvex;}p=p->nextarc;}}}

DFS算法和BFS算法比较:

空间复杂度相同,都是O(n)前者借用了堆栈,后者借用了队列

时间复杂度只与存储结构(邻接矩阵/邻接表)有关,与搜索路径无关

四,生成树和最小生成树

1,生成树的特点:

一个图有许多不同的生成树

生成树的顶点树与图的顶点数相同

生成树是图的极小连通子图,去掉一条边则非连通,再加一条边必然形成回路

有n个顶点的连通图的生成树有n-1条边

生成树中任意两个顶点之间的路径是唯一的

深度优先生成树/广度优先生成树

广度优先生成树高度 ≤ 深度优先生成树高度

2,最小生成树

对于带权连通图G,其中权 值之和最小的生成树称为图的最小生成树。最小生成树可能不唯一.

(1)普利姆算法Prim

初始化U={v}。v到其他顶点的所有边为候选边；重复以下步骤n-1次，使得其他n-1个顶点被加入到U中： 从候选边中挑选权值最小的边输出，设该边在V-U中的顶点是k，将 k加入U中；考察当前V-U中的所有顶点j，修改候选边：若(j，k)的权值小于原来和顶点k关联的候选边，则用(k，j)取代后者作为候选边。

(2)克鲁斯卡尔算法

设连通网 N=(V,E)，令最小生成树初始状态为只有 n个顶点而无边的非连通图7=(V, ()),每个顶点自成一个连通分量。 在E中选取代价最小的边，若该边依附的顶点落在 T中不同的连通分量上（即：不能形成环）则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边。 依此类推，直至7中所有顶 寿島大 点都在同一连通分量上为止。

	普利姆算法	克鲁斯卡尔算法
算法思想	选择点	选择边
时间复杂度	O(n^2)	O(elog2e)
适应范围	稠密图	稀疏图

五,最短路径

从源点到终点可能不止一条路径，把路径长度最短的那条路径 称为最短路径。

1,Dijkstra算法

1,单源最短路径(Dijkstra算法)

1．初始化：先找出从源点v0到各终点vk的直达路径（Vo.Vk), 即通过一条弧到达的路径。

2．选择：从这些路径中找出一条长度最短的路径（Vo,u)。

3更新：然后对其余各条路径进行适当调整： 若在图中存在弧（u,vk)，且（Vo,U)+(U.Vk)<(Vo,Vk), 则以路径（Vo,u,Vk）代替（Vo.v)。 在调整后的各条路径中，再找长度最短的路径， 依此类推。

按长度递增的顺序求出图的某顶点到其余顶点的最短路径

时间复杂度：O(n2)

2,Floyd算法

所有顶点间的最短路径(Floyd算法)

逐个顶点试探,从vi到vj的所以可能存在的路径中选出一条最短路径

时间复杂度：O(n3)

六,拓扑排序

设G=(V，E)是一个具有n个顶点的有向图(AOV/AOE)，V中顶点序列v1 ， v2 ，…，vn 称为一个拓扑序列，当且仅当该顶点序列满足下列条件： 若是图中的边（或从顶点i->j有一条路径）:则在拓扑序列中顶点i必须排在顶点j之前。在一个有向图中找一个拓扑序列的过程称为拓扑排序[有向图中不允许又回路]

拓扑排序步骤(AOV):

(1)在有向图中选一个没有前驱的顶点且输出

(2)从图中删除该顶点和所有以它为尾的弧

(3)重复上述两步,直到全部的顶点均已输出,或者图中不存在无前驱的顶点为止(代表有向图中有环)

七,关键路径

AOE网: 用一个带顶点权有向图（DAG）描述工程的预计进度。 表示事件，有向边表示活动，边e的权c(e)表示完成活动e所需的 时间（比如天数）。 图中入度为0的顶点表示工程的开始事件（如开工仪式），出度为0的 顶点表示工程结束事件

关键路径:从AOE网中源点到汇点的最长路径，具有最大长度的路径叫 关键路径。

事件v最早开始时间	规定源点事件的最早开始时间为0。定义图中任 一事件v的最早开始时间（early event）ee(v)
事件v最迟开始时间	定义在不影响整个工程进度的前提下，事件v必 须发生的时间称为v的最迟开始时间（late event） ，记作le(v)。
活动a的最早开始时间	e(a)指该活动起点x事件的最早开始时间，
活动a的最迟开始时间	l(a)指该活动终点y事件的最迟开始时间与该 活动所需时间之差

计算公式:

事件v最早开始时间	ee(v)=MAX{ee(x)+a，ee(y)+b，ee(z)+c}
事件v最迟开始时间	le(v)=MIN{le(x)-a，le(y)-b，le(z)-c}
活动a的最早开始时间	e(a)=ee(x)
活动a的最迟开始时间	l(a)=le(y)-c
关键活动:d(a)=l(a)-e(a)，若d(a)为0，则称活动a为关键活动

在AOE网中可能存在多条关键路径

关键活动不按期完成就会影响整个工程的完成时间

所有关键活动都提前完成，整个工程也将提前完成