데이터 구조 - 인접 표 에 표 시 된 그림 의 실현 DFS (재 귀 와 비 재 귀), BFS

그림 은 보통 두 가지 표현 방법 이 있다. 인접 행렬 과 인접 표 이다.
희소 한 그림 에 대해 인접 표 는 공간 을 크게 절약 할 수 있다 는 것 을 나타 낸다.
다음은 그림 의 데이터 구조의 주요 부분 이다.
struct Vertex{
   Element Type element; / 노드 이름
   Edge *next;   //포 함 된 사 이 드 로 구 성 된 싱글 체인 시트 의 헤드 포인터
};
struct Edge{
   int adj;  //노드 의 레이 블 (0 - number of nodes)
   Edge *next;
};
실제 응용 에서 노드 는 숫자 가 아 닌 이름 이 있 기 때문에 우 리 는 이름 에서 레이 블 까지 의 맵 을 제공 해 야 합 니 다.
가장 쉬 운 방법 은 Hash (산 목록) 나 이 진 트 리 같은 검색 가능 한 데이터 구 조 를 찾 는 것 입 니 다.
본 논문 의 처 리 는 비교적 간단 하 다. 노드 의 이름 은 'a' - 'z' 이기 때문에 매 핑 은 간단 한 연산 을 통 해 이 루어 질 수 있다.   node id = node name - 'a'.

// copyright @ L.J.SHOU Jan.13, 2014

#include "graph.h"
#include <ctime>
#include <iostream>
#include <stack>
#include <queue>
using namespace std;

typedef char ElementType;
typedef Vertex* Graph;

enum Color{WHITE, GRAY, BLACK};

struct Edge
{
  int vertex;
  int weight;
  Edge *next;
};

struct Vertex
{
  Color color;
  ElementType element;
  int start, finish;
  Edge *next;//head of adjacent list
};

Graph Create(Graph graph, int n)
{
  graph = new Vertex[n]; 
  for(int i=0; i<n; ++i)
  {
    graph[i].color = WHITE;
    graph[i].element = i + 'a';
	graph[i].start = 0;
	graph[i].finish = 0;
	graph[i].next = NULL;
  }
  return graph;
}

// Reset Graph
void Clear(Graph graph, int n)
{
  for(int i=0; i<n; ++i)
  {
    graph[i].color = WHITE;
	graph[i].start = 0;
	graph[i].finish = 0;
  }
}

Graph DeleteGraph(Graph graph, int n)
{
  for(int i=0; i<n; ++i)
  {
    Edge* head(graph[i].next), *next(NULL);
	while(head)
	{
	  next = head->next;
	  delete head;
	  head = next;
	}
  }
  delete [] graph;
  return NULL;
}

// return the outdegree of vertex i
int OutDegree(Graph g, int i)
{ 
  int num(0);

  Edge* link(g[i].next);
  while(link)
  {
    link = link->next;
	++ num;
  }
  return num;
}

// test whether edge(i, j) exists
bool Exist(Graph g, int i, int j)
{
  Edge *link(g[i].next); 

  while(link && link->vertex != j)
    link = link->next;

  if(link == NULL)
    return false;
  else
    return true;
}

bool InsertEdge(Graph g, int i, int j)
{
  if(Exist(g, i, j)){
    cout << "edge (" << i << "," << j << ") already existed" << endl;
    return false;
  }

  Edge *edge(NULL);
  edge = new struct Edge;
  edge->vertex = j;
  edge->next = g[i].next;
  g[i].next = edge;

  return true;
}

bool DeleteEdge(Graph g, int i, int j)
{
  if(!Exist(g, i, j)){
    cout << "edge (" << i << "," << j << ") doesn't exist" << endl;
    return false;
  }

  Edge *cur(g[i].next), *pre(cur);

  while(cur && cur->vertex != j)
  {
    pre = cur;
    cur = cur->next;
  }

  if(pre == NULL)
  { // delete head edge
    g[i].next = cur->next;
	delete cur;
  }
  else
  {
    pre->next = cur->next;
	delete cur;
  }
  return true;
}

// print adjacent list
void OutPut(Graph g, int n)
{
  Edge *edge(NULL);
  for(int i=0; i<n; ++i)
  {
	cout << g[i].element << "->";
    edge = g[i].next;
	while(edge)
	{
	  cout << g[edge->vertex].element << "->";
	  edge = edge->next;
	}
	cout << "NULL" << endl;
  }
}

void DFS(Graph graph, int n)
{
  cout << "DFS: " << endl;;
  Clear(graph, n);
  for(int i=0; i<n; ++i)
  {
    if(graph[i].color == WHITE)
	  DFSVisit(graph, i);
  }
  cout << endl;

  cout << "DFS_stack: " << endl;
  Clear(graph, n);
  for(int i=0; i<n; ++i)
  {
    if(graph[i].color == WHITE)
	  DFSVisitStack(graph, i);
  }
  cout << endl;
}

// recursive DFS
void DFSVisit(Graph graph, int i)
{
  static int time(0);
  Edge *link(graph[i].next);

  cout << graph[i].element << " ";
  graph[i].color = GRAY;
  graph[i].start = ++time;

  while(link)
  { 
    if(graph[link->vertex].color == WHITE)
	  DFSVisit(graph, link->vertex);
	link = link->next;
  }

  graph[i].finish = ++time;
  graph[i].color = BLACK;
}

// non-recursive DFS
void DFSVisitStack(Graph g, int i)
{
  static int time(0);
  struct Edge* edge;
  int vertex;
  stack<int> s;

  //visit vertex i
  cout << g[i].element << " ";
  g[i].color = GRAY;
  g[i].start = ++time;
  s.push(i);

  while(!s.empty())
  {
    vertex = s.top();
	edge = g[vertex].next;
	while(edge)
	{
	  if(g[edge->vertex].color == WHITE)
	  {
		s.push(edge->vertex);
		cout << g[edge->vertex].element << " ";
		g[edge->vertex].start = ++time;
		g[edge->vertex].color = GRAY;
		break;
	  }
	  edge = edge->next;
	}
	//vertex's neigbours have been visited
	if(edge == NULL){ 
	  s.pop();
	  g[vertex].color = BLACK;
	  g[vertex].finish = ++time;
	}
  }
}

/////////////////////////////////////////////////////////////
// search all vertices that can be rearched from Source s ///
// compute the distances from source s ///    ///////////////
/////////////////////////////////////////////////////////////
void BFS(Graph g, int n, int s)
{ 
  queue<int> q;
  Edge *edge(NULL);
  int vertex;

  //visit source vertex
  Clear(g, n);
  cout << "BFS: " << endl;;
  cout << g[s].element << " ";
  g[s].color = GRAY;
  q.push(s);

  while(!q.empty())
  { 
    //dequeue
	vertex = q.front();
	q.pop();

    //all the adjacent vertices
	edge = g[vertex].next;
    while(edge) 
    {
      if(g[edge->vertex].color == WHITE){
	     g[edge->vertex].color = GRAY;
	     cout << g[edge->vertex].element << " ";
		 //enqueue
		 q.push(edge->vertex);
	  }
      edge = edge->next;
    }
    g[vertex].color = BLACK;
  }//end of while

  cout << endl;
}


int main()
{
  Graph graph;
  int num_vertices = 8;

  graph = Create(graph, num_vertices);

  InsertEdge(graph,0,1);
  InsertEdge(graph,1,2);
  InsertEdge(graph,2,3);
  InsertEdge(graph,3,2);
  InsertEdge(graph,4,0);
  InsertEdge(graph,1,5);
  InsertEdge(graph,2,6);
  InsertEdge(graph,3,7);
  InsertEdge(graph,1,4);
  InsertEdge(graph,4,5);
  InsertEdge(graph,5,6);
  InsertEdge(graph,6,7);
  InsertEdge(graph,7,7);
  InsertEdge(graph,6,5);

  OutPut(graph, num_vertices);
  DFS(graph, num_vertices);
  BFS(graph, num_vertices, 0);

  graph = DeleteGraph(graph, num_vertices);

  return 0;
}