pbixy2zje/ConsoleApplication1.cpp

#include<stdio.h>
#include<malloc.h>
#define maxn 10

//栈的结构体
typedef struct
{
	int top;
	int num[maxn];
}Stack;

//邻接表的边结点
typedef struct
{
	int data;
	int quan;
	struct Arcnode* next;
}Arcnode;

//邻接表的头结点

typedef struct
{
	int data;
	Arcnode* first;
}Vnode;

//图的结构体

typedef struct
{
	int vexnum, arcnum;
	Vnode Vnode[maxn];
}ALGraph;

//图的创建

int CreateGraph(ALGraph* G)
{
	int i;

	//先输入图的点数和边数
	printf("请输入图的点数和边数\n");
	scanf("%d%d", &G->vexnum, &G->arcnum);
	for (i = 0; i < G->vexnum; i++)
	{
		printf("请输入第%d个顶点的值\n", i + 1);
		scanf("%d", &G->Vnode[i].data);
		G->Vnode[i].first = NULL;
	}

	//在输入每条边所对应的两个结点，由于是无向图，所以插入链表时，两个顶点所对应的头结点的位置都要插入，采用头插法
	for (i = 0; i < G->arcnum; i++)
	{
		int j, k;
		Arcnode* p, * q;
		printf("请输入第%d条边的两个点\n", i + 1);
		scanf("%d%d", &j, &k);
		p = (Arcnode*)malloc(sizeof(Arcnode));
		p->data = k;
		p->next = G->Vnode[j].first;
		G->Vnode[j].first = p;
		q = (Arcnode*)malloc(sizeof(Arcnode));
		q->data = j;
		q->next = G->Vnode[k].first;
		G->Vnode[k].first = q;
	}
}

//输出邻接表结构
void showALGraph(ALGraph* G)
{
	int i;
	Arcnode* t;
	for (i = 0; i < G->vexnum; i++)
	{
		t = G->Vnode[i].first;
		printf("%d", G->Vnode[i].data);
		while (t)
		{
			printf("->%d", t->data);
			t = t->next;
		}
		printf("\n");
	}
}

//初始化栈
Stack* init()
{
	Stack* s;
	s = (Stack*)malloc(sizeof(Stack));
	if (s == NULL)
	{
		printf("分配失败\n");
		return 0;
	}
	s->top = -1;
	return s;
}
void push(Stack* s, int v)
{
	if (s->top == maxn - 1)
		return;
	s->num[++s->top] = v;
}
int pop(Stack* s)
{
	if (s->top == -1)
		return;
	else
		return s->num[s->top--];
}

//查看顶点是否在栈中
int check(Stack* s, int v)
{
	int i;
	for (i = 0; i <= s->top; i++)
	{
		if (v == s->num[i])
			return 1;
	}
	return 0;
}

//输出栈内数据，也就是路径
void show(Stack* s)
{
	int m = s->top;
	int a = 0;
	while (a <= m)
	{
		printf("%d", s->num[a++]);
	}
	printf("\n");
}

//找到该结点紧邻的第一个顶点
int findfirst(ALGraph* G, int i)
{
	Arcnode* p;
	if (G->Vnode[i].first)
	{
		p = G->Vnode[i].first;
		//printf("第一个顶点是%d\n",p->data);
		return p->data;
	}
	else
	{
		return -1;
	}
}

//找到该结点紧邻的下一个顶点
int findnext(ALGraph* G, int i, int v)
{
	Arcnode* p, * q;
	if (G->Vnode[v].first)
	{
		p = G->Vnode[v].first;
		while (p->data != i)
			p = p->next;
		q = p->next;
		if (q)
		{
			//printf("下一个顶点是%d\n",q->data);
			return q->data;
		}
		else
			return -1;
	}
	else
		return -1;
}

//深度优先算法
void DFS(int B, int E, Stack* s, ALGraph* G) {
	int i;
	push(s, B);
	if (E == B) {
		show(s);
		pop(s);
		return;
	}
	for (i = findfirst(G, B); i != -1; i = findnext(G, i, B)) {
		//show(s);
		if (check(s, i) && i != E)
			continue;
		DFS(i, E, s, G);
	}
	pop(s);
}
int main() {
	ALGraph G;
	Stack* s;
	s = init();
	CreateGraph(&G);
	showALGraph(&G);
	DFS(0, 2, s, &G);


}