@FishC#include<stdio.h>
#include<stdlib.h>
#define Maxvertexnum 100
#define Maxsize 100
#define VertexType int
typedef int DataType;
typedef int Infotype;
typedef struct ArcNode/*表结点*/
{
int adjvex;//邻接点域 一般存放顶点对应的序号或在表头向量的下标
Infotype info;//边的权或信息
struct ArcNode* next;//指向下一个邻接点的指针域
}Edgenode;
typedef struct vnode/*顶点结点*/
{
VertexType vertex;//顶点域
int degree, indegree;/*顶点的度和入度*/
Edgenode* firstarc;/*边表头指针*/
}VertexNode;
typedef struct AlGraph {
VertexNode adjlist[Maxvertexnum];/*邻接表*/
int vertexNum, edgeNum;/*顶点数和边数*/
}ALGraph;//ALGraph是以邻接表方式存储的图类型
ALGraph* CreateALGraph() {
int i, j, k;
Edgenode* p;
printf("请输入顶点数和边数");
ALGraph* G;
G = (ALGraph*)malloc(sizeof(ALGraph));
scanf_s(" %d", &(G->vertexNum));
scanf_s(" %d", &(G->edgeNum));
printf("请输入顶点值");
for (i = 0; i < G->vertexNum; i++) {/*建立有n个顶点的顶点表*/
scanf_s(" %d", &(G->adjlist[i].vertex));
G->adjlist[i].firstarc = NULL;
}
printf("读入边<i,j>的顶点对应序号");
for (k = 0; k < G->edgeNum; k++) {/*建立边表*/
scanf_s("%d", &i);
scanf_s("%d", &j);/*读入边<i,j>的顶点对应序号*/
p = (Edgenode*)malloc(sizeof(Edgenode));
p->adjvex = j;
p->next = G->adjlist[i].firstarc;
G->adjlist[i].firstarc = p;
}
return G;
}
int visited[Maxvertexnum];
void DFS(ALGraph* G, int v) {
visited[v] = 1;
printf(" %d", G->adjlist[v].vertex);
Edgenode* p = G->adjlist[v].firstarc;
while (p) {
if (!visited[p->adjvex]) {
DFS(G, p->adjvex);
}
p = p->next;
}
}
void DFStraverse(ALGraph* G) {/*深度优先遍历*/
int v;
for (v = 0; v < G->vertexNum; v++) {
visited[v] = 0;/*标志向量初始化*/
}
for (v = 0; v < G->vertexNum; v++) {
if (!visited[v]) {
DFS(G, v);
}
}
}
typedef struct SeqQueue {
DataType data[Maxsize];
int front, rear;
}SeqQueue,*PSeqqueue;
PSeqqueue Init_SeqQueue() {
PSeqqueue Q;
Q = (PSeqqueue)malloc(sizeof(SeqQueue));
if (Q) {
Q->front = 0;
Q->rear = 0;
}
return Q;
}
PSeqqueue In_SeqQueue(PSeqqueue Q,DataType e) {
if ((Q->rear + 1) % Maxsize == Q->front) {
printf("队满无法入队");
exit(1);
}
else {
Q->data[Q->rear] = e;
Q->rear = (Q->rear + 1) % Maxsize;
}
return Q;
}
PSeqqueue Out_SeqQueue(PSeqqueue Q, DataType* e) {
if (Q->front == Q->rear) {
printf("队空无法出队");
exit(1);
}
else {
*e = Q->data[Q->front];
Q->front = (Q->front + 1) % Maxsize;
}
return Q;
}
void BFS(ALGraph* G, int v) {
// 广度优先遍历的操作
Edgenode* p=NULL;
PSeqqueue Q = Init_SeqQueue();
printf("\n%d", G->adjlist[v].vertex);
visited[v] = 1;
In_SeqQueue(Q, v);
while (Q->front != Q->rear) {
Q=Out_SeqQueue(Q, &v);
for (p = G->adjlist[v].firstarc; p; p = p->next) {
if (!visited[p->adjvex]) {
printf(" %d", G->adjlist[p->adjvex].vertex);
visited[p->adjvex] = 1;
In_SeqQueue(Q, p->adjvex);
}
}
}
}
void BFStraverse(AlGraph* G) {
for (int v = 0; v < G->vertexNum; v++) {
visited[v] = 0;
}
for (int v = 0; v < G->vertexNum; v++) {
if (!visited[v]) {
BFS(G, v);
}
}
}
int main() {
ALGraph* G = CreateALGraph();
DFStraverse(G);
BFStraverse(G);
return 0;
}
| 
[复制链接]
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2022-11-2 19:20:35
显身卡
发表于 2023-12-12 22:56:19