判断从顶点 u 到 v 是否有路径
- void ExistPath(AdjGraph* G, int u, int v, bool& has)
- {
- int w;
- ArcNode* p;
- visit[u] = 1;
- if (u == v)
- {
- has = true;
- return;
- }
- p = G->adjlist[u].firstarc;
- while (p != NULL)
- {
- w = p->adjvex;
- if (visit[w] == 0)
- ExistPath(G, w, v, has);
- p = p->nextarc;
- }
- }
输出 u 到 v 的一条简单路径
- void FindPath(AdjGraph* G, int u, int v, int path[], int d)
- {
- path[++d] = u;
- visit[u] = 1;
- if (u == v)
- {
- for (int i = 0; i <= d; i++)
- printf("%d", path[i]);
- printf("\n");
- return;
- }
- ArcNode* p = G->adjlist[u].firstarc;
- while (p != NULL)
- {
- if (visit[p->adjvex] == 0)
- FindPath(G, p->adjvex, v, path, d);
- p = p->nextarc;
- }
- }
输出 u 到 v 的所有简单路径, 回溯的深度优先搜索算法
- void FindAllPath(AdjGraph* G, int u, int v, int path[], int d)
- {
- path[++d] = u;
- visit[u] = 1;
- if (u == v)
- {
- for (int i = 0; i <= d; i++)
- printf("-", path[i]);
- printf("\n");
- }
- ArcNode* p = G->adjlist[u].firstarc;
- while (p!=NULL)
- {
- if (visit[p->adjvex] == 0)
- FindAllPath(G, p->adjvex, v, path, d);
- p = p->nextarc;
- }
- visit[u] = 0;
- }
输出 u 到 v 长度为 l 的路径
- void FindlenPath(AdjGraph* G, int u, int v, int l, int path[], int d)
- {
- path[++d] = u;
- visit[u] = 1;
- if (u == v && d == l)
- {
- for (int i = 0; i <= d; i++)
- printf("-", path[i]);
- printf("\n");
- }
- ArcNode* p = G->adjlist[u].firstarc;
- while (p != NULL)
- {
- if (visit[p->adjvex] == 0)
- FindlenPath(G, p->adjvex, v, l, path, d);
- p = p->nextarc;
- }
- visit[u] = 0;
- }
输出 u 到 v 的最短路径
- typedef struct {
- int data;
- int parent;
- }Queue;
- void ShortPath(AdjGraph* G, int u, int v)
- {
- int w;
- ArcNode* p;
- Queue qu[MAXV];
- int front = -1, rear = -1;
- int visit[MAXV] = { 0 };
- rear++;
- qu[rear].data = u;
- qu[rear].parent = -1;
- visit[u] = 1;
- while (front != rear)
- {
- front++;
- w = qu[front].data;
- if (w == v)
- {
- int i = front;
- while (qu[i].parent != -1)
- {
- printf("-", qu[i].data);
- i = qu[i].parent;
- }
- printf("-\n", qu[i].data);
- return;
- }
- p = G->adjlist[w].firstarc;
- while (p != NULL)
- {
- if (visit[p->adjvex] == 0)
- {
- rear++;
- qu[rear].data = p->adjvex;
- qu[rear].parent = front;
- visit[p->adjvex] = 1;
- }
- p = p->nextarc;
- }
- }
- }
求距离 u 最短的一个顶点
- int Maxdist(AdjGraph* G, int v)
- {
- ArcNode* p;
- int qu[MAXV];
- int rear = 0, front = 0;
- int visit[MAXV] = { 0 };
- int i, j, k;
- qu[++rear] = v;
- visit[v] = 1;
- while (rear != front)
- {
- front = (front + 1) % MAXV;
- k = qu[front];
- p = G->adjlist[k].firstarc;
- while (p != NULL)
- {
- if (visit[p->adjvex] == 0)
- {
- rear = (rear + 1) % MAXV;
- qu[rear] = p->adjvex;
- visit[p->adjvex] = 1;
- }
- p = p->nextarc;
- }
- }
- return k;
- }
输出经过 k 的所有简单路径
- void DFSPath(AdjGraph* G, int u, int v, int path[], int d)
- {
- int w, i;
- visit[u] = 1;
- path[++d] = u;
- ArcNode* p = G->adjlist[u].firstarc;
- while (p != NULL)
- {
- w = p->adjvex;
- if (w == v && d> 1)
- {
- printf(" ");
- for (i = 0; i <= d; i++)
- printf("%d", path[i]);
- printf("%d\n",v);
- }
- if (visit[w] == 0)
- DFSPath(G, w, v, path, d);
- p = p->nextarc;
- }
- visit[u] = 0;
- }
- void FindCirclePath(AdjGraph* G, int k)
- {
- int path[MAXV];
- DFSPath(G, k, k, path, -1);
- }
来源: http://www.bubuko.com/infodetail-3303153.html