图的存储和遍历C++实现
最近在做一些OJ题目时,感觉自己图的应用还不够熟练。所以又翻书看别人的博客复习了一下,现把图的常用内容总结如下:图的常用存储方法有:邻接矩阵和邻接表遍历方法有:按深度遍历(DFS),按广度遍历(BFS)下面的代码都是C++写的,用了一些STL库的容器:邻接矩阵:#include#include typedefstruct
·
最近在做一些OJ题目时,感觉自己图的应用还不够熟练。所以又翻书看别人的博客复习了一下,现把图的常用内容总结如下:
图的常用存储方法有:邻接矩阵和邻接表
遍历方法有:按深度遍历(DFS),按广度遍历(BFS)
下面的代码都是C++写的,用了一些STL库的容器:
邻接矩阵:
#include <stdio.h>
#include <stdlib.h>
typedef
structGraph
{
char vexs[100];
//顶点表
int arc[100][100];
//邻接矩阵,可看作边
int
numVertexes, numEdges;
//图中当前的顶点数和边数
}g;
//定位
int
locates(Graph *g,
char
ch)
{
int
i = 0;
for
(i = 0; i < g->numVertexes; i++)
{
if
(g->vexs[i] == ch)
{
break
;
}
}
if
(i >= g->numVertexes)
{
return
-1;
}
return
i;
}
//建立一个无向网图的邻接矩阵表示
void
CreateGraph(Graph *g)
{
int
i, j, k, w;
printf
(
"输入顶点数和边数:\n"
);
scanf
(
"%d,%d"
, &(g->numVertexes), &(g->numEdges));
for
(i = 0; i < g->numVertexes; i++)
{
g->vexs[i] =
getchar
();
while
(g->vexs[i] ==
'\n'
)
{
g->vexs[i] =
getchar
();
}
}
for
(i = 0; i < g->numEdges; i++)
{
for
(j = 0; j < g->numEdges; j++)
{
g->arc[i][j] = INFINITY;
//邻接矩阵初始化
}
}
for
(k = 0; k < g->numEdges; k++)
{
char
p, q;
printf
(
"输入边(vi,vj)上的下标i,下标j和权值:\n"
);
p =
getchar
();
while
(p ==
'\n'
)
{
p =
getchar
();
}
q =
getchar
();
while
(q ==
'\n'
)
{
q =
getchar
();
}
scanf
(
"%d"
, &w);
int
m = -1;
int
n = -1;
m = locates(g, p);
n = locates(g, q);
if
(n == -1 || m == -1)
{
fprintf
(stderr,
"there is no this vertex.\n"
);
return
;
}
//getchar();
g->arc[m][n] = w;
g->arc[n][m] = g->arc[m][n];
//因为是无向图,矩阵对称
}
}
//打印图
void
printGraph(Graph g)
{
int
i, j;
for
(i = 0; i < g.numVertexes; i++)
{
for
(j = 0; j < g.numVertexes; j++)
{
printf
(
"%d "
, g.arc[i][j]);
}
printf
(
"\n"
);
}
}
int
main(
int
argc,
char
**argv)
{
Graph g;
//邻接矩阵创建图
CreateGraph(&g);
printGraph(g);
return
0;
}
基于邻接矩阵的深度优先遍历(DFS)(类似二叉树的前序遍历)(用递归):
#define MAXVEX 100 //最大顶点数
int visited[MAXVEX];
//访问标志数组
#define TRUE 1
#define FALSE 0
//邻接矩阵的深度优先递归算法
void
DFS(Graph g,
int
i)
{
int
j;
visited[i] = TRUE;
printf
(
"%c "
, g.vexs[i]);
//打印顶点,也可以其他操作
for
(j = 0; j < g.numVertexes; j++)
{
if
(g.arc[i][j] == 1 && !visited[j])
{
DFS(g, j);
//对为访问的邻接顶点递归调用
}
}
}
//邻接矩阵的深度遍历操作
void
DFSTraverse(Graph g)
{
int
i;
for
(i = 0; i < g.numVertexes; i++)
{
visited[i] = FALSE;
//初始化所有顶点状态都是未访问过状态
}
for
(i = 0; i < g.numVertexes; i++)
{
if
(!visited[i])
//对未访问的顶点调用DFS,若是连通图,只会执行一次
{
DFS(g,i);
}
}
}
//邻接矩阵的广度遍历算法
#include<queue>
void
BFSTraverse(Graph g)
{
int
i, j;
q
ueue<int> q;
for
(i = 0; i < g.numVertexes; i++)
{
visited[i] = FALSE;
}
for
(i = 0; i < g.numVertexes; i++)
//对每个顶点做循环
{
if
(!visited[i])
//若是未访问过
{
visited[i] = TRUE;
printf
(
"%c "
, g.vexs[i]);
//打印结点,也可以其他操作
q.push(i);
//将此结点入队列
while
(!q.empty())
//将队中元素出队列,赋值给
{
int
m;
m=q.front();
q.pop();
for
(j = 0; j < g.numVertexes; j++)
{
//判断其他顶点若与当前顶点存在边且未访问过
if
(g.arc[m][j] == 1 && !visited[j])
{
visited[j] = TRUE;
printf
(
"%c "
, g.vexs[j]);
q.push(j);
}
}
}
}
}
}
邻接表结构:
#include <stdio.h>
#include<stdlib.h>
#define MAXVEX 1000 //最大顶点数
typedef
struct
EdgeNode
//边表结点
{
int
adjvex;
//邻接点域,存储该顶点对应的下标
int weigth;
//用于存储权值,对于非网图可以不需要
struct
EdgeNode *next;
//链域,指向下一个邻接点
}EdgeNode;
typedef
struct
VertexNode
//顶点表结构
{
char data;
//顶点域,存储顶点信息
EdgeNode *firstedge;
//边表头指针
}VertexNode, AdjList[MAXVEX];
typedef
struct
{
AdjList adjList;
int
numVertexes, numEdges;
//图中当前顶点数和边数
}GraphList;
int
Locate(GraphList *g,
char
ch)
{
int
i;
for
(i = 0; i < MAXVEX; i++)
{
if
(ch == g->adjList[i].data)
{
break
;
}
}
if
(i >= MAXVEX)
{
fprintf
(stderr,
"there is no vertex.\n"
);
return
-1;
}
return
i;
}
//建立图的邻接表结构
void
CreateGraph(GraphList *g)
{
int
i, j, k;
EdgeNode *e;
EdgeNode *f;
printf
(
"输入顶点数和边数:\n"
);
scanf
(
"%d,%d"
, &g->numVertexes, &g->numEdges);
//建立顶点表
for
(i = 0; i < g->numVertexes; i++)
{
printf
(
"请输入顶点%d:\n"
, i);
g->adjList[i].data =
getchar
();
//输入顶点信息
g->adjList[i].firstedge = NULL;
//将边表置为空表
while
(g->adjList[i].data ==
'\n'
)
{
g->adjList[i].data =
getchar
();
}
}
//建立边表
for
(k = 0; k < g->numEdges; k++)
{
printf
(
"输入边(vi,vj)上的顶点序号:\n"
);
char
p, q;
p =
getchar
();
q =
getchar
();
int
m, n;
m = Locate(g, p);
n = Locate(g, q);
e = (EdgeNode *)
malloc
(
sizeof
(EdgeNode));//向内存申请空间,生成边表结点
e->adjvex = n;
e->next = g->adjList[m].firstedge;//将e指针指向当前顶点指向的结构
g->adjList[m].firstedge = e;//将当前顶点的指针指向e
f = (EdgeNode *)
malloc
(
sizeof
(EdgeNode));
f->adjvex = m;
f->next = g->adjList[n].firstedge;
g->adjList[n].firstedge = f;
}
}
void
printGraph(GraphList *g)
{
int
i = 0;
while
(g->adjList[i].firstedge != NULL && i < MAXVEX)
{
printf
(
"顶点:%c "
, g->adjList[i].data);
EdgeNode *e = NULL;
e = g->adjList[i].firstedge;
while
(e != NULL)
{
printf
(
"%d "
, e->adjvex);
e = e->next;
}
i++;
printf
(
"\n"
);
}
}
int
main(
int
argc,
char
**argv)
{
GraphList g;
CreateGraph(&g);
printGraph(&g);
return
0;
}
基于邻接表存储结构的深度优先遍历
//邻接表的深度递归算法
void DFS(GraphList g,int i)
{
EdgeNode *p;
visit[i] = 1;
printf("%c",g->adjList[i].data);
p = g->adjList[i].firstedge;
while(p)
{
if(!visited[p->adjvex])
{
DFS(g,p->adjvex);
}
p = p->next;
}
}
//邻接表的深度遍历操作
void DFSTraverse(GraphList g)
{
int i;
for(i=0;i<g.numVertexes;i++)
{
visited[i] = 0;
}
for(i=0;i<g.numVertexes;i++)
{
if(!visited[i])
{
DFS(g,i);
}
}
}
对比两个不同的存储结构的深度优先遍历算法,对于n个顶点e条边的图来说,邻接矩阵由于是二维数组,要查找某个顶点的邻接点需要访问矩阵中的所有元素,因为需要O(n2)的时间。而邻接表做存储结构时,找邻接点所需的时间取决于顶点和边的数量,所以是O(n+e)。显然对于点多边少的稀疏图来说,邻接表结构使得算法在时间效率上大大提高。
基于邻接表的广度优先遍历:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
//邻接表的广度遍历算法
#include<queue>
void
BFSTraverse(GraphList g)
{
int
i;
EdgeNode *p;
queue q;
for
(i = 0; i < g.numVertexes; i++)
{
visited[i] = 0;
}
for
(i = 0; i < g.numVertexes; i++)
{
if
(!visited[i])
{
visited[i] = 1;
printf
(
"%c "
, g.adjList[i].data);
//打印顶点,也可以其他操作
q.push(i);
while
(!q.empty())
{
int
m;
m = q.front();
q.pop();
p = g.adjList[m].firstedge; 找到当前顶点边表链表头指针
while
(p)
{
if
(!visited[p->adjvex])
{
visited[p->adjvex] = 1;
printf
(
"%c "
, g.adjList[p->adjvex].data);
q.push(p->adjvex);
}
p = p->next;
}
}
}
}
}
|
更多推荐
已为社区贡献1条内容
所有评论(0)