图遍历算法的应用（包括输出长度为l的路径最短最长路径）

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

判断从顶点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("%2d", 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("%2d", 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("%2d", qu[i].data);

				i = qu[i].parent;

			}

			printf("%2d\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);

}