- #include "main.h"
- #include <stdio.h>
- #include <stdlib.h>
- #include <queue>
- using namespace std;
- #define MAX 100
- struct Node
- {
- int weight;
- struct Node* next;
- int id;
- };
- struct ArcList
- {
- char data;
- struct Node* firstEdge;
- };
- struct Graph
- {
- int arcNum,vexNum;
- struct ArcList arcList[100];
- int visited[100];
- };
- void createGraph(struct Graph *g)
- {
- int i,j,k,m;
- struct Node *n;
- printf("input number of vexs and egdes\\n");
- scanf("%d,%d",&g->vexNum,&g->arcNum);
- getchar();
- printf("input data info\\n");
- for (i = 0; i <g->vexNum ; ++i) {
- scanf("%c",&g->arcList[i].data);
- getchar();
- g->arcList[i].firstEdge=NULL;
- }
- printf("input <v1,v2> and weight\\n");
- for (j = 0; j <g->arcNum ; ++j) {
- scanf("%d,%d",&k,&m);
- n=(struct Node*)malloc(sizeof(struct Node));
- n->id=k;
- n->next=g->arcList[m].firstEdge;
- g->arcList[m].firstEdge=n;
- n=(struct Node*)malloc(sizeof(struct Node));
- n->id=m;
- n->next=g->arcList[k].firstEdge;
- g->arcList[k].firstEdge=n;
- }
- }
- void BFSTravel(struct Graph *g)
- {
- queue<int> q;
- for(int i=0;i<g->vexNum;i++)
- {
- g->visited[i]=0;
- }
- for(int i=0;i<g->vexNum;i++)
- {
- if(!g->visited[i])
- {
- putchar(g->arcList[i].data);
- g->visited[i]=1;
- }
- q.push(i);
- while(!q.empty())
- {
- Node *node;
- int k=q.front();
- q.pop();
- node=g->arcList[k].firstEdge;
- while (node)
- {
- if(!g->visited[node->id])
- {
- putchar(g->arcList[node->id].data);
- q.push(node->id);
- g->visited[node->id]=1;
- }
- node=node->next;
- }
- }
- }
- }
- void DFS(struct Graph *g,int i)
- {
- struct Node *p;
- g->visited[i]=1;
- putchar(g->arcList[i].data);
- p=g->arcList[i].firstEdge;
- while(p)
- {
- if(!g->visited[p->id])
- {
- DFS(g,p->id);
- }
- p=p->next;
- }
- }
- //深度优先遍历
- void DFSTravl(struct Graph *g)
- {
- int i;
- for(i=0;i< g->vexNum; i++)
- g->visited[i]=0;
- for(i=0; i<g->vexNum; i++)
- {
- if(!g->visited[i])
- {
- DFS(g,i);
- }
- }
- }
- //该片段来自于http://www.codesnippet.cn/detail/1611201514001.html
来源: http://www.codesnippet.cn/detail/1611201514001.html