|
判断无向图是否存在环：将图中结点状态标记为三种类型，白色代表未被访问（还未入递归栈），红色表示正在访问的结点（存在于递归栈中的结点），黑色表示已经访问结束的结点（出递归栈的结点）。深度优先搜索有向图，如果在搜索过程中遇到红色的结点，则图中存在环。
#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#define MAX_VERTEX_NUM 100
typedef char VertexType;
typedef struct ArcNode {
int adjvex;
struct ArcNode* nextArc;
}ArcNode;
typedef struct VNode {
VertexType data;
ArcNode* firstArc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertices;
int vexNum, arcNum;
int kind;
}ALGraph;
void createALGraph(ALGraph& G, VertexType VList[], int VListLength, int arcList[][2], int arcListLength, int kind) {
for (int i = 1; i adjvex = w;
pnode->nextArc = G.vertices[v].firstArc;
G.vertices[v].firstArc = pnode;
if (kind == 0) {
pnode = (ArcNode*)malloc(sizeof(ArcNode));
pnode->adjvex = v;
pnode->nextArc = G.vertices[w].firstArc;
G.vertices[w].firstArc = pnode;
}
}
G.vexNum = VListLength;
G.arcNum = arcListLength;
G.kind = kind;
}
int visited1[MAX_VERTEX_NUM] = { 0 };
void DFS(ALGraph G, VertexType v) {
printf("%d ", v);
visited1[v] = 1;
ArcNode* pnode = G.vertices[v].firstArc;
while (pnode != NULL) {
VertexType w = pnode->adjvex;
pnode = pnode->nextArc;
if (!visited1[w]) {
DFS(G, w);
}
}
}
void DFSTraves(ALGraph G) {
for (int i = 1; i adjvex;
pnode = pnode->nextArc;
if (visited2[w] == RED) {//在递归遍历栈中遇到红色结点
return 1;
}
else if (visited2[w] == WHITE) {//未被访问过，入递归栈进行DFS遍历
ret = DFSALGraph(G, w);
}
}
visited2[v] = BLACK;//顶点退出递归函数，更新顶点位置
return ret;//返回搜索结果
}
void isExistRing(ALGraph G) {
int ret = 0;
for (int index = 1; index adjvex;
pnode = pnode->nextArc;
if (k == w) {
return 1;
}
else if (!visited3[k]) {
ret = isExistPsth(G, k, w);
}
}
return ret;
}
int main() {
ALGraph G;
VertexType VList[MAX_VERTEX_NUM];
int VListLength;
int arcList[MAX_VERTEX_NUM][2];
int arcListLength;
int kind;
scanf("%d", &VListLength);
for (int i = 1; i |