6.3图的遍历
2.试设计一个算法,判断一个无向图G是否为一棵树。若是一棵树,则算法返回true,否则返回false。
#include <cstdio>
#include <cstring>
#define MaxVertexNum 100
typedef char VertexType;
typedef int EdgeType;
typedef struct {
VertexType Vex[MaxVertexNum][MaxVertexNum];
EdgeType Edge[MaxVertexNum][MaxVertexNum];
int vexnum, arcnum;
} MGraph;
bool visited[MaxVertexNum];
int getIndex(MGraph &G, char *s)
{
for (int i = 0; i < G.vexnum; i++) {
if (strcmp(s, G.Vex[i]) == 0)
return i;
}
return -1;
}
void CreateGraph(MGraph &G)
{
scanf("%d%d", &G.vexnum, &G.arcnum);
for (int i = 0; i < G.vexnum; i++)
scanf("%s", G.Vex[i]);
for (int i = 0; i < G.vexnum; i++)
for (int j = 0; j < G.vexnum; j++)
G.Edge[i][j] = 0;
char a[5], b[5];
int k = 0, u, v;
while (k < G.arcnum) {
scanf("%s%s", a, b);
u = getIndex(G, a);
v = getIndex(G, b);
G.Edge[u][v] = 1;
G.Edge[v][u] = 1;
k++;
}
}
void PrintGraph(MGraph G)
{
for (int i = 0; i < G.vexnum; i++) {
for (int j = -1; j < G.vexnum; j++) {
printf("%4d", G.Edge[i][j]);
}
printf("\n");
}
}
void visit(int n)
{
printf("%d ", n);
}
int FirstNeighbor(MGraph G, int v)
{
for (int i = 0; i < G.vexnum; i++)
if (G.Edge[v][i] == 1) return i;
return -1;
}
int NextNeighbor(MGraph G, int v, int w)
{
for (int i = w + 1; i < G.vexnum; i++)
if (G.Edge[v][i] == 1) return i;
return -1;
}
void DFS(MGraph &G, int v, int &Vnum, int &Enum, bool *visited)
{
visited[v] = true;
Vnum++;
int w = FirstNeighbor(G, v);
while (w != -1) {
Enum++;
if (!visited[w])
DFS(G, w, Vnum, Enum, visited);
w = NextNeighbor(G, v, w);
}
}
bool isTree(MGraph &G)
{
for (int i = 1; i < G.vexnum; i++) visited[i] = false;
int Vnum = 0, Enum = 0;
DFS(G, 1, Vnum, Enum, visited);
if (Vnum == G.vexnum && Enum == 2 * (G.vexnum - 1)) return true;
else return false;
}
int main()
{
MGraph G;
CreateGraph(G);
PrintGraph(G);
if (isTree(G)) printf("yes\n");
else printf("no\n");
return 0;
}
/*
8 7
v1 v2 v3 v4 v5 v6 v7 v8
v1 v2
v1 v3
v2 v4
v2 v5
v3 v6
v3 v7
v5 v8
*/