main.cpp

浙江工商大学 计算机与信息工程学院实验报告

#include <iostream>
using namespace std;

class Graph
{
private:
	typedef struct N
	{
		int data;
		struct N *next;
	}GPH;
	typedef GPH * GP;
	GP p;

	bool *visit;
	int len;

	void dfs(int n)
	{
		GP q;

		cout << n + 1 << " ";
		visit[n] = true;
		for (q = p[n].next ; q ; q = q->next)
			if (!visit[q->data])
				dfs(q->data);
	}

public :
	Graph (int n)
	{
		//n is the number of vertex
		
		len = n;

		p = new GPH[n];
		visit = new bool[n];
		
		for (int i = 0 ; i < n ; i++)
			p[i].next = NULL;
	}

	~Graph()
	{
		delete p;
		delete visit;
	}

	bool CGraph(void)
	{
		int x, y;
		GP q, g;

		cout << "Input Euleraian, End by 0 0" << endl;

		while (cin >> x >> y, x != y)
		{
			x--;
			y--;

			q = new GPH;
			q->data = x;

			g = new GPH;
			g->data = y;

			q->next = p[y].next;
			p[y].next = q;

			g->next = p[x].next;
			p[x].next = g;
		}

		return true;
	}

	bool order(int n)
	{
		for (int i = 0 ; i < len ; i++)
			visit[i] = false;
		dfs(n - 1);
		return true;
	}
};

int main(void)
{
	Graph g(5);

	g.CGraph();
	g.order(1);

	return 0;
}