#include <stdio.h>
#include <stdlib.h>
#define MAX_VALUE 10
#define HAVE_PATH 1
#define NO_PATH 0
typedef struct{
char vexs[MAX_VALUE];//存储顶点元素
int arc[MAX_VALUE][MAX_VALUE];//存储图结构路径的矩阵
int vexnum ;//当前定点数
int arcnum ;//当前边数
}Graph;
//找到该元素所在的下标
int locate(Graph *graph,char ch){
int i ;
for(i = 0;i<graph->vexnum;i++){
if(graph->vexs[i]==ch)
return i;
}
return -1;
}
//构造图元素
Graph* createGraph(){
Graph *graph;
char ch;
graph = (Graph*)malloc(sizeof(Graph));
graph->arcnum = 0;
graph->vexnum = 0;
printf("输入顶点回车退出输入\n");
while((ch=getchar())!='\n'){
graph->vexs[graph->vexnum] = ch;
graph->vexnum++;
printf("输入顶点回车退出输入\n");
fflush(stdin);
}
int i ,j;
printf("当前输入的顶点数如下:\n");
for(i = 0;i<graph->vexnum;i++){
printf("%c ",graph->vexs[i]);
}
printf("输入边数\n");
scanf("%d",&graph->arcnum);
//初始化矩阵
for(i = 0;i<MAX_VALUE;i++)
for(j = 0;j<MAX_VALUE;j++)
graph->arc[i][j]=NO_PATH;
for(i = 0;i<graph->arcnum;i++){
printf("输入两个要连接的顶点的值\n");
fflush(stdin);
char valueA,valueB;
scanf("%c %c",&valueA,&valueB);
int indexA = locate(graph,valueA);
int indexB = locate(graph,valueB);
graph->arc[indexA][indexB] = HAVE_PATH;
//如果无向图 本代码默认为无向图
graph->arc[indexB][indexA] = HAVE_PATH;
}
return graph;
}
//输出矩阵
void outputGraph(Graph *graph){
int i ,j;
for(i = 0;i<MAX_VALUE;i++){
for(j = 0;j<MAX_VALUE;j++)
printf("%d ",graph->arc[i][j]);
printf("\n");
}
}
//图元素操作函数
void work(char ch){
printf("%c ",ch);
}
//深度优先遍历 其思想是 抓住一个点 从顶层遍历到最底层(之前已经遍历过的点就不再遍历)
void DFSGraph(Graph *graph){
int i = 0;
int visited[graph->vexnum];
for(;i<graph->vexnum;i++)
visited[i] = 0;//初始化标志数组
for(i = 0;i<graph->vexnum;i++){
if(visited[i]==0){//如果之前未访问过
work(graph->vexs[i]);
DFS(graph,i,visited);
}
}
}
void DFS(Graph *graph,int index,int *visited){
visited[index] =1;//设立已访问标志
int i = 0;
for(;i<graph->vexnum;i++){
if(graph->arc[index][i]==HAVE_PATH&&visited[i]==0){//如果下标为index的节点和下标为i的节点之间有通路并且这个下标i的节点之前未访问到 则进入下一层搜索
work(graph->vexs[i]);//访问该顶点
DFS(graph,i,visited);
}
}
}
//广度优先遍历 思想是 一层一层遍历 即抓住一个顶点 访问其所有和这个顶点相连的顶点 以此循环
void BFSGraph(Graph *graph){
int i = 0;
int j = 0;
int visited[graph->vexnum];
for(;i<graph->vexnum;i++)
visited[i] = 0;//初始化标志数组
for(i = 0;i<graph->vexnum;i++){
if(visited[i]==0){//如果之前未访问过
work(graph->vexs[i]);
}
for(j = 0;j<graph->vexnum&&i<j;j++){//此for循环要以i<j为条件 因为无向图的原因 以对角线对称 只需访问半边矩阵即可
if(graph->arc[i][j]==HAVE_PATH){
//下标为i和j的之间有通路
work(graph->vexs[j]);//因为i是肯定访问过的 所以此次只需要访问下标为j的顶点
}
}
}
}
int main()
{
Graph * p = createGraph();
outputGraph(p);
// DFSGraph(p);
BFSGraph(p);
return 0;
}
