目录
//1、含邻接矩阵的图结构
//2、创建邻接矩阵
//3、打印邻接矩阵
//4、邻接表的图结构
//5、创建邻接表
//6、打印邻接表
//7、深度优先搜索
//8、广度优先搜索
//9、带主函数完整测试源码
//1、含邻接矩阵的图结构
用邻接矩阵来表示图：
//定义邻接矩阵的图结构
typedef struct graph {
elemtype data[N + 1];//存放顶点，不使用data[0]存放
int side[N + 1][N + 1];//邻接矩阵，同上
}graph;
//2、创建邻接矩阵
邻接矩阵是用来表示边的，0表示没有边，1表示有边，值为1的数组下标分别为边的起始和结尾序号：
//创建邻接矩阵
void Create1(graph* g,int sum) {
int i, j;
//初始化矩阵;
for (i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
g->side[i][j] = 0;//0表示没有边，1表示右边
}
}
//输入边的信息
printf("分别输入%d条边的始尾：n",sum);
for (int k = 1; k <= sum; k++) {
scanf("%d %d", &i, &j);
g->side[i][j] = 1;//无向图的边是双向的
g->side[j][i] = 1;
}
}
//3、打印邻接矩阵
//打印邻接矩阵
void Print1(graph g) {
for (int i = 1; i <= N; i++) {//控制行
for (int j = 1; j <= N; j++) {//控制列
printf("%d ", g.side[i][j]);
}
printf("n");//换行
}
}
//4、邻接表的图结构
//定义邻接表结构
typedef struct linkgraph {
elemtype data;//顶点值
int index;//下标值
struct linkgraph* next;//邻接点
}*linkgraph;
//5、创建邻接表
//定义邻接表结构
typedef struct linkgraph {
elemtype data;//顶点值
int index;//下标值
struct linkgraph* next;//邻接点
}*linkgraph;
//5、创建邻接表
先把每个顶点给放在一个数组里，然后把各顶点的邻接点以链表形式连在其后：
//创建邻接表
void Create2(linkgraph arr[],graph* g) {//arr是邻接表的顶点数组，g是图
//先存放每个顶点的值和序号
for (int i = 1; i <= N; i++) {
arr[i] = (linkgraph)malloc(sizeof(struct linkgraph));//不初始化就报错
arr[i]->data = g->data[i];//先存顶点
arr[i]->index = i;//给每个顶点排号
arr[i]->next = NULL;//因为还不知道该顶点的邻接点是谁所以给空
}
//然后输入边
int i, j, sum;
linkgraph new;//新的邻接表结点，用来连接邻接点
printf("输入边的条数：");
scanf("%d", &sum);
if (sum > E)
printf("输入错误！");
else {
printf("分别输入%d条边的始尾序号：n", sum);
for (int k = 1; k <= sum; k++) {
scanf("%d %d", &i, &j);//输入边，也就是两个顶点的下标值
new = (linkgraph)malloc(sizeof(struct linkgraph));
new->index = j;//先给邻接点排号
new->data=arr[j]->data;//再给新节点赋值让他去连上前一个顶点
new->next = arr[i]->next;//这里是头插法，尾插法需要头节点
arr[i]->next = new;//
//无向图，所以两遍
new = (linkgraph)malloc(sizeof(struct linkgraph));
new->index = i;
new->data = arr[i]->data;
new->next = arr[j]->next;
arr[j]->next = new;
}
}
}
//6、打印邻接表
打印出每个顶点和他的邻接点
//打印邻接表
void Print2(linkgraph arr[]) {
printf("顶点--->邻接点n");
for (int i = 1; i <= N; i++) {//控制顶点
linkgraph p = arr[i];//这里主要是方便后面的书写
printf("%c：t", p->data);
while (p->next) {//这里循环退出时就代表他没有邻接点了
p = p->next;//找到他 的邻接点
printf("%c ", p->data);
}
printf("n");
}
}
//7、深度优先搜索
深度优先就是一条路走到黑，用递归一直访问没有被访问过的顶点，直到把所有顶点都访问了：
//深度优先搜索
int visited[N + 1];//辅助数组，代表顶点的访问状态，访问过了为1，没访问为0
//先初始化这个辅助数组
void InitVisited() {
for (int i = 1; i <= N; i++) {
visited[i] = 0;
}
}
void DFS(graph* g,int i) {
printf("%c ", g->data[i]);
visited[i] = 1;//标记被访问过了
for (int j = 1; j <= N; j++) {
if (g->side[i][j] && !visited[j])//判断两顶点是否存在边并且另一顶点是否被访问过了
DFS(g, j);
}
}
//8、广度优先搜索
广度优先类似于树的层序遍历：
//广度优先搜索
void BFS(graph* g, int i) {
printf("%c ", g->data[i]);
int Queue[N + 1];//辅助队列
int front, rear;//队首队尾指针
front = rear = 0;
visited[i] = 1;//标记被访问过了
Queue[++rear] = i;//入队，把顶点的下标值入队
while (front < rear) {
i = Queue[++front];//出队，找到当前顶点的下标值
for (int j = 1; j <= N; j++) {
if (g->side[i][j] && !visited[j]) {//判断两顶点是否存在边并且另一顶点是否被访问过了
printf("%c ", g->data[j]);
visited[j] = 1;//标记被访问过了
Queue[++rear] = j;//入队，把顶点的下标值入队
}
}
}
}
