/*

• @Author : 菜鸟大声笑
• @Github : https://github.com/cplasf911
• @Date : 2020-12-13 17:25:21
• @LastEditors : 菜鸟大声笑
• @LastEditTime : 2020-12-13 18:05:01
• @FilePath : /CC++/C++/ds.c
• @Description :
  */
  #include <stdlib.h>
  #include <stdio.h>

#define vertexnum 9 /定义顶点数/

struct node /图顶点结构:用邻接表存储/
{
int vertex; /邻接顶点数据/
struct node* next; /下一个邻接顶点/
};

typedef struct node* graph; /定义图结构/
struct node head[vertexnum];
int visited[vertexnum]; /用于标记结点是否已访问/
int queue[101];
int in_queue[101];
int front, tail;

void dfs(int vertex)
/深度优先搜索法/
{
graph pointer;
visited[vertex] = 1;
/标记此结点已访问/ printf("[%d]==>", vertex);
pointer = head[vertex].next;
while (pointer != NULL)
{
if (visited[pointer->vertex] == 0)
dfs(pointer->vertex); /递归调用/
pointer = pointer->next; /下一个邻接点/
}
}

void bfs(void)
{
while (tail < front)
{
int vertex = queue[++tail];
visited[vertex] = 1;
printf("[%d]==>", vertex);
graph pointer = head[vertex].next;
while (pointer)
{
if (!visited[pointer->vertex] && !in_queue[pointer->vertex])
{
queue[++front] = pointer->vertex;
in_queue[pointer->vertex] = 1;
}
pointer = pointer->next;
}
}
}

void create_graph(int vertex1, int vertex2) /建立邻接顶点到邻接表内/
{
graph pointer, new1;
new1 = (graph)malloc(sizeof(struct node));
/配置内存/
if (new1 != NULL)
/成功/
{
new1->vertex = vertex2;
/邻近接点/
new1->next = NULL;
pointer = &(head[vertex1]);
/设为顶点数组之首结点/
while (pointer->next != NULL)
pointer = pointer->next;
/下一个结点/
pointer->next = new1;
/串在链尾/
}
}

void print_graph(struct node *head) /输入出邻接表数据/
{
graph pointer;
pointer = head->next;
/指针指向首结点/
while (pointer != NULL)
{
printf("[%d]", pointer->vertex);
pointer = pointer->next;
/往下结点/
}
printf("\n");
}

void main() /主程序/
{
int i;
int node[20][2] = {{1, 2}, {2, 1}, {1, 3}, {3, 1}, {2, 4}, {4, 2},
{2, 5}, {5, 2}, {3, 6}, {6, 3}, {3, 7}, {7, 3}, {4, 8}, {8, 4},
{5, 8}, {8, 5}, {6, 8}, {8, 6}, {7, 8}, {8, 7}};
/图 G3 的所有结点的邻接点的邻接表/
for (i = 0; i < vertexnum; i++)
{
head[i].vertex = i;
head[i].next = NULL;
}
for (i = 0; i < vertexnum; i++)
visited[i] = 0;
for (i = 0; i < 20; i++)
create_graph(node[i][0], node[i][1]); /建立邻接表/
printf(“graph\n”);
for (i = 1; i < vertexnum; i++)
{
printf(“vertex[%d]: “, i);
print_graph(&head[i]);
}
printf(“the depth of the graph is:\n”);
printf(” start==> “);
dfs(1); /首先从结点 1 开始/
printf(” end “);
for (i = 0; i < vertexnum; i++)
visited[i] = 0;
printf(”\nthe bfs is:\n”);
printf(" start==> “);
in_queue[1] = 1;
queue[++front] = 1;
bfs();
printf(” end ");
}