#include<stdio.h>
#include<stdlib.h>
//#define INFINITY -10
#define MAX_VERTEX_NUM 20
#define VType int
#define VertexType int
//此程序面向无向图
//typedef enum {DG, DN, UDG, UDN} GraphicKind
int visited[MAX_VERTEX_NUM]
typedef struct ArcCell{
VType adj//表示两点之间有无边
int *info//权值
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]
typedef struct {
VertexType vexs[MAX_VERTEX_NUM]
AdjMatrix arcs
int vexnum , arcnum
//GraphicKind kind
}MGraph
void DFS(MGraph G,int v)
int LocateVex(MGraph *G,VType v)
{
int i
for(i=1i<MAX_VERTEX_NUM+1i++)
{
if(G->vexs[i-1]==v)
return i
}
return -1
}
MGraph *CreateUDG(MGraph *G)
{
int i,j,k,v1,v2,w
printf("input vexnum:\n")
scanf("%d",&G->vexnum)
printf("input arcnum:\n")
scanf("%d",&G->arcnum)
//ptintf("input IncInfo:\n")
//scanf("%d",&G.IncInfo)//有无权值
//构造邻接矩阵：
for(i=0i<G->vexnumi++)
{
printf("input the %d th vertex:\n",i)
scanf("%d",&G->vexs[i])
printf("%d",G->vexs[i])
}
//初始化邻接矩阵
for(i=0i<G->vexnumi++)
for(j=0j<G->vexnumj++)
{
G->arcs[i][j].adj = 0
G->arcs[i][j].info = 0
}
//构造邻接矩阵
for(k=0k<G->arcnumk++)
{
printf("input the value of the first node:\n")
scanf("%d",&v1)
printf("input the value of the second node:\n")
scanf("%d",&v2)
printf("input the weight of this arc:\n")
scanf("%d",&w)//权值
i= LocateVex(G,v1)
j= LocateVex(G,v2)
//定位函数
G->arcs[i][j].adj = w
//if(incinfo) Input ( *G.arcs[i][j].info)
G->arcs[j][i] = G->arcs[i][j]
}
return G
}
void DFSTraverse(MGraph G)
{
int v
for (v=0v<G.vexnum++v)
visited[v] = 0
for (v=0v<G.vexnumv++)
if(!visited[v]) DFS(G,v)
}
void DFS(MGraph G,int v)
{
int w
int i
visited[v] = 1
printf("%d",G.vexs[v])
for(i=vi<G.vexnumi++)
if(G.arcs[v][i].adj)
{
w = i
continue
}
DFS(G,w)
}
int main(){
MGraph g
*CreateUDG(&g)
DFSTraverse(g)
}
/*深度优先*/#include<stdio.h>
#include<stdlib.h>
struct node/*图的顶点结构*/
{
int vertex
int flag
struct node *nextnode
}
typedef struct node *graph
struct node vertex_node[10]
void creat_graph(int *node,int n)
{
graph newnode,p/*定义一个新结点及指针*/
int start,end,i
for(i=0i<ni++)
{
start=node[i*2]/*边的起点*/
end=node[i*2+1]/*边的终点*/
newnode=(graph)malloc(sizeof(struct node))
newnode->vertex=end/*新结点的内容为边终点处顶点的内容*/
newnode->nextnode=NULL
p=&(vertex_node[start])/*设置指针位置*/
while(p->nextnode!=NULL)
p=p->nextnode/*寻找链尾*/
p->nextnode=newnode/*在链尾处插入新结点*/
}
}
void dfs(int k)
{
graph p
vertex_node[k].flag=1/*将标志位置1，证明该结点已访问过*/
printf("vertex[%d]",k)
p=vertex_node[k].nextnode/*指针指向下个结点*/
while(p!=NULL)
{
if(vertex_node[p->vertex].flag==0)/*判断该结点的标志位是否为0*/
dfs(p->vertex)/*继续遍历下个结点*/
p=p->nextnode/*若已遍历过p指向下一个结点*/
}
}
main()
{
graph p
int node[100],i,sn,vn
printf("please input the number of sides:\n")
scanf("%d",&sn)/*输入无向图的边数*/
printf("please input the number of vertexes\n")
scanf("%d",&vn)
printf("please input the vertexes which connected by the sides:\n")
for(i=0i<4*sni++)
scanf("%d",&node[i])/*输入每个边所连接的两个顶点，起始及结束位置不同，每边输两次*/
for(i=1i<=vni++)
{
vertex_node[i].vertex=i/*将每个顶点的信息存入数组中*/
vertex_node[i].nextnode=NULL
}
creat_graph(node,2*sn)/*调用函数创建邻接表*/
printf("the result is:\n")
for(i=1i<=vni++)/*将邻接表内容输出*/
{
printf("vertex%d:",vertex_node[i].vertex)/*输出顶点内容*/
p=vertex_node[i].nextnode
while(p!=NULL)
{
printf("->%3d",p->vertex)/*输出邻接顶点的内容*/
p=p->nextnode/*指针指向下个邻接顶点*/
}
printf("\n")
}
printf("the result of depth-first search is:\n")
dfs(1)/*调用函数进行深度优先遍历*/
printf("\n")
}
/***************************广度优先*******************************/
#include <stdio.h>
#include <stdlib.h>
struct node
{
int vertex
struct node *nextnode
}
typedef struct node *graph
struct node vertex_node[10]
#define MAXQUEUE 100
int queue[MAXQUEUE]
int front = - 1
int rear = - 1
int visited[10]
void creat_graph(int *node, int n)
{
graph newnode, p/*定义一个新结点及指针*/
int start, end, i
for (i = 0i <ni++)
{
start = node[i *2]/*边的起点*/
end = node[i *2+1]/*边的终点*/
newnode = (graph)malloc(sizeof(struct node))
newnode->vertex = end/*新结点的内容为边终点处顶点的内容*/
newnode->nextnode = NULL
p = &(vertex_node[start])/*设置指针位置*/
while (p->nextnode != NULL)
p = p->nextnode
/*寻找链尾*/
p->nextnode = newnode/*在链尾处插入新结点*/
}
}
int enqueue(int value) /*元素入队列*/
{
if (rear >= MAXQUEUE)
return - 1
rear++/*移动队尾指针*/
queue[rear] = value
}
int dequeue() /*元素出队列*/
{
if (front == rear)
return - 1
front++/*移动队头指针*/
return queue[front]
}
void bfs(int k) /*广度优先搜索*/
{
graph p
enqueue(k)/*元素入队*/
visited[k] = 1
printf("vertex[%d]", k)
while (front != rear)
/*判断是否对空*/
{
k = dequeue()/*元素出队*/
p = vertex_node[k].nextnode
while (p != NULL)
{
if (visited[p->vertex] == 0)
/*判断其是否被访问过*/
{
enqueue(p->vertex)
visited[p->vertex] = 1/*访问过的元素置1*/
printf("vertex[%d]", p->vertex)
}
p = p->nextnode/*访问下一个元素*/
}
}
}
main()
{
graph p
int node[100], i, sn, vn
printf("please input the number of sides:\n")
scanf("%d", &sn)/*输入无向图的边数*/
printf("please input the number of vertexes\n")
scanf("%d", &vn)
printf("please input the vertexes which connected by the sides:\n")
for (i = 0i <4 *sni++)
scanf("%d", &node[i])
/*输入每个边所连接的两个顶点，起始及结束位置不同，每边输两次*/
for (i = 1i <= vni++)
{
vertex_node[i].vertex = i/*将每个顶点的信息存入数组中*/
vertex_node[i].nextnode = NULL
}
creat_graph(node, 2 *sn)/*调用函数创建邻接表*/
printf("the result is:\n")
for (i = 1i <= vni++)
/*将邻接表内容输出*/
{
printf("vertex%d:", vertex_node[i].vertex)/*输出顶点内容*/
p = vertex_node[i].nextnode
while (p != NULL)
{
printf("->%3d", p->vertex)/*输出邻接顶点的内容*/
p = p->nextnode/*指针指向下个邻接顶点*/
}
printf("\n")
}
printf("the result of breadth-first search is:\n")
bfs(1)/*调用函数进行深度优先遍历*/
printf("\n")
}
邻接表表示的图：#include"stdio.h"#include"stdlib.h"#define MaxVertexNum 50 //定义最大顶点数typedef struct node{ //边表结点
int adjvex //邻接点域
struct node *next //链域
}EdgeNode
typedef struct vnode{ //顶点表结点
char vertex //顶点域
EdgeNode *firstedge //边表头指针
}VertexNode
typedef VertexNode AdjList[MaxVertexNum]//AdjList是邻接表类型
typedef struct {
AdjList adjlist //邻接表
int n,e //图中当前顶点数和边数
} ALGraph//图类型//=========建立图的邻接表=======
void CreatALGraph(ALGraph *G)
{
int i,j,k
char a
EdgeNode *s //定义边表结点
printf("Input VertexNum(n) and EdgesNum(e): ")
scanf("%d,%d",&G->n,&G->e) //读入顶点数和边数
fflush(stdin)//清空内存缓冲
printf("Input Vertex string:")
for(i=0i<G->ni++) //建立边表
{
scanf("%c",&a)
G->adjlist[i].vertex=a //读入顶点信息
G->adjlist[i].firstedge=NULL //边表置为空表
}
printf("Input edges,Creat Adjacency List\n")
for(k=0k<G->ek++) {//建立边表
scanf("%d%d",&i,&j) //读入边（Vi，Vj）的顶点对序号
s=(EdgeNode *)malloc(sizeof(EdgeNode)) //生成边表结点
s->adjvex=j //邻接点序号为j
s->next=G->adjlist[i].firstedge
G->adjlist[i].firstedge=s//将新结点*S插入顶点Vi的边表头部
s=(EdgeNode *)malloc(sizeof(EdgeNode))
s->adjvex=i //邻接点序号为i
s->next=G->adjlist[j].firstedge
G->adjlist[j].firstedge=s //将新结点*S插入顶点Vj的边表头部
}
}
//=========定义标志向量，为全局变量=======
typedef enum{FALSE,TRUE} Boolean
Boolean visited[MaxVertexNum]
//========DFS：深度优先遍历的递归算法======
void DFSM(ALGraph *G,int i)
{//以Vi为出发点对邻接链表表示的图G进行DFS搜索
EdgeNode *p
printf("%c",G->adjlist[i].vertex) //访问顶点Vi
visited[i]=TRUE //标记Vi已访问
p=G->adjlist[i].firstedge //取Vi边表的头指针
while(p) { //依次搜索Vi的邻接点Vj，这里j=p->adjvex
if(! visited[p->adjvex]) //若Vj尚未被访问
DFSM(G,p->adjvex) //则以Vj为出发点向纵深搜索
p=p->next //找Vi的下一个邻接点
}
}
void DFS(ALGraph *G)
{
int i
for(i=0i<G->ni++)
visited[i]=FALSE//标志向量初始化
for(i=0i<G->ni++)
if(!visited[i]) //Vi未访问过
DFSM(G,i) //以Vi为源点开始DFS搜索
} //==========BFS：广度优先遍历=========
void BFS(ALGraph *G,int k)
{ //以Vk为源点对用邻接链表表示的图G进行广度优先搜索
int i,f=0,r=0EdgeNode *p
int cq[MaxVertexNum]//定义FIFO队列
for(i=0i<G->ni++)
visited[i]=FALSE //标志向量初始化
for(i=0i<=G->ni++)
cq[i]=-1 //初始化标志向量
printf("%c",G->adjlist[k].vertex)//访问源点Vk
visited[k]=TRUE
cq[r]=k //Vk已访问，将其入队。注意，实际上是将其序号入队
while(cq[f]!=-1) { // 队列非空则执行
i=cq[f]f=f+1 //Vi出队
p=G->adjlist[i].firstedge//取Vi的边表头指针
while(p) {//依次搜索Vi的邻接点Vj（令p->adjvex=j）
if(!visited[p->adjvex]) { //若Vj未访问过
printf("%c",G->adjlist[p->adjvex].vertex) //访问Vj
visited[p->adjvex]=TRUE
r=r+1cq[r]=p->adjvex //访问过的Vj入队
}
p=p->next //找Vi的下一个邻接点
}
}//endwhile
}
//==========主函数===========
void main()
{
//int i
ALGraph *G
G=(ALGraph *)malloc(sizeof(ALGraph))
CreatALGraph(G)
printf("Print Graph DFS: ")
DFS(G)
printf("\n")
printf("Print Graph BFS: ")
BFS(G,3)
printf("\n")
}邻接矩阵表示的图：
#include"stdio.h"
#include"stdlib.h"
#define MaxVertexNum 100 //定义最大顶点数
typedef struct{
char vexs[MaxVertexNum] //顶点表
int edges[MaxVertexNum][MaxVertexNum] //邻接矩阵，可看作边表
int n,e //图中的顶点数n和边数e
}MGraph //用邻接矩阵表示的图的类型
//=========建立邻接矩阵=======
void CreatMGraph(MGraph *G)
{
int i,j,k
char a
printf("Input VertexNum(n) and EdgesNum(e): ")
scanf("%d,%d",&G->n,&G->e)//输入顶点数和边数
scanf("%c",&a)
printf("Input Vertex string:")
for(i=0i<G->ni++)
{
scanf("%c",&a)
G->vexs[i]=a//读入顶点信息，建立顶点表
}
for(i=0i<G->ni++)
for(j=0j<G->nj++)
G->edges[i][j]=0 //初始化邻接矩阵
printf("Input edges,Creat Adjacency Matrix\n")
for(k=0k<G->ek++) { //读入e条边，建立邻接矩阵
scanf("%d%d",&i,&j) //输入边（Vi，Vj）的顶点序号
G->edges[i][j]=1
G->edges[j][i]=1//若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句
}
}
//=========定义标志向量，为全局变量=======
typedef enum{FALSE,TRUE} Boolean
Boolean visited[MaxVertexNum]
//========DFS：深度优先遍历的递归算法======
void DFSM(MGraph *G,int i)
{ //以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0，1矩阵
int j
printf("%c",G->vexs[i])//访问顶点Vi
visited[i]=TRUE//置已访问标志
for(j=0j<G->nj++) //依次搜索Vi的邻接点
if(G->edges[i][j]==1 &&! visited[j])
DFSM(G,j) //（Vi，Vj）∈E，且Vj未访问过，故Vj为新出发点
}
void DFS(MGraph *G)
{
int i
for(i=0i<G->ni++)
visited[i]=FALSE //标志向量初始化
for(i=0i<G->ni++)
if(!visited[i]) //Vi未访问过
DFSM(G,i) //以Vi为源点开始DFS搜索
}
//===========BFS：广度优先遍历=======
void BFS(MGraph *G,int k)
{//以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索
int i,j,f=0,r=0
int cq[MaxVertexNum] //定义队列
for(i=0i<G->ni++)
visited[i]=FALSE //标志向量初始化
for(i=0i<G->ni++)
cq[i]=-1 //队列初始化
printf("%c",G->vexs[k])//访问源点Vk
visited[k]=TRUE
cq[r]=k //Vk已访问，将其入队。注意，实际上是将其序号入队
while(cq[f]!=-1) { //队非空则执行
i=cq[f]f=f+1//Vf出队
for(j=0j<G->nj++) //依次Vi的邻接点Vj
if(!visited[j] &&G->edges[i][j]==1) { //Vj未访问
printf("%c",G->vexs[j])//访问Vj
visited[j]=TRUE
r=r+1cq[r]=j //访问过Vj入队
}
}
}
//==========main=====
void main()
{
//int i
MGraph *G
G=(MGraph *)malloc(sizeof(MGraph)) //为图G申请内存空间
CreatMGraph(G) //建立邻接矩阵
printf("Print Graph DFS: ")
DFS(G) //深度优先遍历
printf("\n")
printf("Print Graph BFS: ")
BFS(G,3)//以序号为3的顶点开始广度优先遍历
printf("\n")
}
![java中String[][] 是什么东西？string[]又是什么东西？](/aiimages/java%E4%B8%ADString%5B%5D%5B%5D+%E6%98%AF%E4%BB%80%E4%B9%88%E4%B8%9C%E8%A5%BF%EF%BC%9Fstring%5B%5D%E5%8F%88%E6%98%AF%E4%BB%80%E4%B9%88%E4%B8%9C%E8%A5%BF%EF%BC%9F.png)
