定义:
图是一种网状数据结构,是由一个顶点的有穷非空集V(G)和一个弧(arc)的集合E(G)组成,通常记作G=(V,E),其中G表示一个图,V是图G中点的集合,E是图G中弧的集合。
存储结构:
- 邻接矩阵,用一个一维数组来存储G的顶点,用一个相对应的二维数组来存储G的弧。
queue<char> q;
#define MVNum 100
bool Visited[MVNum];
typedef struct AMGraph {
char vexs[MVNum]; //顶点表
int arcs[MVNum][MVNum]; //邻接矩阵
int vexnum, arcnum; //当前的顶点数和边数
}AMGraph;
int LocateVex(AMGraph& G, char v) { //找到顶点v的对应下标
for (int i = 0; i < G.vexnum; i++) {
if (G.vexs[i] == v) return i;
}
}
int CreateUDG_1(AMGraph& G) { //邻接矩阵创建无向图
char v1, v2;
cin >> G.vexnum >> G.arcnum;
getchar();
for (int i = 0; i < G.vexnum; i++) {
cin >> G.vexs[i];
}
for (int i = 0; i < G.vexnum; i++) {
for (int j = 0; j < G.vexnum; j++) {
G.arcs[i][j] = 0;
}
}
for (int k = 0; k < G.arcnum; k++) {
getchar();
cin >> v1 >> v2;
int i = LocateVex(G, v1);
int j = LocateVex(G, v2);
G.arcs[i][j] = G.arcs[j][i] = 1;
}
return 1;
}
void BFS_AM(AMGraph& G, char v0) { //广度优先遍历
int u, i, v, w;
v = LocateVex(G, v0);
cout << v0;
Visited[v] = 1;
q.push(v0);
while (!q.empty()) {
u = q.front();
v = LocateVex(G, u);
q.pop();
for (int i = 0; i < G.vexnum; i++) {
w = G.vexs[i];
if (G.arcs[v][i] && !Visited[i]) {
cout << w;
q.push(w);
Visited[i] = 1;
}
}
}
}
-
邻接表,为每一个顶点建立一个单链表存放与它相邻的边
顶点表,顺序存储 ,每个数组元素存放顶点的数据和边表的头指针
边表,链式存储,单链表中存放与一个顶点相邻的所有边,一个链表节点表示一条从该顶点到链表结点顶点的边
queue<char> q;
#define MVNum 100
bool Visited[MVNum];
typedef struct ArcNode { //边结点
int adjvex;
ArcNode* nextarc;
int info;
}ArcNode;
typedef struct VexNode { //表头结点
char data;
ArcNode* firstarc;
}VexNode,AdjList[MVNum];
typedef struct ALGraph {
AdjList vertices;
int vexnum, arcnum;
}ALGraph;
int LocateVex(ALGraph& G, char v) {
for (int i = 0; i < G.vexnum; i++) {
if (v == G.vertices[i].data) return i;
}
}
int CreateUDG_2(ALGraph& G) { //邻接表创建无向图
char v1, v2;
cin >> G.vexnum >> G.arcnum;
getchar();
for (int i = 0; i < G. vexnum; i++) {
cin >> G.vertices[i].data;
G.vertices[i].firstarc = NULL;
}
for (int k = 0; k < G.arcnum; k++) {
getchar();
cin >> v1 >> v2;
int i = LocateVex(G, v1);
int j = LocateVex(G, v2);
ArcNode* p1 = new ArcNode;
p1->adjvex = j;
p1->nextarc = G.vertices[i].firstarc;
G.vertices[i].firstarc = p1;
ArcNode* p2 = new ArcNode;
p2->adjvex = i;
p2->nextarc = G.vertices[j].firstarc;
G.vertices[j].firstarc = p1;
}
return 1;
}
void BFS_AL(ALGraph& G, char v0) {
int u, w, v;
ArcNode* p;
cout << v0;
v = LocateVex(G, v0);
Visited[v] = 1;
q.push(v0);
while (!q.empty()) {
u = q.front();
v = LocateVex(G, u);
q.pop();
for (p = G.vertices[v].firstarc; p; p = p->nextarc) {
w = p->adjvex;
if (!Visited[w]) {
cout << G.vertices[w].data;
Visited[w] = 1;
q.push(G.vertices[w].data);
}
}
}
}
- 非连通图的广度优先遍历
void BFS(AMGraph G) {
int v;
for (v = 0; v < G.vexnum; v++) Visited[v] = 0;
for (v = 0; v < G.vexnum; v++)
if (!Visited[v]) BFS_AM(G, G.vexs[v]);
}