数据结构-图-基本运算
文章目录
- 定义
- 存储结构
- 结构体定义
- 邻接表创建图
- 输出图G
- 销毁图
- 邻接矩阵与邻接表的相互转化
- 图的遍历
- 深度优先搜索
- 广度优先搜索
- 判断图是否连通
- 主函数调用测试
- 结果
定义
图G由两个集合V和E组成，记为G=(V,E)，其中V是顶点的有限集合，记为V(G), E是连接V中两个不同顶点（顶点对）的边的有限集合，记为E(G)存储结构
- 邻接矩阵
- 邻接表
- 十字链表
- 邻接多重表
#include
#include
#include
using namespace std;
#define MAXV 100
#define INF 32767
typedef struct {
int num;
// 序号
int data;
}VertexType;
// 顶点类型typedef struct {
int edges[MAXV][MAXV];
// 邻接矩阵数组
int n,e;
// 顶点数，边数
VertexType vertex[MAXV];
// 顶点
}MatGraph;
// 图的邻接表表示
typedef struct ANode {//边结点类型
int adjvex;
//该边邻接点编号
struct ANode *nextarc;
int weight;
}ArcNode;
typedef struct Vnode{// 头结点类型
VertexType data;
// 顶点信息
int count;
// 增加数据域：存放顶点入度
ArcNode *firstarc;
}VNode;
typedef struct {
VNode adjlist[MAXV];
int n;
int e;
}AdjGraph;
// 用一个头节点数组构造的图 邻接表创建图
// 用邻接表创建图
void CreateAdj(AdjGraph *&G,int A[MAXV][MAXV], int n, int e)
{
int i,j;
ArcNode* p;
G = (AdjGraph*)malloc(sizeof(AdjGraph));
for(i=0;
iadjlist[i].firstarc = NULL;
for(i=0;
i=0;
j--)
{
if(A[i][j] !=0&&A[i][j]!=INF)
{
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = j;
p->weight = A[i][j];
p->nextarc = G->adjlist[i].firstarc;
G->adjlist[i].firstarc = p;
}
}
G->n = n , G->e = e;
}
输出图G
//输出图G
void DispAdj(AdjGraph *G)
{
int i;
ArcNode *p;
for(i=0;
in;
i++)
{
p = G->adjlist[i].firstarc;
printf("%3d:",i);
while(p!=NULL)
{
printf("%3d[%d]->",p->adjvex,p->weight);
p = p->nextarc;
}
cout << "^\n";
}
} 销毁图
// 销毁图
void DestroyAdj(AdjGraph *&G)
{
int i;
ArcNode *pre, *p;
for(i=0;
in;
i++)
{
pre = G->adjlist[i].firstarc;
if(pre!=NULL)
{
p = pre->nextarc;
while(p!=NULL)
{
free(pre);
pre = p;
p = p->nextarc;
}
free(pre);
}
}
free(G);
}
邻接矩阵与邻接表的相互转化
// 邻接矩阵转邻接表复杂度：O(n^2)
void MatToList(MatGraph g, AdjGraph *&G)
{
int i,j;
ArcNode *p;
G = (AdjGraph*)malloc(sizeof(AdjGraph));
for(i=0;
in;
i++)
G->adjlist[i].firstarc = NULL;
for(i=0;
i=0;
j--)
if(g.edges[i][j]!=0&&g.edges[i][j]!=INF)
{
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = j;
p->weight = g.edges[i][j];
p->nextarc = G->adjlist[i].firstarc;
G->adjlist[i].firstarc = p;
}
G->n = g.n;
G->e = g.e;
} // 邻接表转邻接矩阵复杂度 O(n+e)
void ListToMat(AdjGraph *G, MatGraph &g)
{
int i;
ArcNode *p;
for(i=0;
in;
i++)
{
p = G->adjlist[i].firstarc;
while(p!=NULL)
{
g.edges[i][p->adjvex] = p->weight;
p = p->nextarc;
}
}
g.n = G->n;
g.e = G->e;
}
图的遍历 深度优先搜索
int visited[MAXV]={0};
// 深度优先搜索 DFSO(n+e)
void DFS(AdjGraph *G,int v)// 遍历连通图
{
ArcNode *p;
visited[v] = 1;
printf("%2d",v);
p = G->adjlist[v].firstarc;
while(p!=NULL)
{
if(visited[p->adjvex] == 0)
DFS(G,p->adjvex);
p = p->nextarc;
}
}void DFS1(AdjGraph *G)// 遍历非连通图
{
for(int i=0;
in;
i++)
if(visited[i]==0) DFS(G,i);
}
广度优先搜索
// 广度优先搜索O(n^2)
void BFS(AdjGraph *&G, int v)// 遍历连通图
{
int w;
ArcNode *p;
int visited[MAXV] ={0};
visited[v] = 1;
printf("%2d",v);
deque de;
de.push_back(v);
while(!de.empty())
{
w = *de.begin();
de.pop_front();
p = G->adjlist[w].firstarc;
while(p!=NULL){
if(visited[p->adjvex] == 0)
{
printf("%2d",p->adjvex);
visited[p->adjvex] = 1;
de.push_back(p->adjvex);
}
p = p->nextarc;
}
}
cout << endl;
} void BFS1(AdjGraph *G)// 遍历非连通图
{
for(int i=0;
in;
i++)
if(visited[i]==0) BFS(G,i);
} 判断图是否连通
bool Connect(AdjGraph *G)
{
int i;
bool flag = true;
for(int i=0;
in;
i++)
visited[i] = 0;
DFS(G,0);
for(int i=0;
in;
i++)
if(visited[i]==0)
{
flag = false;
break;
} return flag;
}
主函数调用测试
int main()
{
int A[MAXV][MAXV] = {
{0,28,INF,INF,INF,10,INF},
{26,0,16,INF,INF,INF,14},
{INF,16,0,12,INF,INF,INF},
{INF,INF,12,0,22,INF,18},
{INF,INF,INF,22,0,25,24},
{10,INF,INF,INF,25,0,INF},
{INF,14,INF,18,24,INF,0}
};
AdjGraph *G;
int n = 7,e = 18;
CreateAdj(G,A,n,e);
DispAdj(G);
cout << "广度优先搜索产生的序列为： ";
BFS(G,0);
cout << "深度优先搜索产生的序列为： ";
DFS(G,0);
cout << endl;
//cout << "图G是否连通： ";
//printf(" %d",Connect(G));
DestroyAdj(G);
return 0;
}
结果
文章图片
P.S：马上考试了，我还在写博客，但我觉得这才是正确的复习方式，hahahha太真实了…
