鄰接表c語言

Ⅰ c語言關於圖的鄰接表建立

#include "iostream.h"

const int Max_vertex=5;
const int Max_Edge=8;
int visited[Max_vertex+1]; //訪問標志數組

struct ArcNode
{
int adjvex;
ArcNode *nextarc; //指向下一條弧
};

struct Vnode
{
int v; //頂點信息
ArcNode *next;
}a[Max_vertex+1];

/* 無向圖的建立 */
void creategraph()
{
int i,j,k;
ArcNode *s;
//初始化
for(i=1;i<=Max_vertex;i++)
{
a[i].v=i;
a[i].next=NULL;
}

/*以頭插法建立 */

for(k=1;k<=Max_Edge;k++)
{
cout<<"請輸入第"<<k<<"條邊:";
cin>>i>>j;
if(i>9||i<0||j<0||j>9)
{
cout<<"輸入錯誤!!\n"<<endl;
break;
}
else{
cout<<endl;
s=new ArcNode;
s->adjvex=j;
s->nextarc=a[i].next;
a[i].next=s;
s=new ArcNode;
s->adjvex=i;
s->nextarc=a[j].next;
a[j].next=s;
}
}
}

void display()
{
ArcNode *p;
cout<<"你建立的圖為:"<<endl;
for(int i=1;i<=Max_vertex;i++)
{
p=a[i].next;
cout<<a[i].v<<"->";
while(p->nextarc!=NULL)
{
cout<<p->adjvex<<"->";
p=p->nextarc;
}
cout<<p->adjvex<<endl;
}
}

void main()
{
cout<<"/******\t本演算法以關插法建立無向圖的鄰接表為例!\t******/"<<endl;
char yn='y';int k;
creategraph();
display();

}

Ⅱ 數據結構-圖的鄰接表表示（C語言）

//grap_theory.cpp:定義控制台應用程序的入口點。

//

//#include"stdafx.h"//VS2010頭文件

#include<stdio.h>

#defineNTOTAL(26*4)//最大路徑數目

#defineMAX_DISTANCE10000.0

structpiont{

intline_adjacency_list;

intnum_piont;

inttest_num[2];

charfrom[NTOTAL];

charto[NTOTAL];

charall_piont[NTOTAL];

intall_piont_num[NTOTAL];

floatdistance[NTOTAL];

floatdistance_all[NTOTAL][NTOTAL];

};//結構體定義

voidread(piont*test){

inti;

chartemp[100];

scanf("%d",&test->line_adjacency_list);//讀取行數

gets(temp);//讀取回車字元

for(i=0;i<test->line_adjacency_list;i++){//讀取列表

scanf("%c%c%f",&test->from[i],&test->to[i],&test->distance[i]);

gets(temp);//讀取回車字元

}

scanf("%c%c",&test->from[i],&test->to[i]);//讀取短短路徑名稱

}

voidcal_num_piont(piont*test){

inti,j;

intfrom_num,to_num;

test->num_piont=0;

for(i=0;i<NTOTAL;i++){

test->all_piont_num[i]=0;//點的度數清零

test->distance_all[i][i]=0.0;

for(j=i+1;j<NTOTAL;j++){

test->distance_all[i][j]=MAX_DISTANCE;

test->distance_all[j][i]=MAX_DISTANCE;

}

}

for(i=0;i<test->line_adjacency_list;i++){

//判斷from

for(j=0;j<test->num_piont;j++){

if(test->from[i]==test->all_piont[j]){

from_num=j;

test->all_piont_num[j]++;

break;

}

}

if(j==test->num_piont){

test->all_piont[j]=test->from[i];

from_num=j;

test->all_piont_num[j]++;

test->num_piont++;

}

//判斷end

for(j=0;j<test->num_piont;j++){

if(test->to[i]==test->all_piont[j]){

to_num=j;

test->all_piont_num[j]++;

break;

}

}

if(j==test->num_piont){

test->all_piont[j]=test->to[i];

to_num=j;

test->all_piont_num[j]++;

test->num_piont++;

}

test->distance_all[from_num][to_num]=test->distance[i];

test->distance_all[to_num][from_num]=test->distance[i];

}

//判斷所求點的位置

for(i=0;i<test->num_piont;i++){

if(test->from[test->line_adjacency_list]==test->all_piont[i])

test->test_num[0]=i;

if(test->to[test->line_adjacency_list]==test->all_piont[i])

test->test_num[1]=i;

}

}

floatmin_distance(piont*test){

inti,j,k,n;

floatmin_dis;

floatdis_i_k_add_k_j;

n=test->num_piont;

//Floyd-Warshall演算法

for(k=0;k<n;k++){

for(i=0;i<n;i++){

for(j=0;j<n;j++){

dis_i_k_add_k_j=(test->distance_all[i][k]+test->distance_all[k][j]);

if(test->distance_all[i][j]>dis_i_k_add_k_j)

test->distance_all[i][j]=dis_i_k_add_k_j;

}

}

}

min_dis=test->distance_all[test->test_num[0]][test->test_num[1]];

returnmin_dis;

}

voidtest_printf(piont*test,floatmin_dis){

inti;

printf("%d ",test->num_piont);

for(i=0;i<test->num_piont;i++){

printf("%d ",test->all_piont_num[i]);

}

printf("%-8.0f ",min_dis);

}

voidmain()

{

floatmin_dis;

pionttest1;//結構體聲明

read(&test1);

cal_num_piont(&test1);

min_dis=min_distance(&test1);

test_printf(&test1,min_dis);

}

Ⅲ c語言，圖的鄰接表創建問題。 關於scanf的，不明白是怎麼回事

你在輸入的時候是用回車結束的吧？
scanf()函數從輸入流緩沖區中讀取值的，而讀取時遇到回車(\n)而結束的。帶空格的scanf(" %c")表示要從輸入流緩沖區讀兩個字元，一個給空格，一個給%c。為什麼加空格呢，是因為回車符(\n)也在輸入流緩沖區中，所以將\n賦值給空格，以讓%c被正確賦值。否則，不加空格，回車符\n會被賦值給%c。

Ⅳ C語言 鄰接矩陣和鄰接表

/**********************鄰接矩陣*****************/

#include<bits/stdc++.h>//鄰接矩陣

using namespace std;

const int N=300;

int Map[N][N]={0};//鄰接矩陣

int book[N]={0};//結點標記數組(1表示該點訪問過了;0未訪問過)

int n,m;

void dfs(int x)//深度遍歷

{

for(int i=1;i<=n;i++)

{//book[i]==0:i未被訪問過

// Map[x][i]==1：x到i有邊連接

if(book[i]==0&&Map[x][i]==1)

{

book[i]=1;//訪問標記

printf("->[%d]",i);

dfs(i);//前往下一個結點i

}

}

}

void bfs(int x)

{

int q[N]={0};

int fornt=0;

int rear=0;

q[rear++]=x;//源點入隊

while(fornt<rear)

{

int k=q[fornt++];//出隊

for(int i=1;i<=n;i++)

{//擴展一個點周圍可以訪問的點

if(book[i]==0&&Map[k][i]==1)

{

printf("->[%d]",i);

book[i]=1;//訪問標記

q[rear++]=i;//入隊

}

}

}

}

int main()

{

scanf("%d%d",&n,&m);//n個結點，m條邊

for(int i=0;i<m;i++)

{//構造無向圖

int x,y;//輸入2個結點;x->y;y->x;

scanf("%d%d",&x,&y);

Map[x][y]=1;//1代表x，y鄰接

Map[y][x]=1;

}

book[1]=1;//標記結點1

printf("深度遍歷路徑 [%d]",1);

dfs(1);//從結點1深度遍歷 (起始點可以隨便選,1~n)

printf(" ");

memset(book,0,sizeof(book));//標記數組置0，用於廣度遍歷標記

printf("廣度遍歷路徑 [%d]",1);

book[1]=1;//標記結點1

bfs(1);//從結點1廣度遍歷 (起始點可以隨便選,1~n)

return 0;

}

/*5個結點,7條邊

5 7

1 3

1 2

1 4

2 4

2 5

3 5

4 5

*/

/*************************鄰接表*************************************/

#include<bits/stdc++.h>//萬能頭文件，C/C++都能用,包含了所有的頭文件

using namespace std;//鄰接表

const int N=300;

typedef struct st{

int v;//表頭能到達的結點

struct st *next;//指向下一個結點的指針域

}*link,AK;//定義結點類型

struct sx{

AK *next;//表頭指針域

}s[N];//n個結點,n個表頭

int book[N]={0};//結點標記數組(1表示該點訪問過了;0未訪問過)

int n,m;

void create(int x,int y)

{//前插法構建鄰接表

link p;

p=new AK;//開辟新結點

p->v=y;

p->next=s[x].next;

s[x].next=p;

}

void fun()

{//表頭指針賦空(這一步至關重要,沒有這一步無法建表)

for(int i=1;i<=n;i++)

s[i].next=NULL;

}

void dfs(int x)//深度遍歷鄰接表

{

link p=s[x].next;

while(p)

{

if(book[p->v]==0)

{

printf("->[%d]",p->v);

book[p->v]=1;

dfs(p->v);

}

p=p->next;

}

}

void bfs(int x)//廣度遍歷鄰接表

{

int q[N]={0};//隊列

int fornt=0;

int rear=0;

q[rear++]=x;

while(fornt<rear)

{

int k=q[fornt++];

link p=s[k].next;

while(p)

{

if(book[p->v]==0)

{

printf("->[%d]",p->v);

book[p->v]=1;

q[rear++]=p->v;

}

p=p->next;

}

}

}

void input()//列印鄰接表

{//首列是表頭(其後尾隨的是與其鄰接的結點)

//n個表頭

link p;

for(int i=1;i<=n;i++)

{

p=s[i].next;

printf("[%d]",i);

while(p)

{

printf("->[%d]",p->v);

p=p->next;

}

cout<<endl;

}

}

int main()

{

fun();//調用表頭置空

scanf("%d%d",&n,&m);//n個結點，m條邊

for(int i=0;i<m;i++)

{//構造無向鄰接表

int x,y;//輸入2個結點;x->y;y->x;

scanf("%d%d",&x,&y);

create(x,y);//構建有向鄰接表，只調用一個;

create(y,x);//構建無向鄰接表，只調用兩個;

}

book[1]=1;//標記結點1

printf("深度遍歷路徑 [%d]",1);

dfs(1);//從結點1深度遍歷 (起始點可以隨便選,1~n)

printf(" ");

memset(book,0,sizeof(book));//標記數組置0，用於廣度遍歷標記

printf("廣度遍歷路徑 [%d]",1);

book[1]=1;//標記結點1

bfs(1);//從結點1廣度遍歷 (起始點可以隨便選,1~n)

printf(" ");

printf("列印鄰接表結構 ");

input();//列印鄰接表

return 0;

}

/*5個結點,7條邊

5 7

1 3

1 2

1 4

2 4

2 5

3 5

4 5

*/

Ⅳ c語言，關於鄰接表的建立

AdjList 是自定義類型，是char類型，
第二行 typedef將char類型自定義為 VertexType，即VertexType代表了char型，
VertexType a 就相當於 char a；

同理

倒數第五行 typedef將VertexNode自定義為 AdjList[MaxVertexNum]類型，也就是說現在AdjList就代表了一個 「結構體數組」 類型
AdjList adjlist 相當於 VertexNode adjlist[MaxVertexNum]

這里主要是typedef關鍵字的使用 希望能幫到你

Ⅵ c語言圖的遍歷，鄰接表存儲，深度，廣度優先遍歷

（1） 圖的建立，按採用鄰接表作為存儲結構。
（2） 從指定頂點出發進行深度優先搜索遍歷。
（3） 從指定頂點出發進行廣度優先搜索遍歷。

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#include"math.h"

#define MAX_INT 1000
#define MAX_VERTEX_NUM 20
#define MAX_QUEUE_NUMBER 20

typedef struct ArcNode
{
int adjvex;
double adj;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VexNode
{
char szName[40];
ArcNode *firstarc;
}VexNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vexs;
int vexnum,arcnum;
}Net;
//定義隊列
typedef struct{
int *elem;
int front, rear;
}Queue;
void InitQueue(Queue &Q)
{
Q.elem = new int[MAX_QUEUE_NUMBER];
Q.front = Q.rear = 0;
}
int EmptyQueue(Queue Q)
{
if(Q.front==Q.rear)
return 0;
else
return 1;
}
void DestroyQueue(Queue &Q){
delete []Q.elem;
Q.front = Q.rear = 0;
}

void EnterQueue(Queue &Q, int e)
{
if((Q.rear + 1)%MAX_QUEUE_NUMBER != Q.front)
Q.elem[Q.rear ] = e;
else
printf("隊列滿!\n");
Q.rear = (Q.rear + 1)%MAX_QUEUE_NUMBER;
}
void LeaveQueue(Queue &Q, int &e)
{
if(Q.rear != Q.front)
e = Q.elem[Q.front];
else
printf("隊列空!\n");
Q.front = (Q.front+1)%MAX_QUEUE_NUMBER;
}
int LocateVex(Net ga,char *name)
{
int i;
for(i=0;i<ga.vexnum;i++)
if(strcmp(name,ga.vexs[i].szName)==0)
return i;
return -1;

}
void crt_net(Net &ga)
{
ArcNode *p;
char name1[40],name2[40];
int i,j,k;
double w;
printf("請輸入頂點數和弧數：");
scanf("%d%d",&ga.vexnum,&ga.arcnum);
printf("請依次輸入頂點名：\n");
for(i=0;i<ga.vexnum;i++)
{
scanf("%s",ga.vexs[i].szName);
ga.vexs[i].firstarc=NULL;
}
for(k=0;k<ga.arcnum;k++)
{
printf("請輸入相鄰的兩個定點和權值：");
scanf("%s%s%lf",name1,name2,&w);
i=LocateVex(ga,name1);
j=LocateVex(ga,name2);
p=new ArcNode;
p->adjvex=j;
p->adj=w;
p->nextarc=ga.vexs[i].firstarc;
ga.vexs[i].firstarc=p;
}
}

void DFS(Net ga,char *name,int *visited)
{
int v,w;
ArcNode *p;
v=LocateVex(ga,name);
visited[v]=1;
printf("%s ",ga.vexs[v].szName);
p=ga.vexs[v].firstarc;
while(p!=NULL)
{
w=p->adjvex;
if(visited[w]==0)
DFS(ga,ga.vexs[w].szName,visited);
p=p->nextarc;
}

}
void DFSTravel(Net ga,char *name)
{
int v,k=0;
int visited[20];
for(v=0;v<ga.vexnum;v++)
visited[v]=0;
for(v=LocateVex(ga,name);k!=2;v=(v+1)%(ga.vexnum-1))
{
if(v+1==LocateVex(ga,name))
k++;
if(visited[v]==0)
DFS(ga,ga.vexs[v].szName,visited);

}
}

void BFSTravel(Net ga,char *name)
{
ArcNode *p;
int v,w,u,k=0;
Queue Q;
int visited[20];
for(v=0;v<ga.vexnum;v++)
visited[v]=0;
InitQueue(Q);
for(v=LocateVex(ga,name);k!=2;v=(v+1)%(ga.vexnum-1))
{
if(v+1==LocateVex(ga,name))
k++;
if(visited[v]==0)
{
visited[v]=1;
printf("%s ",ga.vexs[v].szName);
EnterQueue(Q,v);
while(EmptyQueue(Q)!=0)
{
LeaveQueue(Q,u);
p=ga.vexs[u].firstarc;
while(p!=NULL)
{
w=p->adjvex;
if(visited[w]==0)
{
printf("%s ",ga.vexs[w].szName);
visited[w]=1;
EnterQueue(Q,w);
}
p=p->nextarc;
}
}
}

}
}

void main()
{
char name[40];
Net ga;
crt_net(ga);
printf("請輸入深度優先遍歷開始點的名：");
scanf("%s",name);
printf("深度優先遍歷：");
DFSTravel(ga,name);
printf("\n");
printf("請輸入廣度優先遍歷開始點的名：");
scanf("%s",name);
printf("廣度優先遍歷：");
BFSTravel(ga,name);
printf("\n");

}

Ⅶ 在C語言中編程實現建立無向圖的鄰接表,輸出某個點的鄰接點~!

用矩陣表示無向圖的，設有M個節點，則建立一個MXM矩陣，對每個頂點添加它的鄰接點，即每行中對於有標記的列為該行頂點的鄰接點。

Ⅷ 用c語言編程 1創建圖的鄰接矩陣和鄰接表 2驗證圖的深度優先、廣度優先遍歷演算法 3驗證最短路徑

這些是c++的代碼不知是否滿足你的要求。
1、鄰接表表示的圖中分別用DFS和BFS遍歷
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 圖的鄰接表的結點
struct Edge
{
int dest; // 目標結點下標
// int value; // 路徑長度
Edge *link; // 下一個結點
};
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 為圖添加一條邊
// Input: edge - 欲加邊的結點; dest - 目的結點
// Output: edge - 加邊後的結點
// Tags:
void AddEdge(Edge *&edge, int dest)
{
// 簡單的鏈表操作
if (!edge)
{
edge = new Edge;
edge->dest = dest;
edge->link = 0;
}
else
{
Edge *tail = edge;
while (tail->link) tail = tail->link;
tail->link = new Edge;
tail = tail->link;
tail->dest = dest;
tail->link = 0;
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: Console下輸入圖的邊
// Input: Graph - 圖; n - 圖的結點的個數; EdgeNumber - 添加邊的個數;
// Output: Graph - 添加邊後的圖
// Tags: 用戶輸入點對(a, b), 表示添加a->b的路徑
void Input(Edge **&graph, int n, int EdgeNumber)
{
int i = 0, a, b;
for (i = 0; i < EdgeNumber; i++)
{
scanf("%d %d", &a, &b); // 用戶輸入起點終點
AddEdge(graph[a], b); // 添加a->b的邊
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 深度優先搜索並輸出
// Input: Graph - 圖; n - 圖的結點的個數; StartEdge — 開始的結點;
// Output: Console下輸出遍歷的順序
// Tags: 遞歸調用 _dfs過程、回溯演算法
void _dfs(Edge **&graph, bool *visited, int n, int index);
void DFS(Edge **&graph, int n, int StartEdge)
{
bool *visited = new bool[n]; // 標記每個結點是否已訪問
memset(visited, (int)false, sizeof(bool) * n);
visited[StartEdge] = true;
printf("start edge: %d\n", StartEdge);
_dfs(graph, visited, n, StartEdge);
visited[StartEdge] = false;
}
// _dfs過程：
// Input: Graph - 圖; n - 圖的結點的個數; index - 當前的下標, visited - 記錄結點是否已訪問
// Output: Console下輸出遍歷的順序
void _dfs(Edge **&graph, bool *visited, int n, int index)
{
int nIndex; // 下一個結點下標
Edge *edge = graph[index]; // 遍歷用結點
while (edge) // 遍歷所有的鄰接結點
{
nIndex = edge->dest;
if (!visited[nIndex])
{
visited[nIndex] = true;
printf("%d\t", nIndex);
_dfs(graph, visited, n, nIndex);
}
edge = edge->link;
}
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 廣度優先搜索並輸出
// Input: Graph - 圖; n - 圖的結點的個數; StartEdge - 開始的結點
// Output: Console下輸出遍歷的順序
// Tags: 需要一個隊列記錄所有的灰色結點
void BFS(Edge **&graph, int n, int StartEdge)
{
bool *visited = new bool[n]; // 記錄結點是否已訪問
memset(visited, (int)false, sizeof(bool) * n);
queue<int> Q; // 記錄准備訪問的結點
Edge *edge; // 記錄當前遍歷的結點
int nIndex; // 記錄下標

visited[StartEdge] = true;
printf("start edge:%d\n", StartEdge);
Q.push(StartEdge);
while (!Q.empty())
{
edge = graph[Q.front()];
while (edge)
{
nIndex = edge->dest;
if (!visited[nIndex])
{
visited[nIndex] = true;
printf("%d\t", nIndex);
Q.push(nIndex);
}
edge = edge->link;
}
Q.pop();
}
}
int main()
{
const int NODE_NUMBER = 7; // 10結點
const int EDGE_NUMBER = 11; // 10邊
Edge **graph = new Edge *[NODE_NUMBER]; // 圖
memset(graph, 0, sizeof(Edge *) * NODE_NUMBER); // 一開始沒邊
Input(graph, NODE_NUMBER, EDGE_NUMBER); // 輸入邊
printf("DFS:\n");
DFS(graph, NODE_NUMBER, 0); // 深度優先
printf("\n");
printf("BFS:\n");
BFS(graph, NODE_NUMBER, 0); // 廣度優先
printf("\n");
return 0;
}

2、鄰接矩陣表示的圖中利用bellman-ford演算法獲得單點最短路
#include <cstdio>
#include <cstring>
using namespace std;
#define INTEGER_INF 0xffff // 表示無窮大路徑
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 鄰接矩陣表示的圖
struct Graph
{
int **value; // 權值
int number; // 結點個數
};
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 初始化圖
// Input: number - 結點個數
// Output: graph - 圖
void InitGraph(Graph &graph, int number)
{
int i, j;
graph.value = new int *[number];
for (i = 0; i < number; i++)
graph.value[i] = new int[number];
for (i = 0; i < number; i++)
{
for (j = 0; j < number; j++)
{
if (i == j)
graph.value[i][j] = 0;
else
graph.value[i][j] = INTEGER_INF;
}
}
graph.number = number;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 析構圖
// Input: graph - 圖
// Output: graph - 析構後的圖的殼子
void FreeGraph(Graph &graph)
{
int i;
for (i = 0; i < graph.number; i++)
delete []graph.value[i];
delete []graph.value;
graph.number = 0;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 用戶在Console下輸入圖的邊
// Input: n - 邊的數量
// Output: graph - 加邊後的圖
void AddEdge(Graph &graph, int n)
{
int i, a, b, v;
for (i = 0; i < n; i++)
{
scanf("%d%d%d", &a, &b, &v);
graph.value[a][b] = v;
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: BellmanFord 演算法計算單源最短路
// Input: graph - 圖, index - 起點
// Output: true - 存在最短路 且 Console 下輸出起點到各個頂點的最短路
// false - 不存在最短路(存在邊權和為負的環路)
bool BellmanFord(Graph &graph, int index)
{
int num = graph.number; // 結點個數
int *v = new int[num]; // 記錄最短路
int i, j, t;
// 設定初值
for (t = 1; t < num; t++)
v[t] = INTEGER_INF;
v[index] = 0;
// 鬆弛
for (t = 0; t < num - 1; t++) // 循環i-1次
for (i = 0; i < num; i++)
for(j = 0; j < num; j++)
if (i != j && graph.value[i][j] != INTEGER_INF) // 如果兩頂點間有路
if (v[j] > v[i] + graph.value[i][j]) // 鬆弛
v[j] = v[i] + graph.value[i][j];
// 判斷是否存在邊權和為負的環路
for (i = 0; i < num; i++)
for (j = 0; j < num; j++)
if (graph.value[i][j] != INTEGER_INF &&
v[j] > v[i] + graph.value[i][j])
return false;
// 輸出
for (t = 1; t < num; t++)
printf("%d\t", v[t]);
return true;
}
int main()
{
Graph graph;
InitGraph(graph, 5);
AddEdge(graph, 10);
if (!BellmanFord(graph, 0))
printf("該圖中存在邊權和為負的環路!\n");
FreeGraph(graph);
return 0;
}

Ⅸ 用鄰接表表示的圖的輸出(PrintGraph)的演算法(C語言)

單鏈表類中的輸出流函數重載，輸出鏈表
圖類中再次重載輸出流函數。
一次頂點表的循環，輸出。
結果：<<start,dest,weight>,<。。。>>