図の実現と図の深さはGraph's DFSを遍歴する

図の格納には2つの方法があります.
1、配列形式記憶の隣接行列法
2、チェーンテーブル形式で格納する隣接テーブル法.
図の遍歴方法には2つの方法があります.
1、深さ優先遍歴
2、広さ優先遍歴
一、図の記憶
配列形式で格納される隣接マトリクス法:
ここでは行列サイズの連続空間を申請し,edge[i][j]のような2次元配列を1つの配列ポインタで操作した.
int (*edge)[VERTEXNUM] = (int (*)[VERTEXNUM])malloc(sizeof(int)*VERTEXNUM*VERTEXNUM);
チェーンテーブル形式記憶の隣接表法:
1.あるノードが到達可能なノードが単一チェーンテーブル(隣接テーブルと呼ばれる)を構成し、n個のノードを有する図にn個の隣接テーブルがある.このようなA点が持つ隣接テーブルのすべてのノードは,「A点からある点まで1つの辺がある」ことを意味する.
隣接するテーブルのノードを次の構造で表します.
typedef struct edge{int vertex;//このエッジが到達するノード番号struct edge*next;//隣接する次のエッジ}st_edge;//隣接するテーブルごとにすべてのエッジの出発ノードが一致するため、この表示はそこから出発するものではありません.2.それぞれ
単一チェーンテーブルの先頭ノードアドレスが1つ存在します
連続配列でアクセスしやすい.
st_edge** edge = (st_edge**)malloc(sizeof(st_edge*)*VERTEXNUM);
ノードが持つ隣接テーブルを検索するには、edgeに基づいてポインタを後方に移動する必要があります.*(edge+i)は、図のi番点の隣接テーブルのヘッダアドレスである.
二、図の遍歴
グローバル配列を設定して、ループ状況を保存します.
int *vertexStatusArr = (int*)malloc(sizeof(int)*VERTEXNUM);
隣接行列のDFS深さ遍歴:

void dfs(int (*edge)[VERTEXNUM], int* vertexStatusArr)
{
	int i;
	printf("DFS: 
");
	for(i=0;i<VERTEXNUM;i++)
		dfscore(edge, i, vertexStatusArr);
	printf("
");
}

void dfscore(int (*edge)[VERTEXNUM], int i, int* vertexStatusArr)
{
	if(vertexStatusArr[i] == 1)
		return;
	printf("%d ", i);
	vertexStatusArr[i] = 1;

	for(int j=0;j<VERTEXNUM;j++)
		if(edge[i][j] == 1)
			dfscore(edge, j , vertexStatusArr);
}

隣接テーブルのDFS深さ遍歴:

void dfs(st_edge** edge, int* vertexStatusArr)
{
	printf("DFS: ");
	int i;
	for(i=0;i<VERTEXNUM;i++)
		dfscore(edge, i, vertexStatusArr);
	printf("
");
}

void dfscore(st_edge** edge, int i, int* vertexStatusArr)
{
	if(vertexStatusArr[i] == 1)
		return;
	printf("%d ", i);
	vertexStatusArr[i] = 1;

	st_edge* p = *(edge+i);
	while(p != NULL)
	{
		dfscore(edge, p->vertex, vertexStatusArr);
		p = p->next;
	}
}

完全なコード:

// 
#include <stdio.h>
#include <malloc.h>
#define VERTEXNUM 5

void createGragh(int (*edge)[VERTEXNUM], int start, int end);
void display(int (*edge)[VERTEXNUM]);
void dfs(int (*edge)[VERTEXNUM], int* vertexStatusArr);
void dfscore(int (*edge)[VERTEXNUM], int i, int* vertexStatusArr);

void dfs(int (*edge)[VERTEXNUM], int* vertexStatusArr)
{
	int i;
	printf("DFS: 
");
	for(i=0;i<VERTEXNUM;i++)
		dfscore(edge, i, vertexStatusArr);
	printf("
");
}

void dfscore(int (*edge)[VERTEXNUM], int i, int* vertexStatusArr)
{
	if(vertexStatusArr[i] == 1)
		return;
	printf("%d ", i);
	vertexStatusArr[i] = 1;

	for(int j=0;j<VERTEXNUM;j++)
		if(edge[i][j] == 1)
			dfscore(edge, j , vertexStatusArr);
}

void display(int (*edge)[VERTEXNUM])
{
	for(int i=0;i<VERTEXNUM;i++)
	{
		for(int j=0;j<VERTEXNUM;j++)
			printf("%d ", edge[i][j]);
		printf("
");
	}
}

void createGragh(int (*edge)[VERTEXNUM], int start, int end)
{
	edge[start][end] = 1;
}


int main()
{
	int i,j;
	int (*edge)[VERTEXNUM] = (int (*)[VERTEXNUM])malloc(sizeof(int)*VERTEXNUM*VERTEXNUM);
	for(i=0;i<VERTEXNUM;i++)
		for(j=0;j<VERTEXNUM;j++)
			edge[i][j] = 0;

	int* vertexStatusArr = (int*)malloc(sizeof(int)*VERTEXNUM);
	for(i=0;i<VERTEXNUM;i++)
		vertexStatusArr[i] = 0;

	display(edge);
	createGragh(edge, 0, 3);
	createGragh(edge, 0, 4);
	createGragh(edge, 3, 1);
	createGragh(edge, 3, 2);
	createGragh(edge, 4, 1);

	display(edge);

	dfs(edge, vertexStatusArr);
	free(edge);
	return 1;
}

// 
#include <stdio.h>
#include <malloc.h>
#define VERTEXNUM 5

typedef struct edge{
	int vertex;
	struct edge *next;
}st_edge;

void createGragh(st_edge** edge, int start, int end);
void display(st_edge** edge);
void delGragh(st_edge** edge);
void dfs(st_edge** edge, int* vertexStatusArr);
void dfscore(st_edge** edge, int i, int* vertexStatusArr);


void dfs(st_edge** edge, int* vertexStatusArr)
{
	printf("DFS: ");
	int i;
	for(i=0;i<VERTEXNUM;i++)
		dfscore(edge, i, vertexStatusArr);
	printf("
");
}

void dfscore(st_edge** edge, int i, int* vertexStatusArr)
{
	if(vertexStatusArr[i] == 1)
		return;
	printf("%d ", i);
	vertexStatusArr[i] = 1;

	st_edge* p = *(edge+i);
	while(p != NULL)
	{
		dfscore(edge, p->vertex, vertexStatusArr);
		p = p->next;
	}
}

void createGragh(st_edge** edge, int start, int end)
{
	st_edge* newedge = (st_edge*)malloc(sizeof(st_edge));
	newedge->vertex = end;
	newedge->next = NULL;

	edge = edge + start;
	while(*edge != NULL)
		edge = &((*edge)->next);
	*edge = newedge;
}

void display(st_edge** edge)
{
	int i;
	st_edge* p;
	for(i=0;i<VERTEXNUM;i++)
	{
		printf("%d: ", i);
		p = *(edge+i);
		while(p!=NULL)
		{
			printf("%d ", p->vertex);
			p = p->next;
		}
		printf("
");
	}
}

void delGragh(st_edge** edge)
{
	int i;
	st_edge* p;
	st_edge* del;
	for(i=0;i<VERTEXNUM;i++)
	{
		p = *(edge+i);
		while(p!=NULL)
		{
			del = p;
			p = p->next;
			free(del);
		}
		edge[i] = NULL;
	}
	free(edge);
}

int main()
{
	st_edge** edge = (st_edge**)malloc(sizeof(st_edge*)*VERTEXNUM);
	int i;
	for(i=0;i<VERTEXNUM;i++)
		edge[i] = NULL;
	int *vertexStatusArr = (int*)malloc(sizeof(int)*VERTEXNUM);
	for(i=0;i<VERTEXNUM;i++)
		vertexStatusArr[i] = 0;

	createGragh(edge, 0, 3);
	createGragh(edge, 0, 4);
	createGragh(edge, 3, 1);
	createGragh(edge, 3, 2);
	createGragh(edge, 4, 1);

	display(edge);
	dfs(edge, vertexStatusArr);
	edge = NULL;
	free(vertexStatusArr);
	vertexStatusArr = NULL;
	return 1;
}

次回は図のBFSとキューをまとめます.