當前位置:首頁 » 編程語言 » 鄰接表求入度c語言
擴展閱讀
webinf下怎麼引入js 2023-08-31 21:54:13
堡壘機怎麼打開web 2023-08-31 21:54:11

鄰接表求入度c語言

發布時間: 2023-05-27 07:28:33

① 已知一個有向圖的鄰接表,試編寫一個演算法求每個結點的出度和入度。

因此要在多個鄰接頂點之間約定一種訪問次序。@由於圖中可能存在迴路,在訪問某個頂點之後,可能沿著鋒悔租某條路徑銀兆又回到圖的深度優先搜索遍歷演算法p88
聯通的無迴路的無向圖,簡稱樹。樹中的懸掛點又前螞成為樹葉,其他頂點稱為分支點。

② 怎麼用c語言畫鄰接表

1、先把要講解的巧碼圖在下面展示一下,先看一下;

鄰接表是圖的常用儲存結構之一。鄰接表由表頭結點和表結點兩部分組成,其中圖中每個頂點均對應一個存儲在數組中的表頭結點。

③ C語言數據結構圖求入度的演算法

//思路:先把鄰接表芹坦拆轉換成逆鄰接表,這樣問題簡單多了。
//數組out,保存各節點的入度
void countindegree(AdjList gin, AdjList gout)
{

//設有向圖有n個頂點,建逆鄰接表的頂點向量。
for (int i=1;i<=n;i++)
{
gin[i].vertex=gout[i].vertex;
gin.firstarc=null;
}

//鄰嫌棗接表轉為逆鄰接表。
for (i=1;i<=n;i++)
{
p=gout[i].firstarc;//取指向鄰接表的指針。
while (p!=null)
{
j=p->adjvex;
s=(ArcNode *)malloc(sizeof(ArcNode));//申請結點空間。
s->adjvex=i;
s->next=gin[j].firstarc;
gin[j].firstarc=s;
p=p->next;//下一個鄰接點。
}//while
}//endof for

//統計各節點的入度
for (i=0; i<n; i++)
{
p = gin[i].firstarc;

while(p ! = null)
{
out[i]++;
p = p->next;
} //信談endof while
} //endof for

}//endof function

④ 求C# 鄰接表 代碼

我把租搜我過去課上老師發的C語言代碼發給你吧,你在VS里也可以運行。
#include<iostream.h>
#include<stdlib.h>
#define error 0
#define ok 1
#define Overflow -2
#define Underflow -2
#define max_vertex_num 20
int visited[max_vertex_num];
struct qnode{
int qdata;
qnode *next;
};
struct queue{
qnode *front;
qnode *rear;
};
void initqueue(queue &Q){
Q.front=Q.rear=(qnode *)malloc(sizeof(qnode));
if(!Q.front)
exit(Overflow);
Q.front->next=NULL;
}
void enqueue(queue &Q,int e){
qnode *p=(qnode *)malloc(sizeof(qnode));
if(!p) exit(Overflow);
p->qdata=e; p->next=NULL;
Q.rear->next=p; Q.rear=p;
}
void dequeue(queue &Q,int &e){
if(Q.front==Q.rear) exit(Underflow);
qnode *p=Q.front->next;
e=p->qdata;
Q.front->next=p->next;
if(Q.rear==p)
Q.rear=Q.front;
}
int queueempty(queue Q){
if(Q.rear==Q.front) return ok;
else return error;
}

typedef int vertextype;
typedef int Status;
typedef struct arcnode{
int adjvex;
struct arcnode *next;
}arcnode,*arcptr;
typedef struct{
vertextype data;
arcnode *firstarc;
}vnode;
typedef struct{
vnode adjlist[max_vertex_num];
int vexnum,arcnum;
int kind;
}algraph;
int locate(algraph g,vertextype v){
int i=0;
while(i<g.vexnum){
if(v==g.adjlist[i].data) return i;
else i++;
}
return -1;
}

Status create_dg(algraph &g){
vertextype v1,v2;
arcnode *p;
g.kind=0;
cin>>g.vexnum>>g.arcnum;
for(int i=0;i<g.vexnum;i++){
cin>>g.adjlist[i].data;
g.adjlist[i].firstarc=NULL;
}

for(int k=1;k<g.vexnum;k++){
cin>>v1>>v2;
int i=locate(g,v1);
int j=locate(g,v2);
if(i<0||j<0) return error;
p=(arcnode*)malloc(sizeof(arcnode));
p->adjvex=j;
p->next=g.adjlist[i].firstarc;
g.adjlist[i].firstarc=p;
}
return ok;
}

void dfs(algraph g,int v){
arcptr p;
visited[v]=1;
cout<<v<<g.adjlist[v].data<橘型早<' ';
p=g.adjlist[v].firstarc;
while(p){
if(visited[p->圓雀adjvex]==0) dfs(g,p->adjvex);
p=p->next;
}
}
void dfstraverse(algraph g){

for(int i=0;i<g.vexnum;i++)
visited[i]=0;
for(i=0;i<g.vexnum;i++)
if(visited[i]==0) dfs(g,i);
}
int firstadj(algraph g,vertextype v){//求第一鄰接頂點
int i=locate(g,v);
if(i<0) return -2;
int j=0;
if(g.adjlist[i].firstarc)
return g.adjlist[i].firstarc->adjvex;
else
return -1;
}
int nextadj(algraph g,vertextype v,vertextype w){ //求第一鄰接頂點的下個鄰接點
int i=locate(g,v), j=locate(g,w);
if(i<0||j<0) return -2;
j=0;
if(g.adjlist[i].firstarc)
return g.adjlist[i].firstarc->adjvex;
else
return -1;
}
void bfs(algraph g){
for(int i=0;i<g.vexnum;i++)
visited[i]=0;
queue q;
initqueue(q);
for(i=0;i<g.vexnum;i++){
if(visited[i]==0){
visited[i]=1;int v,w;
cout<<i;
enqueue(q,i);
while(!queueempty(q)){
dequeue(q,v);

for(w=firstadj(g,v);w>=0;w=nextadj(g,v,w))
if(visited[w]==0){
visited[w]=1;
cout<<w;
enqueue(q,w);
}
}
}
}
}

void main(){
algraph g;

create_dg(g);
bfs(g);
}

⑤ c語言,關於鄰接表的建立

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

同理

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

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

⑥ 數據結構-圖的鄰接表表示(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);


}



⑦ 建立一個有向鄰接表,計算他的初度和入度

深度優先是從某個頂點出發,訪問完後,尋找一個未訪問的鄰接頂點繼續深度優先,如果此路不同就往回退,所以看鄰接表,首先訪問V1,完了後順鏈尋找沒有訪問的鄰接頂點,自然鏈表中的第一個結點就侍穗罩是v3,接著轉到v3再族升來深度優先,訪問v3後,在其鏈表中第一個鄰接頂點是v4 接著訪問v4,下面走不通,回到v3,繼續順鏈往後,自然老鬧是v5,v5的鄰接頂點中v2還沒有訪問 所以序列為v1, v3, v4, v5, v2 再看廣度優先,從某個頂點完成後,需要一口氣將其鄰接未訪問的所有頂點都訪問,後面類推 於是過程是先v1,再順鏈將v3,v2依次訪問完,然後再依次訪問v3和v2的各個未訪問鄰接頂點,v3鏈表中順鏈可以訪問v4,v5,所以最後訪問序列為v1, v3, v2, v4, v5

⑧ 請教變成數據結構大神題目。 演算法設計:以鄰接表為儲存結構,編寫一個演算法求有向圖中每個頂點的入度。

鄰接表還是逆鄰接表?如果是逆鄰接表,每個頂點出發鄰接表的鏈表中的結點個數就是入度
如果是鄰接表過程如下:
有一個輔慧備助數組,大小就是頂點數量,所有元素初值都為0
從頭到尾遍歷每個頂點出發的鄰接表的結點鬧碧緩,只要當前結點的數據是幾(也就是第液模幾個結點被有向弧進入了),這個下標的輔助數組元素加1,等所有的鄰接表的小鏈表遍歷完了,這個輔助數組中各個下標的數字就是該頂點的入度

⑨ 編寫演算法,求有向圖中各定點的入度

先是根據鄰接表的頂點個數n,創建一個int型的數組a[n](用來存儲各頂點的入度),把a[n]中的每一項置為0。然後再鄰接表埋扮睜遍歷一下就行了,先是頂點遍歷,缺祥然後弧遍歷。
我大致寫一下演算法。
#define n 30;
struct diagraph
{
struct vertex * head;
struct Vertex ver;
struct Edge edg;
}
struct Vertex
{
int pos;
Vertex * nextVertex;
Edge * firstEdge;
};
struct Edge
{
int pos;
Edge * nextEdge;
Vertex * endPoint;//弧尾指彎歲向結點的指針
}
void main()
{
struct digraph a;
//先是鄰接表的建立,我就不寫了,建立完之後如下
int a[n];
int i,j;
struct Vertex * current = a.head;
struct Edge * eCurrent;
for(i=0;i<n;i++)
{
eCurrent=current->firstEdge;
while(eCurrent!=0)
{
a[eCurrent->pos]++;
eCurrent=eCurrent->nextEdge;
}
current = current->nextVertex;
}

}

我直接在知道上面寫的,只是個大概,能看懂的話就給個分吧

⑩ c語言 數據結構基本功能要求:

#include "stdio.h"

#define MAX 50

typedef struct LNode{
int data;
struct LNode *next;
}LNode;

void OutputDegree(int matrix[MAX][MAX], int n);
void Insert(LNode *head, int data);
void list(LNode *head);
void createAdjList(int matrix[MAX][MAX], int n, LNode *head[]);

void main()
{
int matrix1[MAX][MAX] = {{0,1,1},{1,0,1},{0,0,0}};
int matrix2[MAX][MAX] = {{0,1,0,1,0},{1,0,1,0,0},{0,1,0,1,1},{1,0,1,0,0},{0,0,1,0,0}};
int n; /* 頂點數 */
LNode *head[MAX];
int i;

n = 3;
printf("List degree of all vertex : \n");
OutputDegree(matrix1, n);

for(i=0; i<n; i++)
{
head[i] = (LNode *)malloc(sizeof(LNode));
head[i]->data = i+1;
}

createAdjList(matrix1, n, head);

printf("Adjancency List : \n");
for(i=0; i<n; i++)
{
printf("%d : ", head[i]->data);
list(head[i]);
printf("\n");
}

n = 5;
printf("List degree of all vertex : \n");
OutputDegree(matrix2, n);

for(i=0; i<n; i++)
{
head[i] = (LNode *)malloc(sizeof(LNode));
head[i]->data = i+1;
}

createAdjList(matrix2, n, head);

printf("Adjancency List : \n");
for(i=0; i<n; i++)
{
printf("%d : ", head[i]->data);
list(head[i]);
printf("\n");
}
}

/* 輸出頂點的度 */
void OutputDegree(int matrix[MAX][MAX], int n)
{
int InDegree[MAX]; /* 入度 */
int OutDegree[MAX]; /* 出度 */
int i, j;

for(i=0; i<n; i++)
{
InDegree[i] = OutDegree[i] = 0;
for(j=0; j<n; j++)
{
InDegree[i] += matrix[j][i];
OutDegree[i] += matrix[i][j];
}
}

for(i=0; i<n; i++)
{
printf("vertex %d : In - %d, Out - %d\n", i+1, InDegree[i], OutDegree[i]);
}
}

void Insert(LNode *head, int data)
{
LNode *pre = head->next;
LNode *temp;
temp = (LNode*)malloc(sizeof(LNode));
temp->data = data;
temp->next = NULL;

if(pre == NULL)
{
head->next = temp;
return;
}

for(; pre->next!=NULL; pre=pre->next);

pre->next = temp;
}

void list(LNode *head)
{
LNode *curr;
for(curr=head->next; curr!=NULL; curr=curr->next)
{
printf("%d\t", curr->data);
}
}

/* 根據鄰接矩陣構建鄰接表 */
void createAdjList(int matrix[MAX][MAX], int n, LNode *head[])
{
int i, j;

for(i=0; i<n; i++)
{
for(j=0; j<n; j++)
{
if(matrix[i][j] != 0)
Insert(head[i], j+1);
}
}
}