[数据结构与算法]【数据结构与算法】用图的邻接表来遍历

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

typedef struct Edge
{
	int index;
	struct Edge* next;
}Edge;

Edge* create_edge(int index)
{
	Edge* edge = malloc(sizeof(Edge));
	edge->index = index;
	edge->next = NULL;
	return edge;
}

typedef struct Vertex
{
	char vex;
	Edge* head;
}Vertex;

typedef struct Graph
{
	Vertex* vertex;
	size_t vexnum;
}Graph;

Graph* create_graph(const char* str)
{
	Graph* graph = malloc(sizeof(Graph));
	graph->vexnum = strlen(str);
	graph->vertex = malloc(sizeof(Vertex)*graph->vexnum);
	for(int i=0; i<graph->vexnum; i++)
	{
		graph->vertex[i].vex = str[i];
		graph->vertex[i].head = NULL;
	}
	return graph;
}

int _index_vertex(Graph* graph,char v)
{
	for(int i=0; i<graph->vexnum; i++)
	{
		if(v == graph->vertex[i].vex)
			return i;
	}
	return -1;
}

bool add_edge(Graph* graph,char v1,char v2)
{
	int index1 = _index_vertex(graph,v1);
	int index2 = _index_vertex(graph,v2);
	if(index1 < 0 || index2 < 0 || index1 == index2)
		return false;
	
	Edge* edge = create_edge(index2);
	edge->next = graph->vertex[index1].head;
	graph->vertex[index1].head = edge;
	return true;
}

void show_graph(Graph* graph)
{
	for(int i=0; i<graph->vexnum; i++)
	{
		printf("%d %c:",i,graph->vertex[i].vex);
		for(Edge* e=graph->vertex[i].head; NULL!=e; e=e->next)
		{
			printf("%d ",e->index);
		}
		printf("\n");
	}
}

size_t vertex_in(Graph* graph,char v)
{
	int index = _index_vertex(graph,v);
	if(0 > index)
		return -1;

	size_t degree = 0;
	for(int i=0; i<graph->vexnum; i++)
	{
		if(i == index)
			continue;

		Edge* e=graph->vertex[i].head; 
		while(NULL!=e)
		{
			if(e->index == index)
			{
				degree++;
				break;
			}
			e=e->next;
		}
	}
	return degree;
}

size_t vertex_out(Graph* graph,char v)
{
	int index = _index_vertex(graph,v);
	if(0 > index)
		return -1;

	size_t degree = 0;
	Edge* e=graph->vertex[index].head; 
	while(NULL!=e)
	{
		degree++;
		e=e->next;
	}

	return degree;
}

int main(int argc,const char* argv[])
{
	char* str = "ABCDEFG";
	Graph* graph = create_graph(str);
	add_edge(graph,'A','C');
	add_edge(graph,'A','G');
	add_edge(graph,'C','D');
	add_edge(graph,'G','F');
	add_edge(graph,'G','E');
	add_edge(graph,'G','C');
	show_graph(graph);
	printf("%d\n",vertex_out(graph,'G'));
}