邻接表的实现

邻接表：(链式+顺序)
边：
顶点下标
指向下一条边的地址
顶点：
顶点数据
指向第一条边的指针
图：
由顶点组成的数组
顶点数量
优点：节约存储空间，计算出度方便
缺点：计算入度麻烦

#include <stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<string.h>
#include"link_array_queue.h"//引用的之前写的链队列
typedef struct SIDE
{int index;//顶点下标struct SIDE *next;//下一条边地址
}SIDE;SIDE *create_edge(int index)//创建边
{SIDE *edge=malloc(sizeof(SIDE));edge->index=index;edge->next=NULL;return edge;
}typedef struct Vertex//定义顶点数据项
{char vertex;//顶点数据SIDE *first;//和顶点相关的第一条边地址
}Vertex;typedef struct Graph//定义图数据项
{int cnt;Vertex *v;
}Graph;//创建邻接表
Graph *create_graph(const char *str)
{Graph *graph=malloc(sizeof(Graph));//申请一片空间存储邻接表graph->cnt=strlen(str);graph->v=malloc(sizeof(Vertex)*graph->cnt);//申请空间存放顶点//初始化顶点for(int i=0;i<graph->cnt;i++){graph->v[i].vertex=str[i];graph->v[i].first=NULL;}return graph;
}
//添加边
bool add_graph(Graph *graph,char v,char v1)//v为顶点，v1为终点
{for(int i=0;i<graph->cnt;i++)//循环到每一个顶点{if(v==graph->v[i].vertex)//找到顶点下标{int j=0;for(j;j<graph->cnt;j++)//循环找到终点下标{if(v1==graph->v[j].vertex)break;}SIDE *newdege=create_edge(j);//创建新结点newdege->next=graph->v[i].first;//头插法插入graph->v[i].first=newdege;return true;}}return false;//没找到顶点下标
}void show_graph(Graph *graph)
{for(int i=0;i<graph->cnt;i++){printf("%c :",graph->v[i].vertex);	SIDE *edge=graph->v[i].first;while(edge){printf("%c ",graph->v[edge->index].vertex);edge=edge->next;}printf("\n");}
}//入度
int id_graph(Graph *graph,char v)
{int num=0;int index=0;for(int i=0;i<graph->cnt;i++){if(v==graph->v[i].vertex)index=i;}for(int i=0;i<graph->cnt;i++){for(SIDE *edge=graph->v[i].first;edge;edge=edge->next){if(index==edge->index)num++;}}return num;
}//出度
int od_graph(Graph *graph,char v)
{int num=0;for(int i=0;i<graph->cnt;i++){if(v==graph->v[i].vertex){for(SIDE *edge=graph->v[i].first;edge;edge=edge->next){num++;	}return num;}}return -1;
}
//深度优先
void dfs(Graph *graph,int index,char* visited)//依赖，index下标，visited标记是否遍历过
{if(0!=visited[index])return;//如果遍历过，结束printf("%c ",graph->v[index].vertex);visited[index]=1;//遍历过后标记为1for(SIDE *e=graph->v[index].first;e;e=e->next)//从前往后利用递归遍历{if(0==visited[e->index])dfs(graph,e->index,visited);//递归}
}
void dfs_graph(Graph *graph)
{char visited[graph->cnt];//创建标记 ，数组中元素要为常量，LINUX中可以编译memset(visited,0,strlen(visited));//初始化标记for(int i=0;i<graph->cnt;i++){dfs(graph,0,visited);//调用依赖}printf("\n");return;
}//广度优先
void bfs_graph(Graph *graph)
{char visited[graph->cnt];//创建标记memset(visited,0,strlen(visited));//初始化标记ListQueue *queue=create_list_queue();//创建队列for(int i=0;i<graph->cnt;i++){if(!visited[i]){visited[i]=1;//入队标记为1push_list_queue(queue,i);//入队while(!empty_list_queue(queue))//当队列中不为空{int current=head_list_queue(queue);//记录即将出队下标printf("%c ",graph->v[current].vertex);pop_list_queue(queue);//出队for(SIDE *e=graph->v[current].first;e;e=e->next)//从前往后将没入队的入队{if(0==visited[e->index]){visited[e->index]=1;push_list_queue(queue,e->index);	//入队并标记}}}}}destroy_list_queue(queue);//销毁队列printf("\n");
}int main(int argc,const char* argv[])
{char *str="ABCDEFG";Graph *graph=create_graph(str);add_graph(graph,'A','B');add_graph(graph,'A','D');add_graph(graph,'B','D');add_graph(graph,'B','E');add_graph(graph,'C','D');add_graph(graph,'C','F');add_graph(graph,'D','C');add_graph(graph,'D','G');add_graph(graph,'E','G');add_graph(graph,'F','G');add_graph(graph,'G','F');show_graph(graph);printf("D的入度：%d\n",id_graph(graph,'D'));printf("D的出度：%d\n",od_graph(graph,'D'));dfs_graph(graph);bfs_graph(graph);return 0;
}