|
发表于 2023-12-12 23:20:36
|
显示全部楼层
@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;
- }
复制代码 进行图的广度优先探索和深度优先探索时,这段代码有没有什么问题,该怎么改正 |
|