(1) 有向图，无向图的邻接矩阵
（2） 网的邻接矩阵定义为：
a[i][j]:
（1） Wij 若<vi，vj> 或<vi，vj >∈VR（2）∞ 反之
（3）说明：
① 对于无向图，顶点vi的度是邻接矩阵中第i行（或第i列）的元素之和， TD（vi）= ∑ a[i][j]。
② 对于有向图，顶点VI的出度OD（vi）是邻接矩阵中第i行的元素之和，顶点vi的出度ID（vi）是邻接矩阵中第j列）的元素之和。
③ 邻接矩阵法求顶点的度。入度。出度的时间复杂度为O(|V|)。
④ A2 [1][2]:第一个顶点到第二个顶点路径为2的路径有多少条。
#define INFINITY INT_MAX
#define MAX_VERTEXT_NUM 20
typedef enum{DG,DN,AG,AN}GraphKind;
typedef struct ArcCell{VRType adj;//对无向图，用0,1表示是否相邻，对于带权图，为权值InfoType *info;//该弧相关信息的指针}RrcCell,AdjMatrix[MAX_VERTEXT_NUM][MAX_VERTEXT_NUM];//邻接矩阵
（1）代码：
//定义图的结构
typedef struct {VertextType exs[MAX_VERTEXT_NUM]; //顶点AdjMatrix arcs[MAX_VERTEXT_NUM][MAX_VERTEXT_NUM]; //边的邻接矩阵int vexnum,arcnum; //个数GraphKind kind;//有向图？无向图？
}MGraph;
（3）注意：
① 邻接矩阵法的空间复杂度O(|V|2),之和顶点数有关
② 更适合存储稠密图
③对于无向图而言，因为是对称矩阵，可以进行压缩存储
（4）压缩存储
| B[0] | B[1] | B[2] | B[3] | B[4] | B[n(n+1)/2-1] |
|---|---|---|---|---|---|
| a1,1 | a2,1 | a2,2 | a3,1 | a3,2 | an,n |
status CreateGraph(MGraph &G)
{scanf(&G.kind){case DG:return CreateDG(G);case DN:return CreateDN(G);case UDG:return CreateUDG(G);case UDN:return CreateDGN(G);default:return ERROR;}
}
//用无向图为例status CreateUDN(MGraph &G)
{scanf(&G.arcnum,&G.vexnum,&IncInfo);//输入点数和边数//给顶点进行数字化编号for(i=0;i<G.vexnum;i++){ scanf(&s[i]);//定义顶点数组（如果顶点本身就是1~n的数字无需这一步）}//初始化邻接矩阵for(i=0;i<G.vexnum;i++){for(j=0;j<G.vexnum;j++){G.arcs[i][j]={ININITY,NULL};}}//通过边数进行遍历for(k=0;k<G.arcnum;K++){scanf(&V1,&V2,&W);//输入邻接的连个顶点i=locatteVex(G,V1);j=locateVex(G,V2);//查找V1,V2的位置G.arcs[i][j].adj=w;//给邻接矩阵赋值if(IncInfo){INPUT(*G.arcs[i][j].info);}G.arcs[j][i]=G.arcs[i][j];//由于是无向图，对称}return ok;
}优点：
缺点：
———————
| data | firstarc |
———————
——————————
| adjvex | info | nextarc |
——————————
#define MAX_VERTEXT_NUM 20
//建立边结点
typedef struct ArcNode {int adjvex; // 该弧所指向的顶点的位置struct ArcNode *nextarc; // 指向下一条弧InfoType *info; // 该弧相关信息（可选）
}ArcNode;
// 顶点结点
typedef struct VNode{VertexType data; // 顶点信息ArcNode *firstarc; // 指向第一条依附该顶点的弧
}VNode,AdjList[MAX_VERTEXT_NUM];
//邻接表
typedef struct {Adjlist vertices;int vexnum,arcnum;int kind;
}ALGraph;
//建立邻接表算法
//初始化一个结点总数为num的图，k为图的类型，num为结点总数
void InitG(ALGraph G,enum GraphKind k,int num)
{G.kind=k;G.vexnum=num;G.vertices=new VNode[vexnum];for(int i=0;i<G.vexnum;i++){G.vertices[i].Firstarc=NULL;cin>>G.vertics[i].data;}
}//有向图(网)增加弧的算法，将弧(from,to,weight)加入图
void InsertArc(ALGragh G,int from,int to,int weight)
{ArcNode *s=new ArcNode;s->weight=weight;s->adjvex=to;s->nextarc=G.vertices[from].firstarc;//插到链表vertices[from]的头G.vertices[from].firstarc=s;
}（1）在邻接表中，同一条边对应两个结点。
（2）无向图中顶点v的度：等于v 对应的链表的长度；但是，在有向图中，要求顶点A的的入度，则需要遍历所有的顶点连接的链表，判断有几个存在顶点A；求出度，则是A顶点链表有几个点。
（3）判定两顶点v，w是否邻接：要看v对应的链表中有无对应的结点w（相反判断也行）；
（4）对于一个图，给定的邻接表是并不唯一的（区分与邻接矩阵）
（5）增减边：要在两个单链表插入、删除结点；
（6）占用存储空间与顶点数、边数均有关；适用于边稀疏的图
| 时间复杂度 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 无向图 | O(1) | O(1)~O(V) |
| 有向图 | O(1) | O(1)~O(V) |
| 时间复杂度 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 无向图 | O(V) | O(1)~O(V) |
| 有向图 | O(V) | 出边：O(1)~O(V) 入边：O(E) |
| 时间复杂度 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 无向图 | O(1) | O(1) |
| 有向图 | O(1) | O(1) |
| 时间复杂度 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 无向图 | O(V) | O(1)~O(E) |
| 有向图 | O(V) | 删出边：O(1)~O(V) 删入边：O(E) |
| 时间复杂度 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 无向图 | O(1) | O(1) |
| 有向图 | O(1) | O(1)~O(V) |
| 时间复杂度 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 无向图 | O(1)~O(V) | O(1) |
| 有向图 | O(1)~O(V) | 找出边连接点：O(1) 找入边邻接点：O(1)~O(E) |
| 时间复杂度 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 无向图 | O(1)~O(V) | O(1) |
| 有向图 | O(1) | O(1)~O(V) |
重点是 6、7
1、定义——从某顶点出发，沿着一些边访问连通图中所有顶点，且使每个顶点仅访问一次的运算。
2、为避免重复访问，可设置辅助数组Visited[ ]，各分量初值为0，当顶点被访问，对应分量被置为1。
3、方法——深度优先（depth first search DFS）
广度优先（breadth first search BFS）
从图中某个顶点V0 出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到。
- 从深度优先搜索遍历连通图的过程类似于树的先根遍历；
- 如何判别V的邻接点是否被访问？
解决的办法是：为每个顶点设立一个 “访问标志数组bool visited[vexnum]”。
int visited[MAX];//设置一个数组，判断是否遍历过，false/1为遍历过
void DFGTraverse(Graph G,int v)
{for(v=0;v<G.vexnum;v++)visited[v]=0;//初始化判断数组for(v=0;v<G.vexnum;v++){if(!visited[v])//如果没有遍历过DFS(G,V);//进行遍历}
}
void DFS(Graph G,int v)//进行递归遍历
{visited[v]=1;printf(v);//改变判断数组，输出点for(w=FirstVex(G,v);w!=0;w=NextVex(G,v))//从每一行第一个邻接矩阵值为1的，跳转到下一个值为1的{if(!visited[w])DFS(G,v);}
}
int FirstVex(Graph G,int v)//判断第一个不是0的
{int i;for(i=0;i<G.vexnum;i++){if(G.arcs[v][i]==1&&visited[i]==False)return i;}return -1;
}
void NextVex(Graph G,int v)//判断下一个不是0的
{int i;for(i=w;i<G.vexnum;i++){if(G.arcs[v][i]==1&&visited[i]!=False)return i;}return -1;
}
2.邻接表
void DFS(Graph G,int v)
{cout<<G.vertices[v].data<<" ";visited[v]=true;ArcNode *p=G.vertices[v].firstarc;while(p!=NULL){int w=p->adjvex;if(!visited[w])DFS(G,w);p=p->nextarc;a}
}
采用邻接表存储实现无向图的广度优先遍历
//visited是访问标记数组//处理非连通图的情况
bool BFSTraverse(Graph G){for(int i=0;i<G.vexnum;++i)visited[i] = false;InitQueue(Q);for(int i=0;i<G.vexnum;++i){if(!visited[i])BFS(G,i);}
}void BFS(Graph G,int v){visit(v); //访问v顶点 visited[v] = True; //修改该顶点对应数组的值为true EnQueue(Q,v); //入队 while(!isEmpty(Q)){ //不空还有未遍历到的节点 DeQueue(Q,v); //出队v for(w = FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)) //找到所有符合条件的邻接节点 if(!visited[w]){ //w是否被访问 visit[w]; //访问 visited[w] = true; //修改该顶点对应数组的值为trueEnQueue(Q,w); //入队 }}
}
bool BFSTraverse(Graph G，int v){for(int i=0;i<G.vexnum;++i)visited[i] = false;InitQueue(Q);for(int i=0;i<G.vexnum;++i){if(!visited[i])visit(v); //访问v顶点 visited[v] = True; //修改该顶点对应数组的值为true EnQueue(Q,v); //入队 while(!isEmpty(Q)){ //不空还有未遍历到的节点 DeQueue(Q,v); //出队v for(w = FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)) //找到所有符合条件的邻接节点 if(!visited[w]){ //w是否被访问 visit[w]; //访问 visited[w] = true; //修改该顶点对应数组的值为trueEnQueue(Q,w); //入队 }}}
}
① 如果使用邻接表，则从同一个顶点广度优先遍历序列会随着链接表不同而不同，但是由于邻接矩阵是唯一的，所以从同一个广度优先遍历得到的顺序是唯一的。
② 对于无向图，调用BFS函数的次数=连通分量数
③ 空间复杂度：O(|V|)
④ 时间复杂度：
a.使用邻接矩阵存储的图：访问|V|个顶点的需要O(|V|)的时间，查找每个顶点的邻接点都需要O(|V|)的时间，而总共有|V|个顶点，时间复杂度=O(|V|2)+o(|V|)=O(|V|2)。
b.使用邻接表的图：访问|V|个顶点的需要O(|V|)的时间，查找各个顶点的邻接点都需要O(|E|)的时间，时间复杂度=O(|V|)+o(|E|)。
① 通过广度优先遍历可以的得到一棵遍历树
② 由于邻接表不唯一，则树不唯一；由于邻接矩阵唯一，则树唯一。
伞 遍历非连通图，可以得到广度优先生成森林。
（1）对于无向图而言，调用BFS/DFS的次数=连通分量数。
（2）对于有向图而言，若起始顶点到其他顶点都有路径，则只需调用一次BFS/DFS函数。对于强连通图，从任一结点出发只需调用1次BFS/DFS函数。
本文发布于:2024-01-29 17:45:42，感谢您对本站的认可！
本文链接：https://www.4u4v.net/it/170652154717187.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
| 留言与评论（共有 0 条评论） |
